邱亚　梁承姬　张悦

摘要：为提高自动化集装箱码头堆场中自动化轨道吊（automated stacking crane，ASC）的作业效率，研究箱区动态接力点对双ASC作业效率的影响。考虑双ASC作业过程中的安全距离、相互冲突等因素，建立以最小化双ASC最长完工时间为目标的混合整数规划模型，利用遗传算法对该模型进行求解。与固定贝位接力模式进行对比，结果表明，相较于固定贝位接力模式，动态接力点模式下双ASC的作业效率更高。在不同规模算例背景下，将遗传算法与CPLEX的计算结果进行对比，验证了遗传算法的有效性。

关键词：自动化集装箱码头; 自动化轨道吊; 动态接力点; 遗传算法

中图分类号：  U691.3

文献标志码：A

Coordination scheduling of twin automated stacking cranes under dynamic relay point mode

QIU Ya， LIANG Chengji， ZHANG Yue

（Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

In order to improve the operation efficiency of automated stacking cranes （ASCs） in the automated container terminal yards， the influence of dynamic relay points in the block on the operation efficiency of twin ASCs is studied. Considering the safety distance and conflicts in the operation process of twin ASCs， a mixed integer programming model aiming at minimizing the longest completion time of twin ASCs is established， which is solved by the genetic algorithm. Compared with the fixed shell relay mode， the results show that the twin ASCs are more efficient under the dynamic relay point mode. In the background of different scale examples， the calculation results from the genetic algorithm and CPLEX are compared to verify the effectiveness of the genetic algorithm.

Key words：

automated container terminal; automated stacking crane; dynamic relay point; genetic algorithm

0 引 言

集装箱运输的高速发展正在改变世界港口、船舶和装卸工艺的传统格局。与传统集装箱码头不同，自动化集装箱码头的堆场采用垂岸式的布局，每个箱区有两台自动化轨道吊（automated stacking crane， ASC）分别负责海侧和陆侧作业。因此，ASC与自动导引小车 （automated guided vehicle， AGV）或外集卡的交接只能发生在箱区的两端。随着集装箱码头的发展，码头作业效率的瓶颈已经从码头前沿转移到了后方的堆场。ASC是堆场中主要的调度设备，其作业效率很大程度上影响了堆场的作业效率。考虑到本文所研究的并行式双ASC之间不可相互穿越的特性，对双ASC实行合理高效的调度是非常有必要的。

国内外学者对传统码头场桥和自动化集装箱码头ASC的调度做了很多的研究。初良勇等[1]考虑场桥作业的时间及成本，建立了集装箱场桥的智能調度优化数学模型，并设计了基于遗传算法（genetic algorithm，GA）的模型求解策略。刘志雄等[2]针对多场桥调度问题，提出一种混合演化策略算法，通过与其他算法的结果对比，证明了该算法在优化多场桥调度问题时的有效性。CHANG等[3]为实现场桥全局最优调度，提出一种新的动态滚动范围决策策略，并用启发式算法和仿真模型的计算结果验证了所提方法的有效性和效率。裴磊磊等[4]在考虑ASC之间协调性、交接区容量限制的基础上，采用GA与仿真相结合的方法对混合整数模型进行求解，得出最短的作业总时间和最小的ASC间行驶距离之差。卢毅勤[5]考虑了AGV的行驶速度和ASC作业时间的不确定性，建立了AGV与ASC的联合调度优化模型，并采用改进的粒子群优化算法进行求解。HE等[6]考虑了船舶到达时间的不确定性，研究了任务组到达时间和处理量不确定情况下场桥的调度问题。CARLO等[7]针对并行式双ASC在作业过程中发生冲突时的优先级问题提出了14条优先级规则，并量化所选优先级规则的影响，得出最优的优先级规则组合。NG等[8]研究了同一箱区多场桥作业相互干扰的问题，并开发了一种基于动态规划的启发式算法来解决场桥的调度问题。PARK等[9]为提高ASC的作业效率，在考虑翻箱的情况下，提出了基于启发式算法和局部搜索的双ASC实时调度方法，以实现AGV和外集卡的等待时间最短的目标。郑红星等[10]设计了混合和声模拟退火算法，并采用实时预倒箱来降低倒箱对场桥作业的影响，以此减少船舶装船作业时间。徐飞庆[11]将场桥调度问题转化为一个基于软时间窗的车辆路径优化问题，在考虑节能减排的基础上，实现场桥调度过程中能耗成本和延误成本最低的目标。SHA等[12]从低碳角度探讨场桥调度问题，提出了一种整数规划模型，以最小化场桥的总能耗。

针对接力区的研究如下：黄继伟等[13]为解决双ASC存取箱作业冲突问题，在箱区内设置接力区，最小化双ASC最长完工时间，并用GA进行求解。KRESS等[14]研究了在ASC不可相互穿越的条件下，在箱区内设置接力区，并提出一种动态规划算法和相关的波束搜索启发式算法进行求解。GHAREHGOZLI等[15]为研究堆场内接力区的设置对ASC作业的影响，以最小化ASC的完工时间或等待时间为目标，对接力区集装箱堆放位置以及接力区的有无、大小、数量等展开研究。

已有的研究多数针对固定贝位接力模式，而很少考虑不同接力模式对ASC作业效率的影响。本文采用动态接力点的双ASC接力模式对进出口集装箱进行作业调度。在对双ASC的调度研究中，以最小化双ASC的最长完工时间为目标，建立混合整数规划模型，用GA和CPLEX对不同规模算例进行求解，并与固定贝位接力模式的调度结果进行对比。

1 问题描述

在自动化集装箱码头，ASC只能在箱区的两端与AGV或外集卡进行交接作业。为提高ASC的利用率，避免双ASC出现忙闲不一的情况，对双ASC实行有效的调度就显得尤为重要。由于本文所研究的双ASC不可相互穿越，在已有的固定贝位接力模式下，接力点固定在箱区的中间，双ASC的作业范围受到限制，只能在接力区的某一侧进行作业。然而，在动态接力点模式下，接力点不固定，陆侧ASC可到海侧作业，海侧ASC也可到陆侧作业。

双ASC的动态接力点模式可分解为两个阶段：第一阶段，一侧ASC将需要接力的任务箱放至动态接力点，这个阶段为主作业;第二阶段，另一侧ASC从动态接力点提走任务箱并放至目标位置，这个阶段为接力作业。在双ASC的动态接力过程中，如果任务箱的起点和终点在箱区的同一侧（即都在图1虚线的左侧或右侧），那么这个任务箱由该侧的ASC独立完成;如果任务箱的起点和终点不在箱区的同一侧，那么就需要ASC接力完成，即海侧（陆侧）ASC将任务箱放至动态接力点，陆侧（海侧）ASC结束正在进行的任务后去完成接力任务。

相较于已有的固定贝位接力，本文研究的双ASC动态接力体现在接力点的不固定上。如果某侧ASC有任务箱a需要接力，找到该ASC的下一个任务箱b所在位置，将a箱放至靠近箱区中间位置且与b箱所在位置相隔一个贝位处，这样就确定了接力点。如图1所示，以任务箱起点在海侧为例，1号箱的起始位置在海侧，终点位置在陆侧，由于起点与终点不在同侧，所以海侧ASC将1号箱放至距其下一个任务2号箱一个贝位处，等待陆侧ASC过来完成接力，此时海侧ASC离开并进行下一个任务作业。起点在陆侧的任务箱作业原理相同。在双ASC作业过程中可能会出现ASC互相干扰的情况，如图2所示：由于2台ASC不能相互跨越，且海侧作业优先级高于陆侧作业优先级，一旦2台ASC发生作业冲突，海侧ASC就优先于陆侧ASC进行作业，在此过程中，陆侧ASC要与海侧ASC保持一定的安全距离。

2 模型建立

本文考虑双ASC不可跨越以及作业过程中保持安全距离等因素，建立混合整数规划模型。为得到双ASC最长完工时间的最小值，假设：（1）接力区存储空间足够大;（2）ASC在移动时始终保持匀速，不考虑加速或减速;（3）不考虑ASC小车的移动;（4）ASC提箱与放箱所用的时间一致，并且为固定值;（5）在ASC作业过程中不考虑翻箱;（6）ASC在交接点作业时无须等待。

2.1 符号说明

n为总任务数量;K为ASC的集合，K={1，2}，k∈K;Jk为第k台ASC的任务集;J为所有ASC的任务集，J=J1∪J2;A为同一任务拆分后的子任务对{i，j}的集合，A={（i，j）|i∈Jk，j∈Jk′，k≠k′};P1为目标箱在初始位置提箱任务的集合;D1为主作业中在接力点放箱任务的集合;P2为接力作业中目标箱在接力点提箱任务的集合;D2为接力作业中目标箱在目的地放箱任务的集合;P=P1∪P2;D=D1∪D2;v为ASC的移动速度;l为单位贝位的长度;si为任务i的开始时刻;ti为任务i的操作完成时刻;B为单箱区总的贝位数，b=1，2，…，B;Tij为ASC从任务i的结束位置移动到任务j的初始位置所需时间，当i=j时，表示ASC从一个任务的起点移动到终点的时间;oi为操作提箱任务i或放箱任务i所需的时间;σ为双ASC作业的安全距离;bik为ASC k作业任务i时所在的貝位;h（1）i∈{0，1}，若bi1为海侧交接点则h（1）i=1，否则h（1）i=0;h（2）i∈{0，1}，若bi2为陆侧交接点则h（2）i=1，否则h（2）i=0;M为足够大的数。

决策变量：x（k）ij∈{0，1}，若ASC k以（i，j）的顺序进行作业则x（k）ij=1，否则x（k）ij=0;u（k）i∈{0，1}，若ASC k从任务i开始作业则u（k）i=1，否则u（k）i=0;w（k）i∈{0，1}，若ASC k在任务i结束作业则w（k）i=1，否则w（k）i=0;y（k）tb∈{0，1}，若ASC k在时刻t处于贝位b则y（k）tb=1，否则y（k）tb=0。

2.2 目标函数及约束条件

式（1）是目标函数，表示最小化双ASC的最长完工时间;式（2）表示每个接力任务的主作业只进行一次操作;式（3）表示每个接力任务的接力作业最多进行一次操作;式（4）和（5）确保ASC 1和ASC 2的移动路径从箱区的两端开始，在最后一个任务处结束;式（6）表示ASC从一个任务移动到下一个任务所需要的时间;式（7）表示同一任务的操作完成时刻约束;式（8）保证任务间作业的连续性;式（9）表示任意两个任务之间的起止时间关系;式（10）表示接力点的提箱操作应当在这个接力点放箱操作完成之后再进行;式（11）和（12）确保一台ASC每次只能作业一个任务箱;式（13）保证一个任务总的作业时间由ASC的移动时间与操作时间组成;式（14）确保交接点处的任务靠近哪一侧就只能由那一侧对应的ASC完成;式（15）表示对于由同一任务拆分而来的两个任务，先完成主作业，后完成接力作业;式（16）保证双ASC在作业过程中保持安全距离。

3 算法设计

GA是一种常用的元启发式算法，双ASC的动态接力问题是NP难问题，而GA对该类问题具有良好的适应性，因此本文采用GA进行求解。

3.1 染色体编码与解码

染色体采用实数编码的形式，整数部分表示集装箱的任务编号，小数部分表示接力作业的不同阶段。染色体长度为任务箱量，即ASC作业任务数。编码时，首先对ASC和集装箱任务进行编号，海侧ASC编号为1，陆侧ASC编号为2。为满足式（4）和式（5）约束，ASC 1和ASC 2的第一个任务的初始贝位必须是贝位1和贝位42（见第4.1节）。将染色体的前半段设置为需要ASC 1完成的任务，后半段设置为需要ASC 2完成的任务，以满足式（13）约束。对于不需要接力的任务，一个任务对应一台ASC，对于需要接力的任务，其作业的2个阶段需要2台ASC共同完成。如图3所示：7.1表示任务7的第一个阶段，由ASC 1完成;7.2表示任务7的第二个阶段，由ASC 2完成。

解码过程分为2个阶段，首先根据对应基因位将任务分配至2台ASC，然后按照任务段中的任务顺序依次解码，得到ASC 1和ASC 2对应的集装箱作业序列。在图3所示的染色体中，解码得到ASC 1的作业序列为{2，7.1，6，10.2，9，8，5}，ASC 2的作业序列为{3，7.2，10.1，1，4}。

3.2 适应度函数

适应度函数为f（u）=1/Cmax，其中Cmax为ASC最长完工时间的最小值。

3.3 遗传操作

3.3.1 选择操作

本文的选择操作采取精英保留的策略，将种群中适应度值大的前10%的个体保留下来，与随机产生的90%的新个体形成新种群。

3.3.2 交叉操作

由于本文染色体的集装箱任务部分由海侧ASC和陆侧ASC完成，所以交叉时也将其分为海侧ASC作业序列和陆侧ASC作业序列2部分进行交叉，且每個部分都采用双切点交叉法。根据交叉概率，每次从上一代个体中选择2个个体作为父代，如图4a所示：在每个父代个体的海侧ASC作业序列部分随机生成2个交叉点①和②，将这两个交叉点之间的基因值进行交换;在每个父代个体的陆侧ASC作业序列部分随机生成2个交叉点③和④，也将这两个交叉点之间的基因值进行交换。得到的新个体见图4b。

3.3.3 变异操作

本文采用逆转变异法，即在每台ASC的作业序列中随机选2个点，将其基因值进行交换。同样地，由于染色体的集装箱任务部分由海侧ASC和陆侧ASC完成，所以变异时也将其分为海侧ASC作业序列和陆侧ASC作业序列2部分进行变异。图5为变异操作示意图。

3.3.4 修复操作

经过交叉和变异操作后，可能会产生一些不可行的染色体，因此需要进行基因修复。本文设计的基因修复规则如下：

规则1：如果新种群中产生了不满足式（14）约束的个体，即染色体中出现了接力任务的接力作业开始时间早于主作业的完成时间的情况，则此条染色体需要修复，将相关基因值的位置进行调整。

规则2：对于不需要接力的任务以及由需要接力的任务拆分而来的2个子任务，ASC只能对该任务作业一次，即2台ASC对应的作业序列中的基因值都各不相同。如果ASC 1或ASC 2对应的染色体作业序列中有2个基因值相同（如图4b所示），则需要基因修复。修复结果如图4c所示。

4 算例分析

4.1 参数设置

某自动化集装箱码头的堆场采用两端式双ASC的布置，一个箱区有40个贝位，设海侧交接点为贝位1，陆侧交接点为贝位42，从海侧至陆侧贝位号依次递增。海侧ASC的起始位置为贝位1，陆侧ASC的起始位置为贝位42。2台同型号的ASC协同作业，在移动过程中保持匀速，并且速度相同，安全距离为1个贝位，放箱操作和提箱操作的时间为70 s。以20个集装箱任务为例，输入的数据见表1。

交叉和变异算子对 GA性能有重要影响，问题类型的不同导致算法参数值的选取存在差异。为找到适当的交叉和变异算子的参数值，本文对动态接力点模式下双ASC的调度问题进行多次实验。设置种群数量为100，最大迭代次数为100，实验在Intel（R） Core（TM）i5的处理器、内存4 GB的PC上进行，在MATLAB 2018a平台上编程实现。实验结果如表 2 所示：在所有备选参数中，当交叉概率Pc=0.9，变异概率Pm= 0.2时算法性能最佳。在后面的数值实验中本文将采用此组交叉和变异参数值进行计算。

4.2 两种模式下的结果分析

4.2.1 动态接力点模式下双ASC调度结果

图6为动态接力点模式下ASC的移动路线图，当双ASC发生作业冲突时，陆侧ASC等待海侧ASC完成作业后再进行作业。动态接力点模式下双ASC的最长完工时间为3 078 s，双ASC的具体调度结果见表3。图7为动态接力点模式下调度结果的甘特图，其中每个矩形两侧的部分是ASC提放箱的时间，中间部分是ASC移动的时间（或移动加等待的时间），任务7～14为接力任务，由2台ASC共同完成。

4.2.2 固定贝位接力模式下双ASC调度结果

图8为固定贝位接力模式下ASC移动路线图，从图8可以看出双ASC在作业过程中未发生冲突，海（陆）侧ASC只能在海（陆）侧移动，不能到另一侧进行作业。固定贝位接力模式下双ASC的最长完工时间为3 251 s，双ASC的具体调度结果见表4。图9为固定贝位接力模式下调度结果的甘特图。

由表3和4可知，动态接力点模式下双ASC的完工时间为3 078 s，相较于固定贝位接力模式，双ASC的作业效率提高了5.3%。从ASC的作业效率看，在相同任务量的情况下，动态接力点模式优于固定贝位接力模式。从图6和8可以看出，在固定贝位接力模式下，ASC的移动范围有一定的局限性，而动态接力点模式下ASC的移动范围没有局限，这更有利于ASC间的相互协作。在图7和9中可以更直观地看出每个任务的作业时间以及ASC间的冲突情况，虽然动态接力点模式中有干扰发生，但ASC整体的完工时间是优于固定贝位接力模式的。

为进一步验证动态接力点模式的有效性，本文设置不同规模的算例，并用GA和CPLEX对不同作业模式、不同规模的算例进行求解，结果见表5。

从表5可以看出：在不同任务量下，GA和CPLEX求出的ASC完工时间相差不大;由于CPLEX对大规模算例求解较慢，所以当任务量大于等于50时，本文设置CPLEX的求解时间的上限为14 000 s，即运行时间到达14 000 s后，算法停止运行;对于任务量为200的算例，由于CPLEX的内存不足，所以无法在可接受的范围内求出最优解。通过对比GA和CPLEX的计算结果能够得出，GA计算出的结果是有效并且能被接受的，可以作为最优解。

5 结 论

本文针对自动化集装箱码头堆场单箱区双自动化轨道吊（ASC）的接力问题进行了研究。考虑了双ASC不可跨越以及作业过程中保持安全距离等因素，以最小化双ASC的最长完工时间为目标，建立混合整数规划模型，并设计遗传算法（GA）进行求解。在算例分析部分，本文设计了不同规模的算例，计算结果表明，与固定贝位接力模式相比，在动态接力点模式下双ASC的最长完工时间更短，作业效率更高。然而，在实际操作中，ASC作业过程中的翻箱以及ASC与自动导引小车（AGV）和外集卡的协调等问题都会影响ASC的作业效率，在后续研究中可以考虑双ASC与AGV和外集卡的联合调度，使研究更加具有现实意义。

参考文献：

[1]初良勇， 阮志毅， 李淑娟. 基于遗传算法的港口集装箱堆场场桥智能调度优化[J]. 中国航海， 2018， 41（1）： 48-52.

[2]刘志雄， 李俊， 张煜， 等. 基于混合演化策略算法的多场桥调度优化[J]. 计算机应用与软件， 2016， 33（5）： 242-247.

[3]CHANG Daofang， JIANG Zuhua， YAN Wei， et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling[J]. Advanced Engineering Informatics， 2011， 25： 485-494. DOI： 10.1016/j.aei.2011.02.003.

[4]裴磊磊， 苌道方. 基于仿真優化的自动化集装箱码头双ARMG调度研究[J]. 广西大学学报（自然科学版）， 2017， 42（2）： 500-510. DOI： 10.13624/j.cnki.issn.1001-7445.2017.0500.

[5]卢毅勤. 自动化码头堆场设备联合调度不确定优化[J]. 计算机仿真， 2019， 36（8）： 325-328.

[6]HE Junliang， TAN Caimao， ZHANG Yuting， et al. Yard crane scheduling problem in a container terminal considering risk caused by uncertainty[J]. Advanced Engineering Informatics， 2019， 39： 14-24. DOI： 10.1016/j.aei.2018.11.004.

[7]CARLO H J， MARTNEZ-ACEVEDO F L. Priority rules for twin automated stacking cranes that collaborate[J]. Computers & Industrial Engineering， 2015， 89： 23-33. DOI： 10.1016/j.cie.2015.04.026.

[8]NG W C， MAK K L. Yard crane scheduling in port container terminals[J]. Applied Mathematical Modelling， 2005， 29： 263-276. DOI： 10.1016/j.apm.2004.09.009.

[9]PARK T， CHOE R， OK S M， et al. Real-time scheduling for twin RMGs in an automated container yard[J]. OR Spectrum， 2010， 32： 593-615. DOI： 10.1007/s00291-010-0209-0.

[10]郑红星， 刘保利， 匡海波， 等. 考虑实时预倒箱的出口箱堆场多场桥调度优化[J]. 中国管理科学， 2018， 26（9）： 85-96. DOI： 10.16381/j.cnki.issn1003-207x.2018.09.009.

[11]徐飞庆. 基于软时间窗的集装箱码头场桥调度研究[J]. 物流工程与管理， 2016， 38（3）： 23-26. DOI： 10.3969/j.issn.1674-4993.2016.03.008.