双40英尺岸桥的集卡调度问题研究

梁承姬，严亚平，李玲君

(上海海事大学 物流科学与工程研究院，上海 201306)

随着集装箱吞吐量增加、船舶大型化发展和高昂油价等问题的出现，大型船舶对于选择停泊港口的装卸效率提出了更高的要求，以达到缩短船舶在港时间，降低运输成本的目的。在各种因素的催化下，第1台双40英尺岸桥诞生于2005年，由上海振华港机制造。此后，这种能同时抓起 2个双 40英尺集装箱的新式岸桥得到了越来越广泛的关注和应用。由于双40英尺岸桥可以同时装卸2个集装箱，所以其理论上的装卸效率比常规岸桥高50%以上，然而其实际使用情况却不是很理想，据2007年洋山港10台双40英尺岸桥与10台常规岸桥的统计数据相比：双 40英尺岸桥平均综合效率比常规岸桥只提升了5.35%；双40英尺岸桥投资额较常规岸桥高15%左右；钢丝绳维护成本高70%左右；单箱能耗高25%左右；由于增加了一套起升机构，双40英尺岸桥故障台次约为常规岸桥的2.3倍[1]。这些成本的增加都需要通过提高双 40英尺岸桥的装卸效率来解决，而制约双 40英尺岸桥的效率的一个重要因素便是岸桥与集卡之间的协同调度问题。国内外关于集装箱码头岸桥集卡调度问题的研究主要集中在对常规岸桥集卡调度模型和算法的研究。CAO等[2]将岸桥与集卡整合到一起考虑，打破了以前研究中单独考虑某一个问题的模式，并建立了一个整数规划模型。尚晶等[3]在研究集装箱装卸作业面的集卡调度问题中，将减少集卡的空驶行程作为调度优化目标之一。计明军等[4]在考虑集卡运输时间和岸桥作业时间的基础上，提出了以运输时间最短为目标的集卡调度优化模型法。Lee等[5]建立了集卡运输时间和等待延迟时间权重和最小的数学模型，并利用启发式算法进行求解。秦天保等[6]针对岸桥集卡协同调度问题，建立混合整数规划(MIP)模型和约束规划(CP)模型，设计OPL语言使用不同规模的实例对约束规划模型和 MIP模型进行测试。TANG等[7]在岸桥集卡联合调度中，运用改进 PSO算法进行计算单项进口集装箱作业和双向进出口集装箱作业问题，并与 CPLEX 求解器的结果进行对比。乐美龙等[8]建立以单船岸桥最小作业时间为目标的混合整数规划模型P1，通过简化模型P2求解岸桥调度模型P1的下限边界值和排程数据，在此基础上，运用基于规则的启发式算法求解模型 P1的岸桥调度时序表。钱继锋等[9]建立了“岸桥-集卡-堆场”双向作业计划协同优化模型，并设计了混合智能算法对其求解。Kaveshgar 等[10]利用遗传算法和贪婪算法来解决岸桥、集卡的集成调度问题，最终求得集装箱装卸作业的最小完工时间。Homayouni 等[11]在对自动化集装箱港口的岸桥、集卡、场桥的集成调度的研究中，发现在精确度和调度方案中，基于模拟退火算法的 SP-AS/RS系统的设备调度不如遗传算法的计算结果。康志敏等[12]基于 Petri网研究了利用改进遗传算法解决集卡调度问题。这种调度方法经过分析表明，可以在一定程度上提高装卸作业的“重进重出”。韩晓龙等[13]针对集卡到达的不确定性和动态性提出了新的调度规则，建立了岸桥集卡的协同调度模型，采用遗传算法进行求解，证明了模型和算法在解决岸桥集卡调度问题上有效。采用改进的遗传算法。李尤丰等[14]采用作业面装卸方式，建立了以集卡空驶时间最小为目标的集卡动态调度模型，采用改进的遗传算法求解，并引入 N6 邻域方法，设计了多种交叉操作和变异操作。关于双 40英尺岸桥的集卡调度研究比较少，尚晶[15]建立以岸桥延迟时间和集卡空驶时间为目标的集卡调度模型，设计了基于自适应交叉和变异概率的改进遗传算法，证明改进遗传算法在求解双 40英尺岸桥集卡调度问题上有较优方案。本文在其研究的基础上，针对双 40英尺岸桥作业的特点，采用双循环的作业方式，将集卡到达岸桥的同步性作为装卸效率的考核目标之一，以岸桥的延迟时间及集卡的空驶时间、任务对的时间差为目标建立考虑双 40英尺岸桥的集卡调度模型，并设计遗传算法及启发式算法进行求解并对求解结果进行分析。

1 问题描述

双40英尺岸桥可以同时装卸2个40英尺或者4个20英尺的集装箱，这表示，岸桥可以同时对两辆集卡进行作业。这对岸桥和集卡的配合，即集卡的同步性和次序性提出了较高的要求。同步性是指：双40英尺岸桥在卸船作业时需要2个空集卡同时到达岸桥来装载进口箱至箱区，而装船时需要2个集卡同时将堆场的出口集装箱运送至岸桥。次序性是指：集卡的调度要同时考虑岸桥的作业顺序，要根据岸桥的装卸计划来安排集卡。这些限制条件增加了港口内部作业调度的复杂性。

对于双40英尺岸桥一次操作的2个集卡，如果到达的时间不同步，一则会造成前一辆集卡的等待，二则会使岸桥不能按照计划时间开始工作，且岸桥的后续所有任务都会延迟。

2 模型建立

2.1 模型假设

由于现实问题的复杂性，为了便于问题求解和模型建立，现设定如下假设：

1) 集装箱的规格是相同的，集卡一次服务于一个集装箱。而岸桥一次可以服务2个40尺箱或4个20尺箱，为简便计算，设定2个20尺或1个40尺箱为1个集装箱。

2) 集卡在移动过程中总是匀速行驶，行驶时间由距离所得；

3) 船舶的配载符合双 40英尺岸桥的作业要求，且出口集装箱数和进口集装箱数都为偶数，确保双40英尺岸桥一次操作2个集装箱。

2.2 模型参数及变量

本文的目的是为集装箱码头参与装卸工作的岸桥和集卡安排合适的数量。每一对待装卸的集装箱称之为一个任务对，用i和j来表示。要装船的集装箱的起点位置是它在于堆场的位置，终点位置是对应于负责装船的岸桥的位置。而卸船的集装箱的起点位置是负责卸船的岸桥处，而终点位置是存放于堆场的位置。在一个船舶装卸的过程中，用 J表示要装卸的集装箱的集合，n为各个岸桥要装卸的任务的总量，|J|=n。

在此为每一条集卡路径安排一个虚拟开始节点O和一个虚拟结束结点F，对应于虚拟工作，假设集卡池位于虚拟岸桥处，集卡从集卡池出发相当于集卡位于虚拟岸桥处O开始工作，集卡完成任务回到集卡池相当于集卡位于虚拟岸桥处 F结束工作，即虚拟开始岸桥O和虚拟结束岸桥F与集卡数目相同。参与调度的每一辆集卡都必须从虚拟工作开始，到虚拟工作结束。

O虚拟开始岸桥；F虚拟结束节岸桥，参与调度的每一辆集卡都必须从虚拟工作开始，到虚拟工作结束；T表示在工作中所用到的集卡的集合，|T|=t；Q表示参与装卸作业的岸桥的集合，岸桥序号用k, l表示，|Q|=q；mk表示岸桥k需要完成的集装箱任务对的装卸总量，mO=mF=t；i和j表示双40英尺岸桥每次操作的任务对，每一个任务对同时包含2个小任务i=(i1,i2)，j=(j1,j2)，岸桥每一次操作的任务序号用e, f(e, f=1, 2)表示，ie即表示双40英尺岸桥操作i任务对的第e个集装箱；α，β，μ分别表示为岸桥延迟时间、集卡空驶时间及任务对到达岸桥处的时间差的目标权重系数，由于岸桥不允许延迟，所以：α>>β。

表1 的计算方法(if堆场表示任务jf所在的堆场位置)Table 1 Calculation method of (if yard indicate the location of jf in yard)

表1 的计算方法(if堆场表示任务jf所在的堆场位置)Table 1 Calculation method of (if yard indicate the location of jf in yard)

前接任务性质kie后继任务性质ljf clif kie lif kiet装载 装载 岸桥k装载ie的时间+集卡从岸桥k到jf堆场的时间+场桥操作jf的时间+集卡从jf堆场到岸桥l的时间集卡从岸桥k到jf堆场的时间装载 卸载 岸桥k装载ie的时间+集卡从岸桥k到岸桥l的时间 集卡从岸桥k到岸桥l的时间卸载 卸载 岸桥k操作任务ie的时间+集卡从岸桥k到ie堆场的时间+场桥操作任务ie的时间+集卡从ie堆场到岸桥l的时间集卡从ie堆场到岸桥l的时间卸载 装载岸桥k操作任务ie的时间+集卡从岸桥k到ie堆场的时间+场桥操作任务ie的时间+ie堆场到j堆场的时间+场桥操作任务jf的时间+集卡从jf堆场到岸桥l的时间ie堆场到jf堆场的时间

决策变量为：

同一集卡在完成双40英尺岸桥k处的集装箱ie任务时，接着操作双40英尺岸桥l处的集装箱jf，其值为1，否则为0。

2.3 目标函数及约束条件

其中目标函数(1)表示所求目标为岸桥的延迟时间、集卡的空驶时间及操作同一任务对的2辆集卡到达岸桥的时间差的加权和最小。约束(2)和约束(3)确保对于任意一个任务只有一个继后任务和一个继前任务；约束(4)和约束(5)表示任意一个岸桥操作任务对的实际开始时间在计划开始时间之后；约束(6)表示岸桥在操作同一任务对的两岸集卡都到达码头前沿后开始工作；约束(7)表示同一辆集卡操作的前后相接的2个任务开始时间之间的关系，M为前一任务的开始时间；约束(8)表示岸桥操作任意一个任务对时的产生的延迟时间；约束(9)和约束(10)表示虚拟开始结点的数目与虚拟结束结点的总数目相同，并且与集卡的数量相同。

3 算法实现

3.1 遗传算法实现

1) 染色体编码和个体选择

首先将各个集装箱任务进行优先级排序，以优先级序号来表示各个集装箱任务，染色体中的序号表示的是任务优先级。设开始工作时，集卡从集卡池 0出发，经过不同的节点，完成所有分派的任务都返回集卡池。由于每一辆集卡表示一条路径，所以每一条染色体包含多条子路径，各条子路径之间以0分割。例如，一条染色体可以表示为如图1所示。

图1 一条染色体示例Fig. 1 A set of chromosome samples

由于上述模型的目标函数取的是最小值，所以需要将目标函数映射为适值函数，令 F =- m in u，从而将求最小化的问题转化为求最大化的问题。

3) 交叉操作

采用双切点交叉原则产生子代。在验证子代的合法性时根据不同的情况分别采取修复策略或者拒绝策略，见图 2。当子代中出现的子路径不等于集卡的数目或者出现空的子路径时，则子代不合法，需要被拒绝；当子代中出现子路径有序号重复时，采用部分映射交叉(PMX)的修复原则进行修复；当子代中出现子路径中的序号乱序时，则进行自动局部整(如图3所示)。

上述染色体的各条子路径如下。

集卡路径1：集卡池0→节点1→节点3→工作完成

集卡路径2：集卡池0→节点2→节点4→工作完成

集卡路径3：集卡池0→节点5→节点6→工作完成

集卡路径4：集卡池0→节点7→节点8→工作完成

个体选择概率的分派方法使用的是轮盘赌法，适应度值越高被选择的可能性越大。

2) 适应度函数

图2 交叉操作拒绝策略Fig. 2 Rejection way based on crossover

图3 交叉操作及修复操作Fig. 3 Crossover operator and repair operator

4) 变异操作

采用换位变异原则执行变异操作。在生成的子代中也会出现局部优先级序号乱序的情况，处理方法同交叉操作(如图4~5)。

图4 变异操作Fig. 4 Mutation operator

图5 变异修复操作Fig. 5 Mutation and repair operator

3.2 多级目标优化的启发式算法实现

针对集装箱港口双 40英尺岸桥的工作特点，在此设计一个多级目标优化的启发式算法，来与遗传算法进行比较(见图6)。

图6 多级目标优化的启发式算法流程Fig. 6 Multiple target optimization heuristic algorithm process

在所设计的启发式算法中，综合考虑了岸桥装卸集装箱的作业顺序、同时作业的2辆集卡的协调问题及任务的选择分派情况来制定集卡的实时调度策略。采用多级优化方法，将操作同一个任务对的2辆集卡到达岸桥处的时间差作为第一级优化目标，将任务分派结束后的岸桥延迟时间及集卡空驶时间作为第二级优化目标。为各级目标设定不同的权重，根据最终目标时间最小化来决定任务分派方案。在此启发式算法中主要用到2个策略：

最紧急任务选择策略：对于双 40英尺岸桥同时操作的2个集装箱，任何一个集装箱的延迟都会对后续的安排产生很大的影响，所以双 40英尺岸桥对于集卡的同步性与协调性要求比常规岸桥的要求更高，最紧急的任务就是优先权最高的任务。

集卡分派策略：由于双 40英尺岸桥对操作同一个任务对的两辆集卡有同步性的要求，在为任务分配集卡时，首先以第一级优化目标为决策条件。在分派任务对的各个任务时，要将任务分配给集卡同步性最好的集卡，满足2辆集卡到达岸桥处的时间差最小的要求。为了防止分派方案陷入局部最优的情况，在分派方案时采用允许任务根据优先级的顺序自动插入到已分派好任务的集卡路径中，后续任务将自动延时操作。循环结束后进行第二级目标的选择，最终确定解决方案。

4 案例及结果分析

4.1 案例

本文设定某港口某时刻有一艘船舶需要装卸，有2台双40英尺岸桥参与装卸任务，每个岸桥分配10个任务对，共有40个集装箱任务需要操作，首先为这2台岸桥分配4辆集卡。任务的计划开始时间与工作顺序如表2所示。

表2 任务对的工作顺序Table 2 Work order of couple tasks

表3 集卡行驶时间及设备操作时间Table 3 Vehicle transportation time and equipment operation time

根据表1的计算方法及上述数据可以得到相邻2个工作间的准备时间，为模型的求解做准备。由于案例中涉及到随机数据的产生，所以对每一个结果都运行 10次，然后各自取平均值，目标权系数设为：α=0.4，μ=0.5，β=0.1。

4.2 结果分析

将上述案例用遗传算法和启发式算法分别求解，2种方法分别采用Python编程及C#编程实现。设启发式算法的最大循环次数是200。

表4 案例求解结果Table 4 Results for case s

由表4可以看出，2种求解方法都可以满足时间上的实时调度要求，遗传算法的求解结果明显要优于启发式算法的求解结果，其求解的结果更准确。这说明本遗传算法的设计有效。

但是双 40英尺岸桥的效率并没有得到最大发挥，仍然存在很大的岸桥延迟时间，究其根本原因是在此案例中分配的集卡数量不能很好地满足双40英尺岸桥的调度需求，集卡不能在双40英尺岸桥准备好开始工作时将集装箱运到岸桥处，造成双40英尺岸桥操作当前任务及后续任务的延迟。为了尽量使双 40英尺岸桥发挥其效率，需要进一步增加集卡的数量来配合双40英尺岸桥的装卸工作。

4.2.1 集卡数量对结果的影响

为了说明不同数量集卡对于装卸效率的影响，利用遗传算法就上述案例进行求解不同数量集卡条件下的集卡分配问题，得到最佳的岸桥－集卡配比。求解结果数据图形化如图7所示。

图7 双40尺岸桥不同集卡数量配比各个指标Fig. 7 Indexes under different number of cards for dual 40’quay crane

由图7可以看出，随着集卡数量的增多，目标函数逐渐减小，当集卡数量达到 11辆时，目标函数开始趋于稳定，说明对于此案例 11台集卡足以满足双40英尺岸桥工作的需求，当集卡数量大于8台时，集卡的空驶时间开始回升，这是因为当集卡增多到一定程度的时候，由于工作量不是太大，有一部分集卡将不会进行边装边卸的操作，从而增加集卡的空驶时间。

岸桥的延迟时间及同任务组集卡时间差在集卡数量大于 11时，趋于收敛。在港口作业中，双40英尺岸桥与集卡相比，双40英尺岸桥不能有效工作引起的损失远大于集卡空驶带来的损失，所以经过综合分析可以得到岸桥－集卡的最佳配比为2:11。

4.2.2 岸桥类型对结果的影响

为了说明双 40英尺岸桥与常规岸桥在工作效率上的差异，将上述案例通过常规岸桥进行操作，将任务组的2个任务进行拆分，一前一后分别等待操作，利用改进遗传算法得到如下结果，求解结果见表5。

表5 不同数量集卡配比的岸桥工作时间Table 5 Dual 40’ quay crane working time based on different number of cards s

为了更形象地揭示双 40英尺岸桥与常规岸桥工作效率的对比情况，可以对二者的差值进行定量分析，在此引入了一个比值关系：

γ=(常规岸桥最早完工时间-双 40英尺岸桥最早完工时间)/常规岸桥最早完工时间。

上述公式表示的是在同等条件下，双 40英尺岸桥与常规岸桥相比，工作效率提升的程度。当 γ为正时，说明双 40英尺岸桥的工作效率高于常规岸桥，值越大则说明双 40英尺岸桥作用越明显。根据表5，可以计算得出不同集卡数量下的γ值，见表6。

表6 不同数量集卡下的γ值Table 6 γ value under different number of cards

根据表6中的比值数据，可以看出双40英尺岸桥对于提升港口装卸效率的贡献。双 40英尺岸桥的作业效率始终高于常规岸桥的作业效率。当集卡的数目为11时，γ=0.46接近于0.5，说明在港口资源配置合理的情况下，双 40英尺岸桥可将工作效率提升至接近极限值。

5 结论

1) 实验结果证明了与多级目标优化的启发式算法相比，遗传算法在求解双 40英尺岸桥的集卡调度问题有最优方案。

2) 在集卡合理配置的情况下，与常规岸桥相比，双40英尺岸桥的作业效率可提高近50%。

[1] 包起帆, 金茂海. 双 40英尺集装箱桥吊的实践与探索[J]. 港口科技, 2008, 19(2): 53-55.BAO Qifan, JIN Maohai. The practice of and probing on the double 40′ container bridge crane[J]. Science &Technology of Ports, 2008, 19(2): 53-55.

[2] CAO Jinxin, SHI Qixin, Lee D H. Integrated quay crane and yard truck schedule problem in container terminals[J].Tsinghua Science & Technology, 2010, 15(4): 467-474.

[3] 尚晶, 徐长生. 基于强化学习的集装箱码头卡车调度策略研究[J]. 武汉理工大学学报, 2011, 33(3): 72-76.SHANG Jing, XU Changsheng. Vehicle scheduling in container terminal based on reinforcement learning[J].Journal of Wuhan University of Technology, 2011, 33(3):72-76.

[4] 计明军, 靳志宏. 集装箱码头集卡和岸桥协调调度优化[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]. Journal of Fudan University (Natural Science), 2007, 46(4): 476-480.

[5] Lee D H, CAO Jinxin, SHI Qixin, et al. A heuristic algorithm for yard truck scheduling and storage allocation problems[J]. Transportation Research Part E, 2009, 45(5):810-820.

[6] 秦天保, 彭嘉瑶, 沙梅. 基于约束规划的岸桥与集卡集成调度[J]. 计算机工程, 2014, 40(5): 196-202.QIN Tianbao, PENG Jiayao, SHA Mei. Integrated quay crane and yard truck scheduling based on constraint programming[J]. Computer Engineering, 2014, 40(5):196-202.

[7] TANG Lixin, ZHAO Jiao, LIU Jiyin. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research,2014, 236(3): 978-990.

[8] 乐美龙, 赵彦营, 刘秀玲. 时间窗下单船岸桥调度-基于数学规划和规则的启发式算法[J]. 计算机工程与应用, 2014, 50(9): 242-248.LE Meilong, ZHAO Yanying, LIU Xiuling.Shore-mounted gantry crane scheduling for single vessel under time window-using mathematical programming and rule heuristic algorithm[J]. Computer Engineering and Applications, 2014, 50(9): 242-248.

[9] 钱继锋, 朱晓宁, 谢霞. “岸桥—集卡—堆场”双向作业协同模型[J]. 交通运输系统工程与信息, 2014, 14(2):138-143.QIAN Jifeng, ZHU Xiaoning, XIE Xia.“Quays, Trailers and Yard” two way operations plan coordinated model[J].Transportation Systems Engineering and Information,2014, 14(2): 138-143.

[10] Kaveshgar N, Huynh N. Integrated quay crane and yard truck scheduling for unloading inbound containers[J].Production Economics, 2015, 159(1): 168-177.

[11] Homayouni S M, Tang S H, Motlagh O. A genetic algorithm for optimization of integrated scheduling of cranes, vehicles, and storage platforms at automated container terminals[J]. Journal of Computational and Applied Mathematics, 2014, 270(1): 545-555.

[12] 康志敏, 吴洪明. 港口集装箱码头集卡优化调度研究[J]. 物流工程与管理, 2011, 33(2): 59-61.KANG Zhimin, WU Hongming. Research on optimized scheduling for container truck at port container wharfs[J].Storage Transportation ＆ Preservation of Commodities,2011, 33(2): 59-61.

[13] 韩晓龙, 牟少莉. 基于CHC 算法的集卡与岸桥协调调度优化问题[J]. 武汉理工大学学报(信息与管理工程版), 2014, 36(2): 233-236.HAN Xiaolong, MOU Shaoli. Integrated quay crane and yard truck scheduling based on CHC algorithm[J].Journal of Wuhan University of Technology (Information& Management Engineering), 2014, 36(2): 233-236.

[14] 李尤丰, 李勤丰, 刘玉霞, 等. 一种新的集卡动态调度模型及算法[J]. 南京师范大学学报(自然科学版), 2014,37(1): 104-111.LI Youfeng, LI Qinfeng, LIU Yuxia, et al. Dynamic dispatch model of container trucks based on hybrid genetic algorithm[J]. Journal of Nanjing Normal University (Natural Science Edition), 2014, 37(1): 104-111.

[15] 尚晶. 面向双40英尺岸桥的码头集卡调度模型与算法[J]. 华中科技大学学报(自然科学版), 2011, 38(11):84-87.SHANG Jing. Vehicle routing model and algorithm for twin 40 ft quay cranes in container terminals[J]. Journal of Huazhong University of Science and Technology(Nature Science), 2011, 38(11): 84-87.