0

引言

集装箱堆场作业效率是影响码头前沿船舶装卸效率的重要因素之一。如何对堆场内有限的装卸作业设备进行合理调度，从而缩短船舶靠泊时间，是当前集装箱港口面临的重要研究课题。场桥和内集卡是集装箱港口堆场中负责垂直作业和水平运输的重要设备，2种设备的作业效率直接影响岸桥装卸船作业效率，为降低优化难度，目前大多学者只针对场桥或集卡单种设备的调度优化开展研究。

本文以装船作业时间最短为目标，考虑场桥间安全距离和装船任务优先顺序等现实需求，提出面向多箱区作业的场桥和内集卡联合调度方法，并针对问题特征，将遗传算法和启发式规则相结合，设计调度算法，并基于堆场实际运营过程提出算法改进操作，提升算法求解效率和求解效果。

1

协同调度方法

1.1场景描述

装船和卸船作业是集装箱港口常见的2种作业方式，二者作业过程相反。在实际作业中，与卸船作业相比，出口集装箱装船作业对场桥和内集卡联合调度效率有更高的要求，因此研究装船作业模式下的场桥和内集卡联合调度有更大的实际价值。装船作业流程见图1，集装箱船靠泊后，由场桥对提前堆放在堆场上的出口集装箱进行提箱作业，岸桥负责在海侧为集装箱船舶执行装船作业，内集卡负责在海侧与陆侧之间进行集装箱水平运输。

在装船作业过程中，港口操作人员根据出口集装箱量、出口集装箱堆存位置和船舶配载计划等，并考虑场桥和内集卡作业能力和作业规则等因素，对二者进行配置并制定联合调度作业方案，从而使总装船任务完成时间和船舶在港靠泊时间最短。为明确场桥和内集卡联合调度优化问题边界，作出3点假设：

• 待装船出口集装箱的堆存位置和装船顺序可通过堆场堆存计划和船舶配载计划获知。

• 场桥和内集卡1次仅处理1个集装箱。

• 场桥仅能在同排箱区间移动。在港口实际生产过程中，轨道式龙门吊无法在不同排箱区间进行跨箱区作业，而轮胎吊在不同排箱区间跨越时所需时间较长，严重影响堆场运营效率，因此不考虑场桥在不同排箱区间跨越的情况。

1.2两阶段调度方法设计

由于场桥移动速度慢、数量有限且作业调度过程复杂，在实际运营中场桥的配置和调度比内集卡具有更高的优先级，因此建立两阶段调度方法分别对场桥和内集卡进行调度，其中：第1阶段对场桥进行调度；第2阶段基于第1阶段所得调度结果对内集卡进行调度。

1.2.1第1阶段调度方法

第1阶段调度的作用在于优化生成合理的场桥作业序列，从而最小化不同场桥的任务量差异，从而均衡场桥作业时间，若某调度方案中存在不同场桥的任务数量差异过大的情况，则该调度方案显然非最优。基于此，提出各排箱区分配场桥数不均衡阈值Line 1和同排箱区场桥任务量不均衡阈值Line 2，以限定不同场桥之间的任务量不均衡程度。此外，在场桥调度过程中需要保证所有集装箱任务都能够被分配给场桥执行，即所有场桥所分配的作业区域包含所有待装船集装箱。同时，每排箱区所分配的场桥数之差不超过Line 1，每排箱区内各场桥任务量之差不超过Line 2。

1.2.2第2阶段调度方法

第2阶段基于第1阶段调度结果对内集卡进行调度，使总任务完成时间最短。在此过程中，应保证各箱区各时段场桥总数不超过3台，1台场桥在一个时段内不能移入和移出同一个箱区。场桥需要在集装箱堆存位置作业直到完成该集装箱提取操作，并且在此过程中内集卡应在相应任务贝位停驻直至任务结束，因此只有场桥和内集卡都到达任务位置后才开始进行提箱作业。

1.3调度算法

由于场桥和内集卡联合调度是典型的NP-hard问题，传统的混合整数规划精确式搜索算法无法满足实际装船作业调度需求，而具备较强鲁棒性和全局搜索性等特点的遗传算法在NP-hard难题求解方面得到广泛应用，因此基于遗传算法对场桥和内集卡联合调度问题进行研究。考虑遗传算法的随机性，若两阶段调度过程均采用遗传算法将大幅增加问题求解难度。因此，基于待装船出口集装箱在堆场中的位置和装船任务顺序信息，使用遗传算法生成场桥调度方案，并根据先到先服务规则生成与场桥调度方案相对应的内集卡调度方案，随后使用仿真模型对调度方案进行评估，最后通过算法迭代，对调度方案进行优化改进。算法求解流程见图2。

1.3.1染色体结构

遗传算法的目的在于生成按任务优先等级顺序排列的场桥任务编码，染色体编码共分为2个部分：场桥分配数目和场桥作业区域箱位数。染色体编码示例见图3。

以实例进行说明，在实例场景中包含2排共4个箱区和5台场桥，对应的场桥作业区域分配示意图见图4，其含义是2排箱区分别分配3台场桥和2台场桥进行集装箱装卸作业，其中：第1排箱区内的3台场桥所负责的作业区域分别包含55、75和70个箱位（图4中第1排箱区中3个不同颜色区域）；第2排箱区内的2台场桥所负责的作业区域分别包含97和103个箱位（图4中第2排箱区中2个不同颜色区域）。

1.3.2初始种群生成

初代染色体经过以下3个步骤生成：

• 步骤1：随机分配各排箱区场桥数目。以单排箱区为单位，随机分配场桥数目，并判断各排箱区场桥数之差是否超过Line 1，若超过，则需对染色体进行改进操作1，即读取各排箱区场桥分配数量，查找场桥分配数量最少的某一排箱区A和场桥分配数量最多的某一排箱区B，并分别将A的场桥数量+1，同时将B的场桥数量-1，重复进行该操作，直至不同排场桥数量差异在阈值范围内。

• 步骤2：随机分配各场桥任务区域。根据所分配场桥数，为各场桥随机分配所负责的任务区域，该区域由箱位数量表示，不同场桥所分配任务区域不发生重叠。若场桥任务量分配不均衡，则使用改进操作2，即挑选出在同一排箱区执行装卸作业的场桥，将其中任务量最少的场桥所负责箱位数+1，同时将任务量最多的场桥所负责箱位数-1，改进操作2同样可重复进行，每经过一次改进操作2，都要重新检测是否符合均衡要求，直至符合要求。

• 步骤3：任务编码排序。读取每个场桥所负责区域内的任务信息，并将任务编号按照任务等级顺序进行排列。

1.3.3内集卡调度

基于第1阶段得到的场桥调度方案，采用“先到先服务”规则生成内集卡调度方案，即当场桥需执行取箱操作时，首先判断是否有空闲内集卡：若有，则选择最先到达堆场且处于空闲状态的内集卡进行下一个装船作业任务；若无，则等待至有空闲内集卡为止。

1.3.4适应度值计算

根据场桥和集卡实际作业过程，建立时间驱动仿真模型，仿真流程见图5。首先，输入仿真环境参数，例如堆场和箱区尺寸、设备作业参数、集装箱堆存位置和任务信息等，从而生成仿真场景。其次，按照场桥和集卡的作业方案为场桥和集卡分配作业任务，过程中不断更新设备位置、装卸作业过程和集装箱信息，直到所有设备完成规定的集装箱装卸作业。最后，记录所有集装箱装卸作业完成的时间，并输出最后1个集装箱完成装船作业的时间，作为所有任务总的完成时间。

1.3.5遗传操作

遗传操作用于生成新的子代染色体。首先，从父代染色体中随机选择2条染色体。其次，按照一定概率进行染色体交叉操作，即在2条染色体中随机选择相同长度染色体片段进行交换。由于交叉操作会改变场桥的作业区域箱位数，进而影响场桥的作业量分配结果，为确保交叉操作所生成染色体仍符合均衡要求，对不符合均衡要求的染色体进行改进操作2。最后，以一定概率进行染色体变异操作，即为保证经变异操作生成的染色体符合均衡要求，须重复初始种群的生成过程。

2

实例验证

为了验证调度方法的有效性和先进性，分别在单箱区和多箱区场景下，运用本文所提出的两阶段算法对问题进行求解，同时与传统的双层遗传算法（Multi-layer Genetic Algorithm，MLGA）进行对比。MLGA的上层遗传算法用于生成场桥调度方案，其过程与本文所用遗传算法相同。MLGA的下层遗传算法用于生成集卡调度方案，其过程参考文献10所用MLGA的下层遗传算法，所生成的调度方案使用本文的适应度值计算方法进行仿真评估。算法采用MATLAB 2012b进行编译。

2.1单箱区试验

2.1.1试验设置

基于码头设备实际作业过程，设置相关仿真参数，假设场桥和岸桥装卸1个集装箱的时间分别为120 s和90 s，集卡速度为5 m/s。某箱区待装船出口集装箱堆存分布图见图6，其中灰色方格为待装船箱所在位置。所用算例中包含2台场桥、4辆内集卡和11个待装船集装箱，所有集装箱属于同一任务组，因此可以按任意顺序装船。

MLGA因随机性较强而难以在较少迭代次数内得出较优结果，因此将其迭代次数设置为50 000次，而本文算法的迭代次数设置为500次。由于该算例仅涉及单个箱区，因而此时参数Line 1失效，此处将参数Line 2分别取值1、3、5进行试验，以探究参数Line 2对算法性能的影响。

2.1.2优化结果对比

MLGA和本文算法的不同参数求解结果散点对比图见图7。MLGA所得结果离散程度强，收敛速度慢，最优解的目标值仍高于800，而本文算法所得结果明显集中程度高，因而算法收敛速度快，且结果大量集中于最优解。增大Line 2后，算法越难收敛至最优解，其原因是该算例中集装箱在箱区中均匀分布，均衡分配场桥任务即可最小化总装船作业时间，因此参数Line 2取值越小，则场桥任务量差异越小，从而缩减算法搜索时间，提升算法收敛速度。

综上可知，本文所提出的调度方法和求解算法在单箱区调度优化方面具有有效性和先进性。

MLGA和本文算法求得的最优解对比见表1，两算法所得最优解具有差异，同时总作业完成时间由MLGA的703 s减少为693 s，可见本文所提出算法能够有效提升算法优化效果。

2.2多箱区调度试验

为进一步验证调度方法在多箱区场景下的有效性和先进性，进行多箱区实例试验。

2.2.1试验设置

假设的装船作业集装箱分布场景见图8，共40个待装船出口集装箱随机分布在2排共4个箱区中。

假设共有5个集装箱装船作业任务，见表2。场桥需按照任务编号顺序进行装船作业，即每台场桥需在完成所分配区域内的任务1的集装箱装船作业后，才能开始执行任务2的集装箱装船作业，其他任务以此类推。共有5台场桥、8辆内集卡参与装船作业。为观察参数Line 1和参数Line 2对算法调度优化结果的影响，分别设置4个不同Line 1和Lin 2参数值对，即分别取[1，1]、[1，3]、[1，5]和[3，1]对算例进行求解，算法终止迭代次数均设置为500次。

2.2.2算法结果对比分析

不同参数求解结果散点图见图9。不同于单箱区试验结果，当参数Line 1和Line 2取值最小时，其最优解显然劣于参数Line 1和Line 2其他取值所得结果，其原因是该场景较为复杂，在考虑不同作业优先顺序的情况下，均衡不同场桥各时段作业量，可能出现部分场桥等待其他场桥完成优先任务的情况。增大参数Line 2取值后得到的解具有更强的多样性，因此能够得到更好的最优解。然而，可行解增加会导致算法搜索范围扩大，进而导致算法收敛速度降低，因此染色体目标值离散度最高。增大参数Line 1取值同样能够得到更多可行解。综上可知，参数Line 1和Line 2取值越小，则算法收敛速度越快，但其可行解有限，因此应适当增大参数Line 1和Line 2的取值。

3

结论

本文研究了带任务顺序约束的场桥和内集卡联合调度优化问题。首先，基于场桥和内集卡的实际作业过程，考虑场桥和内集卡作业约束、场桥作业量均衡分配等，提出不均衡阈值参数，并提出两阶段调度方法。随后，考虑调度过程的复杂性，使用遗传算法对问题进行求解，并提出2种改进操作，以提升算法求解效率，同时考虑内集卡作业过程与场桥作业过程的耦合性，使用启发式规则对内集卡进行调度。最后，通过算例验证本文所提出的调度方法和求解算法在单箱区和多箱区调度过程中均具有较强的有效性和先进性，能够提高场桥和内集卡作业效率，减少船舶在港靠泊时间。