动态模式下的集装箱综合调度路径优化算法

郑斯斯

（惠州学院 数学与统计学院，广东 惠州 516007）

1 研究背景

伴随全球贸易保护主义的抬头态势，国际物流市场持续萎靡，港口需要提高效率以吸引更多的航班挂靠；此外，船舶大型化的发展趋势也对集装箱码头的装卸效率提出了更高的要求.面对新的挑战，世界范围内的集装箱港口运营商纷纷利用物流自动化技术来提升港口的效率和竞争力.在集装箱码头，集装箱的翻箱率是衡量码头作业效率的关键因素.假设码头的年吞吐量为40 万TEU，翻箱作业成本为20 元/TEU，翻箱时间为4min/TEU，则翻箱率每降低3%，码头每年可以节约作业成本达84 万元，节约作业时间达800 h.因此，减少翻箱数量能大幅度节约作业成本和作业时间.翻箱率的高低在很大程度上是由箱位调度的效果所决定，科学合理的箱位调度策略能有效减少翻箱率.尽管越来越多的自动化集装箱码头投入运营，但关于集装箱码头从传统向自动化转型中出现的集装箱的箱位调度、翻箱等关键科学和实际问题的研究有待深入开展.

学者们针对自动化集装箱码头的研究主要集中在码头布局和自动化设备2 个方面，笔者结合学术界已有的研究成果，对其研究现状进行简要梳理.早期针对自动化集装箱码头的研究着重于码头布局方面，结合现场作业特点可知，自动化码头有垂岸式布局和水平式布局2 种形式，垂岸式布局不但可以减少水平运输车辆的行驶距离，而且可以提高堆场的利用率，因此这种布局更适合自动化码头［1-4］. 针对码头的自动化程度，刘广红等［5］对半自动化码头、AGV 全自动化码头、跨运车全自动化码头和立体分配全自动化码头的布局、装卸流程、港区内交通组织和环保性能等多方面进行分析与对比.王施恩等［6］对欧美几个大型的自动化码头的平面布置、堆场特征等方面进行分析，研究结果表明：垂岸式布局能有效将海侧自动化车流和陆侧人工驾驶车辆分离，有利于港区的交通组织.装卸设备主要有自动化堆码起重机（ASC）、自动化轨道式龙门吊起重机（ARMG）、轮胎式龙门吊起重机（ARTG），对起重机进行合理调度以避免冲突是国内外学者的研究重点.其中，针对ARTG 调度的研究较少，Rizaldi 等［7］以集卡停留时间和ARTG 的能源消耗为评价指标，用仿真方法对3 种场桥调度方案进行比较.针对ARMG 调度的研究较多，以双ARMG协调调度为主.魏晨等［8］研究了接力式作业的ARMG 调度问题；裴磊磊和苌道方［9］考虑了2台ARMG之间的协调性和缓存区的容量限制；周静娴和胡志华［10］对双ASC执行任务的序列进行优化，提出规避冲突后的最优作业序列.李敏和韩晓龙［11］考虑了集装箱任务组的时间窗约束，并且提出了8 条优先权规则来解决同一贝位上任务的冲突.Han等［4］总结了4 种起重机运作模式，以最小化作业时间为优化目标，构建了混合整数规划模型并设计了遗传算法进行求解.

已有研究文献对论文开展提供了良好的理论与技术支持，但仍有待解决的问题：大多数研究假设提箱过程中没有新进集装箱，箱位调度时并没有结合集装箱的进场和离场；较少研究关注动态模式下，集装箱同时进出场的情况.因此，有必要进行深入探讨，进而提出相应的调度方案.作者在该领域也做了部分研究，在Zheng 等［12-16］、郑斯斯和王爱虎［17-18］等文献中分别研究了集装箱码头的翻箱问题、箱位选择问题等.本文将在已有研究基础上对集装箱调度问题进行研究，分别分析集装箱的进场和出场情况，并在动态模式下考虑集装箱同步进场和离场，构建双层目标规划模型，开发集装箱综合调度的路径优化算法（POA）研究满足理论与现实的双重需求，在理论上为我国集装箱码头的自动化和智能化建设提供方法论，在实践上为集装箱码头成本的降低、效率的提升和管理水平的改善提供决策依据和指导.

2 集装箱的综合调度模型

2.1 基本问题描述及符号定义

在堆场中，根据集装箱的不同属性通常会分成不同的箱区，每个箱区包括多个贝，每个贝有垂直堆放的多个栈，每个栈可以堆垛多层集装箱.在集装箱码头堆场，最便捷的装卸设备是轨道龙门吊，龙门吊的走动包括水平方向以及垂直方向.其中，水平方向的走动由龙门吊大车完成，是指在不同贝位之间的操作；垂直方向的走动由龙门吊小车完成，是指同一贝位不同栈之间的操作.本文所用的基本符号见表1.

表1 集装箱调度问题的符号说明

（续表1）

2.2 模型构建

集装箱调度包括：集装箱进场和出场，集装箱调度的目标是减少压箱或翻箱数量，为此构建集装箱的综合调度模型，目标函数和约束条件如下：

约束条件由上至下分别表示每次作业中，任意集装箱只能放在一个箱位中；任意箱位slot（m，n，k）最多只能放一个集装箱；龙门吊的初始位置在第1贝；每一贝的集装箱数量不超过该贝位的具体容量；任意集装箱均不允许悬空放置；集装箱a 和b分别放在箱位slot（m，n，k）和slot（m，n，k-z），且有P（a）＜P（b），即优先级更高的集装箱a箱位比集装箱b低层，则移走集装箱a时，需先移走集装箱b，记一次翻箱，即Rmn（k-z）=1（m=1，2，…，M；n=1，2，…，N；k=1，2，…，K）.

3 集装箱的综合调度算法

3.1 调度策略

由于集装箱调度问题是一个NP-hard 问题，模型很难求出精确解.因此，作者在现场调研的基础上，提炼多个调度策略并构建规则库，设置启发式算法以减少一些非优的调度路径.以下调度策略将有助于在调度过程中，选取最优箱位.

（1）同贝优先，邻贝次之原则（Same Bay First &Neighboring Bays Second，SFNS）.针对阻塞箱落箱位置的选取，优先考虑移到同贝箱位，同贝箱位已满时，再考虑移到邻贝.

（2）阻塞箱较少原则（Least-Obstructive Heuristic，LOH）.当阻塞箱在同贝位内搜寻落箱位置时，根据集装箱的优先级，比较阻塞箱与同贝位内不同栈集装箱的优先级.栈内阻塞箱越少，造成压箱或翻箱数量就越小.

（3）就近原则（Nearest-Slot Heuristic，NSH）.为了操作便捷，经常将阻塞箱放在同贝位且离原箱位最近栈的空箱位上.龙门吊移动距离越小，作业时间越短.

（4）最矮栈原则（Lowest-Slot Heuristic，LSH）.出于安全考虑，经常将集装箱放在同贝位内最矮栈，保证平均高度最矮.堆垛高度越低，发生事故概率越低.

（5）重心稳定原则（stable core Heuristic，SCH）.在多贝位的箱位分配中，优先将集装箱放在低层，保持重心稳定.

3.2 算法框架

构建规则库并将多个规则嵌入集装箱调度，设计多个规则并行使用下的算法.集装箱进场的路径优化算法（Path Optimum Algorithm，简称进场POA）的步骤详见算法1，该算法使得集装箱进场作业更加科学合理.

算法1：集装箱进场的路径优化算法（进场POA）

输入：进场序列；集装箱总数量；

变量：A表示一个进场序列，矩阵规模为1行s列；B 表示最终输出的箱位矩阵；B（bay，stack，tier）表示集装箱的箱位，其中（bay，stack，tier）=（m，n，k），当m=1，B（bay，stack，tier）可以简单记为B（stack，tier）；s 表示总的集装箱数量；rth container 表示集装箱的优先级，即第r 号集装箱；N（sm）表示箱区中集装箱移动的总次数；N（sy）表示箱区中集装箱压箱的总次数；

输出：集装箱移动的总次数；集装箱压箱的总次数；最优分配路径；运行时间.

1：设置初始进场序列A规模是1行s列，并开始计时

2：初始设置N（sm）←0，N（sy）←0，rth container←1，G（n）←1 {重置计数器}

3：for 分配的集装箱数量＜=s do

4： if Bay的数量m=1 then

5： 矩阵B（stack，tier）的最底层与矩阵A 第1至第n列一致

6： for 集装箱数量=（n+1）：s do {依次判断第（n+1）至第s个集装箱的箱位}

7： 执行规则一：压箱数量最少.压箱数是指要放入的元素，与当前列中所有元素相比，如果要放入元素的优先级更小，记为1，一共小几个，记为几，如果该列最高层已放满，则记为inf，比较各列的压箱数量，选择最少的一列，记压箱数N（sy）=w

8： 执行规则二：最近原则.依次判断要放入元素与每一列的横向距离，与第一列距离1，第二列记为2，第三列记为3，直至最后一列，如果该列最高层已放满，则记为inf，比较与各列的距离，选择最近的一列

9： 执行规则三：最矮原则.依次判断要放入元素与每一列的纵向距离，如果第一列已有元素2个，记为2，如果第二列已有元素为3，记为3，如果该列最高层已放满，则记为inf，比较各列的已有元素，选择最少一列

10： 依次执行规则一至规则三，比较各列已有元素，选择最少一列，将目标箱放在第n栈（n=1，2，…，N）第k层（k=1，2，…，K），并继续判断下一个集装箱

11： N（sm）←N（sm）+1

12： N（sy）←N（sy）+w

13： end for

14： else {Bay的数量m＞=1}

15： 贝的数量为m，栈的数量为（n/m），层的数量为k

16： 第1贝矩阵B（1，stack，tier）的最底层与矩阵A 第1 至第（n/m）列一致，第2 贝矩阵B（2，stack，tier）的最底层与矩阵A第（n/m+1）至第（2n/m）列一致，第m 贝矩阵B（m，stack，tier）的最底层与矩阵A 第［（m-1）*n/m+1］至第n列一致

17： for 集装箱数量=（n+1）：s do {依次判断第（n+1）至第s个集装箱箱位}

18： 依次判断规则一至三后，继续判断规则四：重心稳定堆垛原则，当该贝最底层已满，跳到下一贝安排箱位，并继续判断下一个集装箱

19： N（sm）←N（sm）+1

20： N（sy）←N（sy）+w

21： end for

22： end if

23：end for

24：直到系统内没有目标箱

25：返回集装箱移动的总次数；集装箱压箱的总次数；最优箱位分配路径；运行时间.

26：结束计时

集装箱离场的路径优化算法（简称离场POA）的步骤详见算法2，该算法能使得翻箱作业更有效率，加快运行速度.

算法2：集装箱离场的路径优化算法（离场POA）

输入：箱位矩阵（任一状态）；集装箱总数量；

变量：B表示一个三维矩阵；B（bay，stack，tier）表示集装箱的箱位；S表示总的集装箱数量；rth container表示集装箱的优先级，即第r 号集装箱；N（sm）表示箱区中集装箱移动的总次数；N（sr）表示箱区中集装箱翻箱的总次数；G（n）为决策变量，等于1时表示移动到其它贝位，等于0时表示其它.

输出：集装箱移动的总次数；集装箱翻箱的总次数；最优翻箱路径；运行时间.

1：设置初始三维矩阵B规模是M×N×K（即M贝N栈K层），并开始计时

2：初始设置N（sm）←0，N（sr）←0，rth container←1，G（n）←1{重置计数器}

3：for 栈的数量＜=（N-1）do

4： 决定是否需要将阻塞箱移动到其它贝位

5： ifB（bay，n，tier）=0 then

6： 将阻塞箱放在该贝位的第n栈（n=1，2，…，N），并继续判断下一个集装箱

7： else

8： 判断该贝位中其它栈是否有空箱位

9： ifG（n）==1{该贝位中的其它栈没有空箱位可用于放置阻塞箱，该阻塞箱需要移动到其它贝位}

10： ifbay＞1 or bay＜mthen

11： fora=1：1：（bay-1）or b=（bay+1）：1：mdo

12： 判断第a贝位或第b贝位中是否有空箱位

13： ifG（n）==0then

14： 该阻塞箱可放于第a贝位或第b贝位

15： end if

16： end for

17： end if

18：N（sm）←N（sm）+1

19：N（sr）←N（sr）+1

20： end if

21： end if

22：end for

23：N（sm）←N（sm）+1

24：N（sr）

25：直到系统内没有集装箱

26：返回集装箱移动的总次数；集装箱翻箱的总次数；最优翻箱路径；运行时间.

27：结束计时

根据集装箱综合调度的详细流程（图1），将多个规则嵌入算法，从而得到集装箱综合调度路径优化算法（简称综合调度POA），由此得到优化调度路径、移箱数量、压箱数量、翻箱数量、运行时间.

图1 集装箱综合调度的详细流程图

集装箱综合调度POA 的优点表现在：算法可适用于单贝、多贝的箱位调度和动态模式下的进出场综合调度；启用规则库，多个规则并行使用，对集装箱的移动路径进行多层筛选；有助于排除大量非优的集装箱选择方案，从而减少了计算复杂度；针对集装箱的不同初始状态，只需要改变初始输入矩阵，就能求解问题，并且运行的代码改变得越少，箱位选择决策时间越短，越符合高速运转的集装箱码头.

4 算例分析

4.1 集装箱进场

数值实验的第一部分将测试集装箱进场的性能，数值测试基本场景为：箱区内有M贝N栈K层，一共有1 到S号集装箱需放入该箱区.要求S≤M×N×K-（K-1），使得箱区内有足够的空箱位便于后续翻箱使用.随机生成100组M×N×K-（K-1）个集装箱的进场序列，执行进场POA并记录对应数据.

由在单贝和多贝不同利用率下的集装箱平均压箱数量和计算机平均运行时间（见表2、表3）可知：使用进场POA可以合理分配单贝或多贝集装箱，控制集装箱的压箱数量，作业效果优于人工作业；使用进场POA能在短时间内为集装箱分配合适箱位；当箱区规模为10贝16栈9层，最大容量达到1 440 TEU的情况下，计算机的运行时间仍旧控制在0.2 s以内.

表2 单贝不同利用率下的集装箱平均压箱数量和计算机的平均运行时间

表3 多贝不同利用率下的集装箱平均压箱数量和计算机的平均运行时间

4.2 集装箱离场

数值实验的第二部分将测试集装箱离场的性能，数值测试基本场景为：箱区内有M贝N栈K层，一共有1到S号集装箱在该箱区内.要求S≤M×N×K-（K-1），使得箱区内有足够的空箱位便于翻箱使用.生成M×N×K-（K-1）个集装箱，并且每个集装箱的提箱序列已经给定.随机生成100组初始状态下的三维矩阵实例，执行离场POA并记录对应数据.

由箱区不同利用率下的集装箱平均翻箱数量、计算机平均运行时间以及龙门吊移动的曼哈顿距离（表4）可知：使用离场POA能在最大程度上控制集装箱的翻箱数量，且作业效果将远远优于仅仅依赖人工作业经验，翻箱数量越少，作业速度越快，作业效率越高；使用离场POA 能将计算机的运行时间保持在一个稳定的较低水平；使用离场POA能在最大程度上控制龙门吊移动的曼哈顿距离，且作业效果将远远优于仅仅依赖人工作业经验以及仅仅采用单一的翻箱策略，当龙门吊移动的曼哈顿距离越少，龙门吊的损耗越少，并且作业成本越低.

表4 箱区不同利用率下的集装箱平均翻箱数量、计算机平均运行时间以及龙门吊移动的平均曼哈顿距离

4.3 集装箱综合调度

数值实验的第三部分将测试集装箱综合调度的性能，数值测试基本场景为：1个箱区内有M贝N栈K层，有多个集装箱需要进入或离开箱区.这里随机生成一组示例，执行综合调度POA 并记录对应数据，便于观察算法的运行结果.分2 种情况进行讨论：第1 种情况是进场和提箱序列确定的情况下，为集装箱分配合适箱位后，再将这些集装箱提出堆场，这2个过程是分离的，而且进场和离场过程中没有新进集装箱；第2种情况是进场和提箱序列已定，且集装箱进场和离场是同步进行的，2个过程不再分离.综合调度POA实现了从理论模型到实际场景的改进，实现集装箱同步进出场的调度，拉近理论研究与实践应用之间的距离，向管理实践靠拢.

5 小结

该文以集装箱码头转型升级为背景，探讨动态模式下集装箱的综合调度问题，融入实践经验元素的调度策略，并行使用多个规则，对集装箱的移动路径进行多层筛选.在此基础上，实现集装箱同步进出场的调度，让进场和出场不再分离，拉近理论研究与实践应用之间的距离，向管理实践靠拢.数值测试结果表明：本文提出的综合调度POA 适用于单贝或多贝下的集装箱调度问题，集装箱可以随意进场和出场，算法实现在多个规则筛选下为集装箱分配合适的箱位，有效减低翻箱率和压箱数量，提高作业效率.实现了集装箱进场和出场同步进行的箱位调度，也提炼出适用于集装箱调度问题的共性策略，达到了优化作业的目标，但这些研究是在一定假设条件下进行的，所以得到的结论仍旧存在不足之处.为使研究更全面，更适应集装箱码头的作业场景，进一步研究方向可以考虑不确定因素.