双循环操作策略下集装箱码头岸桥与集卡多船作业联合调度

梁承姬，杨全业

(上海海事大学 物流研究中心，上海 201306)

0 引 言

在过去几十年里，全球集装箱运输得到快速发展；近年来，虽然全球经济形势低迷，但集装箱吞吐量仍保持5%左右的增长趋势。2015年，全球前10大集装箱港共完成箱量21 634万标箱，其中上海港以3 653万标箱的吞吐量连续6年坐稳全球第一。

集装箱码头吞吐量不断增加，也促使码头改进其作业工艺，提升码头作业效率。目前，很多集装码头开始改进其单循环集卡调度策略，逐渐采用双循环集卡作业模式。但是，由于双循环集卡调度流程复杂，目前码头此项操作基本是基于调度员的作业经验，缺乏与之匹配的一套完整标准作业程序。由于码头作业设备较多且相互紧密配合，尤其是涉及到多船作业时岸桥和集卡的联合调度问题，实际操作中调度难度极大。

提高港口装卸效率是提升港口竞争力的关键因素，国内外许多学者对集装箱港口装卸系统进行了广泛的研究。CAO Jinxin等[1]、胡少龙等[2]和秦天保等[3-4]分别针对岸桥和集卡的联合调度问题进行研究；但是这些学者均是基于采用单循环集卡操作策略。LIU C I等[5]提出了4种不同的AGV分配规则，并通过仿真模型对比分析了4种分配规则作业效率。史飞等[6]针对自动化集装箱码头采用AGV方案和ALV方案的水平搬运装卸工艺，明确了仿真上下界，建立了仿真模型，并对港口设备进行优化配置，使其服务水平最大化，港船舶停留时间最短。E．NISHIMURA等[7]提出了集卡动态分配规则及集卡行驶路径优化；与传统的“静态分配”规则不同，动态分配规则将集卡车队为所有岸桥共享，而非指派一个车队特定服务于某一岸桥；动态调度可缩短集卡空驶距离，从而提高生产效率，降低成本。杨静蕾[8]提出了以集卡运行距离最小为目标的码头物流路径优化模型。曾庆成等[9-10]针对在以岸桥为核心的装卸过程基础上，讨论了集卡调度问题，提出了岸桥集卡动态调度模型，其目的是使岸桥等待时间最少，采用Q学习算法求解方法，并给出了最佳的集卡调度策略；建立岸桥集卡装卸作业调度的双层模型，通过下层集卡调度反馈上层岸桥调度，通过上下层之间的相互反馈形式从而达到集装箱整体优化方案。计明军等[11]考虑了在岸桥调度下集卡运输时间，提出了集卡岸桥协同优化模型，以完成集装箱操作量为目标，采用改进进化算法对所建模型进行求解。CAO Jinxin等[12]将岸桥和集卡捆绑在一起进行考虑，建立了混合整数规划(MIP)模型，运用遗传算法和改进约翰逊规则启发式算法对问题进行求解。梁承姬等[13]为缓解集装箱港口的泊位和岸桥资源比较紧张的现实情况，提高港口的运营效率，针对港口中泊位和岸桥的联合分配问题，在基于泊位和岸桥数量随时间动态变化的条件下，综合考虑泊位的连续性和船舶的泊位偏好性，建立了一个以船舶剩余作业量、船舶偏离偏好泊位的距离和岸桥移动次数之和最小为目标的混合整数线性规划划模型，在保证船舶能在最迟离港时间前离港的前提下，让船舶尽快离港，通过CPLEX 求解出此模型的最优解和算例分析，证实了文中的混合整数模型在解决实际港口中泊位和岸桥联合分配问题上的有效性。韩晓龙等[14]针对自动化集装箱港口中的AGV(automated guided vehicle) 的调度策略和数量配置问题，利用专业仿真软件eMPlant建立了包括岸桥、AGV、场桥和堆场资源在内的集装箱港口仿真模型，分析不同的AGV 调度策略及AGV 配置数量对集装箱港口装卸系统效率的影响，最后根据分析结果，给出集装箱港口对于AGV 的调度和数量优化的配置建议。

综合分析上述文献研究方向和研究内容，得出当前研究中存在以下不足：① 对于多船作业时大多基于采用单循环集卡操作策略；② 基于双循环作业模式下单船作业岸桥和集卡的联合调度优化。然而，对于同一艘船舶而言，其装卸同时进行的时间较少，应用双循环操作策略的机会因此大大下降。在研究多船岸桥集卡动态调度的过程中，要综合考虑多方因素，不仅要考虑船舶数量，还要考虑到集卡对其服务时的作业路线，即集卡是基于“作业面”调度还是基于“作业线”调度原则。另外，还要考虑到可作业岸桥数量，集装箱船舶靠泊位置等诸多会影响岸桥调度优化的额外因素，因此增加了研究的难度，对问题求解造成压力。在集装箱港口的实际作业中，往往需要同时进行多艘集装箱船舶的装卸操作，仅仅针对单船集卡静态调度优化的研究是无法满足港口的实际操作要求，无法正确合理地对港口岸桥操作进行指导。③ 在过往对岸桥集卡联合调度研究中，通常岸桥与集卡作为一个整体进行研究，而忽视了船舶之间距离对集卡调度的影响。在实际集装箱操作过程中，岸桥与集卡的调度优化问题研究是在泊位分配问题研究之后产生的，即岸桥调度时泊位分配的下个阶段，当多艘船舶靠泊之后，由于船舶自身的型号、装载货物类型以及集装箱码头实际情况，不同泊位对所停靠的船舶有不同要求。

基于此，笔者针对双循环操作策略下集装箱码头岸桥和集卡多船作业的联合调度问题进行研究。尝试建立岸桥和集卡联合调度基础模型，并在此基础上讨论船舶之间距离对集卡调度的影响。通过优化岸桥和集卡配置和调度，提高集卡利用效率减少集卡运输距离，从而提高码头整体装卸作业效率。

1 问题描述

基于“作业面”的调度方法有两种。笔者分别对这两种基于“作业面”的调度方法进行分析。第1种为集卡在进行不同船舶作业的岸桥间共享，如图1；第2种为集卡在同一船舶作业的岸桥间共享，即在不同“作业线”间共享集卡，如图2。两个集卡群分别对船舶1、2进行集装箱装卸作业，为船舶1、2服务的集卡同样是在不同岸桥间共享。

图1 集成集卡群岸桥-集卡装卸协同作业Fig. 1 Collaboration of QC and IT loading and unloading operationof the integrated truck group

图2 分散集卡群岸桥-集卡装卸协同作业Fig. 2 Collaboration of QC and IT loading and unloading operationof the decentralized truck group

笔者在岸桥集卡联合调度的基础上，以岸桥和集卡装卸船作业时间最小为目标，提出了岸桥和集卡联合调度基础模型，对集卡使用基于“作业面”调度方式，并对集卡路径进行优化，采用矩阵式编码遗传算法，在此基础上采用随机贪婪搜索方式对其进行改进。

对岸桥和集卡联合调度优化问题，考虑如下条件：

1)当岸桥a既可为泊位X服务又可为泊位Y服务时，在a完成泊位X任务后可继续为泊位Y服务。服务于泊位1的岸桥为qci,{i=1,2,3}；服务于泊位2的岸桥为qcj,{j=3,4,5,6}；服务于泊位3的岸桥为qck,{k=5,6,7}。泊位为离散状态；

2)两艘船舶在码头泊位停靠，两艘船舶同一时间分别进行装卸船作业；

3)一辆集卡每次只能完成一个集装箱作业，即不考虑集卡多载问题；

4)岸桥和集卡作业性能已知，因此不考虑岸桥和集卡故障情况下，其作业时间和移动时间均确定。

2 模型建立

2.1 双循环策略下岸桥与集卡联合调度模型

2.1.1 集合与参数

2.1.2 决策变量

当集装箱i的作业由岸桥k完成时，xki=1，否则xki=0；当集装箱i与集装箱i′由同一岸桥k完成，且作业顺序i'在i的前面，xkii′=1，否则xkii′=0；当集装箱i由集卡v运送时，yvi=1，否则yvi=0；当集装箱i与j作业均由集卡v完成，且i是j的前序任务时，yvij=1，否则yvij=0；若集卡的路径为u→v或v→u时，有zvu=1，否则zvu=0。

xijm为集卡从岸桥i到进口箱区j的运送次数m；zijm为集卡从出口箱区i到岸桥j的运送次数m。

2.1.3 目标函数和约束函数

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(1)表示岸桥的装卸作业时间、集卡运输时间之和最小，w1、w2为权重系数，由于在集装箱码头作业中，码头的整体作业效率因由岸桥的作业效率决定，在模型中对岸桥作业时间的权重设置为0.8，集卡运输时间设为0.2。式(2)～(5)表示保证每个集装箱能够被岸桥与集卡服务。式(6)～(9)表示岸桥作业序列中，每个集装箱最的前序作业或后序作业只有一个。式(10)～(11)表示从岸桥角度进行定义每个集装箱作业完成时间之间的关系。式(12)～(13)表示从集卡角度出发对完成集装箱操作量进行了定义。式(14)表示将每一出口集装箱一一与进口集装箱进行配对后，集卡在完成集装箱装卸后的行驶距离。式(15)～(16)表示每个集装箱只能被服务一次。式(17)表示若集装箱i与j为一对集装对，则要求集装箱i和j由一辆集卡作业。式(18)表示某一船舶待卸集装箱量等于集卡到进口箱区的运输次数。式(19)表示某一船舶待装集装箱量等于集卡从出口箱区到该船舶的运输次数。式(20)表示船舶的操作箱量等于这艘船的待装量和待卸量之和。式(21)表示待卸集装箱量要小于等于进口箱区的最大容量。式(22)表示待装箱量小于等于出口集装箱数量。式(23)表示定义集卡作业序列。

3 遗传算法

遗传算法是一种智能的搜索算法，通过编码、选择、交叉以及变异操作来达到局部搜索和全局搜索，但如果任意初始化、任意化交叉算子、任意化变异算子以及任意化适应度函数，标准遗传算法很难使全局收敛达到最优解。但在一定情况下，自适应遗传算法(AGA)可实现上述情况，因此笔者提出AGA对模型进行求解，其流程如图3。

图3 AGA流程Fig. 3 Flow chart of AGA

3.1 染色体编码

一个染色体个体中有6层编码，第1层代表进口集装箱编号，第2层代表出口集装箱编号，第3层代表岸桥服务集装箱顺序，第4层代表集卡服务集装箱顺序，第5层代表进口箱区编号，第6层代表出口箱区编号。如图4，对岸桥1服务进口集装箱的优先级为39、46，服务出口集装箱的优先级为46、7。集卡4服务进口集装箱的优先级为22、44，服务出口集装箱的优先级为19、40.对于进口箱区，进口集装箱22、38进入进口箱区4。出口集装箱19、40都同来自于出口箱区11。

图4 染色体编码Fig. 4 Chromosome encoding

3.2 适应度函数

使用轮盘赌法和“精英保优”策略相结合方式选择算子，保留前20%的优良个体让它们不进行交叉和变异[15]。

文中的适应度函数如式(24)：

(24)

式中：favg为当代种群个体平均适应度值；f为原始适应度，此适应度函数是针对求解目标函数最小化，若问题本身求解为最小化问题，则f直接取目标函数，若目标函数本身是求解最大值，则需要将目标函数通过转化为求解最小值；g为其差值在(-10，10)以外个体的数目；c为(f-favg)绝对值中的最大值的数量级。

3.3 遗传操作

3.3.1 交 叉

用轮转法选择两个父代中的个体行遗传操作，对这两个父代个体进行n的次交叉操作，分别计算这两个子代的适应度值，并记为i1,i2(i=1,2,…,n+1)，然后选出max(i1,i2)最大值的一组结果(记为L)，与父代的两个个体比较，比较父代适应度值与L大小，选择大的作为新一代的两个个体，其目的是为了产生更好的后代。为避免个别高适应值个体多次被复制到下一代而导致种群多样性退化，因此为每一代个体设一临界点，高于临界点的个体只复制一代进入下一代。

具体交叉方式如图5。采用多点交叉，在父代中选择两个切点，交换这两个切点第3列到第6列基因值。

图5 染色体交叉演示Fig. 5 Chromosome intersected demonstration

3.3.2 变 异

变异方式：与交叉方式相同，在父代中随机的选择两个切点，切点位置交换这两个切点基因座上的第3列到第6列的基因值。如图6。

图6 染色体变异演示Fig. 6 Chromosome variation demonstration

3.3.3 控制系数选择

交叉概率以及变异概率如式(25)、(26)：

(25)

(26)

式中：favg为所有个体平均适应度值；fmax为种群最大适应度个体；f′为两个进行交叉父代中适应度较大的个体；f为要进行变异个体的适应度值；pc1>pc2>pc3；pm1>pm2>pm3；A=9.903 438；r为一个很小的正数。

上述要进行的交叉个体概率，通过其f′与favg比较，使其在不同区间进行自适应调整。当f′≥favg，则pc∈[pc3,pc2]；当f′

4 数值实验

假定有两艘船舶A、B要同时进行装卸作业，且A船和B船分别停靠于泊位1、2。A船要操作的集装箱量为100 TEU，待卸集装箱量为50 TEU，待装集装箱量为50 TEU；B船操作的集装箱量为100 TEU，待卸集装箱量为50 TEU，待装集装箱量为50 TEU。涉及堆场堆区16片。岸桥作业效率为60～70 TEU/h，集卡行走速度为50 m/min，装卸船到堆场区的距离由泊位决定，如表1。堆场各堆区的卸箱量和装箱量见表2。

表1 泊位和进、出口箱区之间距离Table 1 Distance between the berth and the inlet and exit box m

表2 堆场各堆区的卸箱量与装箱量Table 2 Unloading quantity and loading quantity of each pile in the yard m

文中AGA参数：Psize=100，最大迭代代数Gmax=300，pc1=0.9、pc2=0.8、pc3=0.6、pm1=0.01、pm2=0.005、pm3=0.001、r=1。采用MATLAB编程实现算法开发。

岸桥对集装箱进行装卸作业所涉及的约束条件较多，因此在遗传算法基础上采用随机贪婪适应性搜索方法(greedy randomized adaptive search procedure，GRASP)进行改进。构建初始种群时采用GRASP进行创建。这一过程分为可行解以及对可行解优化两阶段，即先将集装箱作业任务加入到某一岸桥作业任务中，并进行局部优化搜索。在GRASP所创建的初始种群基础上采用AGA。

4.1 求解结果及分析

由表3可知：增加集卡数量不仅可降低运作时间，还可降低计算时间。当作业任务数量不变，集卡数量为28和35时，运作时间可以减少71%，其模型计算时间也分别减少了29%和57%。同时，增加集卡数量能在一定程度上减少作业时间。但增加集卡数量并不一定总能降低运作时间，如当集卡数量为28和35时，其运作时间均为477 min。

表3 遗传算法计算结果Table 3 Calculation results of genetic algorithm

4.2 船舶间距离与集卡调度关系

通常情况下，集装箱码头和到港船舶由于其型号、类型以及所载货物在都有自己的偏好位置，根据偏好位置停靠在不同泊位上。在对集卡的调度问题上，许多学者采用的是基于“集成作业面”调度，而忽视船舶之间距离对其影响。

在实际集装箱码头操作中，若两艘船舶停靠的泊位距离较近时，基于“集成集卡群”可以有效的提高集卡的利用率；若两艘船舶距离较远时，采用“分散集卡群”调度，即把集成集卡群分成若干集卡群，分别对船舶进行装卸作业，这样即便于管理，又能减少集卡总运输距离，从而减少对船舶的服务时间。

船舶间距离与集卡调度对比，如表4。由表4可看出：船舶间距离小于275 m时，基于“集成调度”集卡运行距离和作业时间小于“分散调度”；等于275 m时，集成调度与分散调度在作业时间和运行距离相差不大两者效率相同；随着船舶间增大，基于“分散调度”优于“集成调度”。

表4 船舶间距离与集卡调度对比Table 4 Distance between ships and the contrast of containertruck dispatch

图7为当船舶间距离为400 m时，集成集卡群集卡调度行驶总距离和分散集卡群集卡调度行驶距离收敛图。由图7可发现：分散集卡群集卡行驶距离小于集成集卡群集卡行驶距离。且可看出：当迭代次数达到100～150代时候，数值趋于稳定状态，从而证明了文中算法的有效性和可行性。

图8(a)、(b)分别代表当船舶间距离达到400m时分散集卡群1与分散集卡群2在时间上的调度甘特图；图8(c)为集成集卡群在时间上调度甘特图。由图8可发现：分散集卡群1与分散集卡群2作业时间之和小于集成集卡群作业时间。

图7 集卡调度行驶距离收敛Fig. 7 Driving distance convergence of container truck dispatch

图8 集卡调度甘特图Fig. 8 Gantt chart of container truck dispatch

5 结 语

基于集装箱码头对集装箱操作流程特点，建立了装卸作业时间最短的协同优化模型。笔者设计了矩阵编码方式的AGA对该模型进行求解优化，讨论了染色体编码、交叉、变异规则，并采用随机贪婪适应性搜索过程对AGA进行改进。通过对算法和模型进行验证，该方法能很好解决岸桥-集卡协调调度优化问题，为提高码头的运营效率提供了决策支持。

在笔者研究中，分析了船舶之间的距离与集卡调度的关系，并通过算例验证了算法及模型的正确性，给出了相应的优化方案，使集装箱码头的集卡作业效率大幅度明显提升。

[1] CAO Jinxin, SHI Qixin, LEE Der-horng. A decision support method for truck scheduling and storage allocation problem at container[J].TsinghuaScience&Technology, 2013, 13(Sup1):211-216.

[2]胡少龙，胡志华．集装箱港口桥吊、龙门吊和集卡集成调度的全自由度模型[J]．武汉理工大学学报，2012，34(5)：58-63．

HU Shaolong, HU Zhihua. Full freedom optimization for integrated quay cranes, trucks and yard cranes in container port[J].JournalofWuhanUniversityofTechnology, 2012, 34(5): 58-63.

[3]秦天保，彭嘉瑶，沙梅．带任务顺序约束的岸桥集卡集成调度约束规划模型[J]．上海海事大学学报，2013，34(3)：1-7．

QIN Tianbao, PENG Jiayao, SHA Mei. Constraint programming model for integrated quay crane and yard truck scheduling with precedence relations[J].JournalofShanghaiMaritimeUniversity, 2013, 34(3): 1-7.

[4]秦天保，彭嘉瑶，沙梅．基于约束规划的岸桥与集卡集成调度[J]．计算机工程，2014，40(5)：196-202．

QIN Tianbao, PENG Jiayao, SHA Mei. Integrated quay crane and yard truck scheduling based on constraint programming[J].ComputerEngineering, 2014, 40(5): 196-202.

[5] LIU CI, IOANNOU PA. A comparison of different AGV dispatching rules in an automated container terminal[R]//TheIEEE5thConferenceonIntelligentTransportationSystems. Singapore, Singapore, 2002: 356-371.

[6]史飞，张新艳，赵启元．新型自动化集装箱码头仿真分析[J]．机械与电子，2008(12)：55-59．

SHI Fei, ZHANG Xinyan, ZHAO Qiyuan. Simulation and analysis of a new type of automated container terminal[J].MachineryandElectronics, 2008(12): 55-59.

[7] NISHIMURA E, IMAI A,PAPADIMITRIOU S. Yard trailer routing at a maritime container terminal[J].TransportationResearchPartE:LogisticsandTransportationReview, 2005, 41(1): 53-76.

[8]杨静蕾．集装箱码头物流路径优化研究[J]．水运工程，2006(1)：32-35．

YANG Jinglei. Logistics routing optimization of container terminals[J].Port&WaterwayEngineering, 2006(1): 32-35.

[9]曾庆成，杨忠振．集装箱码头集卡调度模型与Q学习算法[J]．哈尔滨工程大学学报，2008，29(1)：1-4．

ZENG Qingcheng, YANG Zhongzhen. A Scheduling model and Q-learning algorithm for yard trailers at container terminals[J].JournalofHarbinEngineeringUniversity, 2008, 29(1): 1-4.

[10]曾庆成，杨忠振．集装箱码头作业调度双层规划模型及求解算法[J]．哈尔滨工程大学学报，2007，28(3)：277-281．

ZENG Qingcheng, YANG Zhongzhen. A bi-level programming model and its algorithm for operation scheduling in container terminals[J].JournalofHarbinEngineeringUniversity, 2007, 28(3): 277-281.

[11]计明军，靳志宏．集装箱码头集卡与岸桥协调调度优化[J]．复旦学报(自然科学版)，2007，46(4)：476-480．

JI Mingjun, JIN Zhihong. A united optimization of crane scheduling and yard trailer routing in a container terminal[J].JournalofFudanUniversity(NaturalScience), 2007, 46(4): 475-488.

[12] CAO Jinxin, SHI Qixin, LEE Der-horng. Integrated quay crane and yard truck schedule problem in container terminals[J].TsinghuaScience&Technology, 2010, 15(4): 467-474.

[13]梁承姬，夏桑，鲁渤．集装箱港口连续泊位与岸桥的动态配置[J]．重庆交通大学学报(自然科学版)，2016，35(5)：155-159．

LIANG Chengji, XIA Sang, LU Bo. The dynamic allocation of continuous berths and quay cranes in container terminals[J].JournalofChongqingJiaotongUniversity(NaturalScience), 2016, 35(5): 155-159.

[14]韩晓龙，樊加伟．自动化港口AGV调度配置方针分析[J]．重庆交通大学学报(自然科学版)，2016，35(5)：151-154．

HAN Xiaolong, FAN Jiawei. Analysis of AGV dispatching and configuration simulation of automated container terminals[J].JournalofChongqingJiaotongUniversity(NaturalScience), 2016, 35(5): 151-154.

[15]金晶，苏勇．一种改进的自适应遗传算法[J]．计算机工程与应用，2005，41(18)：64-69．

JIN Jing, SU Yong. An improved adaptive genetic algorithm[J].ComputerEngineeringandApplications, 2005, 41(18): 64-69.