自动化堆场混合堆存模式下双轨道吊协同调度策略与优化

蒋敏敏，添 玉，黄 渭，范勤勤

（1.中山大学南方学院 商学院，广东 广州 510970；2.上海海事大学 物流工程学院，上海 201306）

0 引言

目前，全球贸易处于高速发展中，世界货物进出口量也随之迅速增长，海上运输以货运成本低且运输量大的优势，在全球贸易中占据不可动摇的地位。作为联系海上运输与内陆腹地的港口正面临着集装箱激增的巨大压力，另外随着劳动力成本不断增加以及环保理念日益深入人心，必然驱使港口向自动化、智能化的方向发展。自动化集装箱码头堆场作业系统不仅是码头内外作业区域的连接枢纽，而且保障了整个码头进出货物的均衡性，其装卸工艺和设备也决定整个码头运营效率。场桥是堆场的主要装卸设备，其调度过程十分复杂，目前国内外学者对双场桥调度问题有一定研究。针对单一作业模式下双场桥调度问题，邵乾虔，等[1]考虑进口箱疏港过程中翻箱作业不能跨贝进行的现实约束，并建立动态优化模型并求解；景贞文，等[2]针对双轨道吊作业进口箱优先权分配问题，提出9条优先权分配规则以及直接避让和动态暂存区两种非优先轨道吊避让方案；范厚明，等[3]考虑场桥实际作业中的安全距离，建立混合整数规划模型，运用遗传算法求解；Gharehgozli，等[4]以场桥完成任务时间和由于被动移动和等待造成非正常作业时间为目标研究双场桥调度，建立混合整数规划模型，并运多重启发式算法求解。针对双场桥调度过程中交接问题，Zhou，等[5]提出交换点的概念，并用优化算法求解最小化延迟时间和延迟的工作数量；魏晨，等[6]考虑不可跨越式ASC 之间的空间约束，以最小化任务完成时间为目标函数建立整数规划模型并求解，减少因时空同步和干涉造成的等待；丁一，等[7]考虑接力、缓冲区、碰撞等条件约束，建立以最小化外集卡和船舶延时为目标函数的不对称的多旅行商模型，求解优化双自动化轨道吊调度；Huang，等[8]提出一种利用装载小车侧面作业的双自动化轨道吊(ARMG)在线调度方法，用非零博弈策略建立双场桥调度模型，并提出一步前瞻算法和两步前瞻算法；周娴静，等[9]通过固定存、取箱贝位研究跨越式双自动化轨道吊调度，考虑上自动化轨道吊作业同一贝位任务时避免碰撞约束，建立多目标混合整数规划模型。上述文献缺乏多场桥调度、交接贝位选择与协同策略的集成考虑，因此，本文以自动化堆场为对象，考虑混合堆存模式下对等式ARMG 工艺特性和能耗成本，提出协同调度模型和策略，优化存取顺序以及交接点决策，改善自动化堆场装卸性能。

1 问题描述

目前，自动化集装箱码头堆场布局采用垂直码头岸线为主，如荷兰Euromax 码头、巴塞罗那港口（BEST）码头以及厦门远海和上海洋山港四期，如图1所示。每个箱区两侧分别设有平行轨道，配置两台对等式ARMG，需保持一定安全距离，不能相互跨越。虽然该布置会降低装卸设备的灵活性和可靠性，但可以提高场地利用率，降低投资成本，且可进行海侧、陆侧及接力作业，提高堆场效率。箱区海侧端部配置支架系统，有效缓解耦合刚性矛盾，采取混合堆存模式，既可堆放出口箱，也可临时存储进口箱。一是提高ARMG 装卸效率，如ARMG 作业卸船箱到指定位置后，可以顺便提取附近的装船箱至支架，减少空驶时间；二是提高AGV 装卸效率；三是码头整个运作系统由水平运输、岸桥作业以及堆场作业系统组成，每个环节都相互影响，AGV和堆场装卸协同终将改善船舶装卸效率。

上述作业模式增加了系统柔性，但对装卸设备的调度提出更高要求。自动化堆场装卸效率与双对等式ARMG 的调度策略和交接贝有关，所以可视为均衡优化问题，即保持堆场稳定有序作业的同时提高整个码头的运作效率。因此，使用堆场装卸完工时刻评价双ARMG 协同程度，采用双ARMG 行驶距离评价堆场作业成本，采用海侧ARMG 完成所有装船箱的结束时刻评价码头整体作业效率。

图1 自动化集装箱码头整体布局

2 双对等式ARMG调度模型

2.1 假设条件

（1）集港在装船作业过程之前已经完成，疏港在装船作业过程之后进行；（2）假设岸桥调度结果已知，这里岸桥调度的任务以簇任务形式定义，且簇任务约束关系已知；（3）调度计划期内，已知每个箱任务的操作类型（装/卸）、在船上以及堆场的存放位置；（4）ARMG、AGV可用数量已知，且每个设备一次只处理一个集装箱；（5）ARMG、AGV 空/重载与行驶速度以及设备的装卸效率已知；（6）进出口箱允许堆存在同箱区，各箱区贝位容量充足；（7）暂不考虑翻箱作业。

2.2 符号变量说明

2.3 目标函数

（1）最小化所有ARMG中最大结束时刻：

（2）最小化ARMGa 中完成装船任务的最大结束时刻：

（3）最小化所有ARMG行驶路程：

2.4 约束条件

式（4）-式（7）表示ARMG 一次只能执行一个箱任务，且都要被执行，一旦被执行不能中断。式（8）表示一个集装箱只被分配箱区一个贝位。式（9）、式（10）表示同一个ARMG执行相邻任务的时间逻辑关系。式（11）、式（12）表示同一箱区的ARMG 任何时刻不可少于两个贝位的时间间隔且不得跨越操作。式（13）-式（15）表示箱任务在堆场存放和交接位置的要求。式（16）-式（19）表示对于同一装船箱任务的设备环节的时间逻辑关系及先后顺序要求：ARMGb-ARMGa-AGV。式（20）-式（23）表示对于同一卸船箱任务的设备环节的时间逻辑关系及先后顺序要求：AGV-ARMGa-ARMGb。式（24）、式（25）表示每一个ARMGa、ARMGb在先装后卸的情况下需分别与岸桥、ARMGa作业顺序一致。

该模型的特征在于，并未要求ARMGb的作业序列完全遵照ARMGa，而只在ARMGa先装后卸的情形下，ARMGb才须与ARMGa接力调度。增加双ARMG的工作柔性，在一定程度上能提高双ARMG 协同调度效果。此外，双ARMG 作业过程中的碰撞和跨越问题采用时间上连续性处理。

3 算法设计

3.1 调度机制

针对ARMG 的调度问题，大多文献假设ARMGb遵守ARMGa的作业序列，虽然简化了计算和执行难度，但一定程度上造成大量的空驶、等待和被迫移动，浪费设备资源。

本文提出：仅在ARMGa先后两个箱任务为先装后卸时，ARMGb 须按照ARMGa 的序列完成，其他情况下可以按照当前任务的优先程度选择，如图2 所示。交接点位置的选取，传统方案是将箱区中间贝位选作交接贝，常常出现一台ARMG任务量过重，而另一台相对空闲，箱区中间贝位拥挤，其他贝位闲置，箱区资源浪费。因此，应改变固定式接力方式，将交接点作为相对位置进行选择，实现双对等式ARMG均衡且柔性作业，如图2所示。

图2 ARMGa与ARMGb作业序列示意图

3.2 算法步骤

3.2.1 序列编码和解码与交接点决策

（1）ARMGa 操作序列。基于岸桥调度结果对所有箱任务采用自然数编码，每个染色体代表一种所有箱任务的随机排序，长度代表箱任务数量N。并按照下列启发式策略循环N-1 次操作，得到ARMGa 操作序列：

step1：从编码序列中找到第i 个卸船箱，i＜N，执行step2。

step2：判断第i个卸船箱后续的编码序列中箱任务属性，若是卸船箱，则跳过，继续寻找下一个元素，直到找到装船箱，执行step3。

Step3：判断step1 与step2 找到的两个箱任务是否属于同一艘船舶且也属于同一个箱区，若是，则一定概率将两个编码元素交换，若不是，则不作任何操作，然后执行step4。

Step4：完成该卸船箱在作业序列中的顺序调整。寻找编码中下一个卸船箱，反复执行step1-step3，直到遍历完所有卸船箱。

（2）ARMGb操作序列编码。将ARMGa的每个箱任务拆分为两个操作任务，其中一个由ARMGa自身作业，另一个则由ARMGb 完成。因此ARMGb 作业序列生成如下：

Step1：在ARMGa 编码的随机序列中，提取属于同一个箱区任务，得到对应序列。

Step2：在 Step1 上各加上每个 ARMGa 操作任务数量，得到新的自然数编码；

Step3：将Step1的结果随机排列，得到ARMGb随机操作序列；

Step4：按照类似上文ARMGa操作序列的启发式策略得到ARMGb最终操作序列。

下面用箱区1的10个箱任务为例对上述编码进行说明：-1表示卸船箱，+1表示装船箱。

表1 ARMGb编码生成

（3）交接点选择策略。交接点选择在相对贝位。这里针对箱任务所在目的贝位的中间位置。当箱任务的目的贝在箱区中间区域前端，则只由ARMGa 作业，反之则选择目的贝位与海侧的中间位置作为交接点。

3.2.2 不可行和重复序列修正。随机生成或迭代后的个体修正策略：（1）不可行序列修正：通过已知岸桥作业箱任务顺序及簇任务约束关系修正：（2）重复序列修正：搜寻每代重复个体，并采用部分逆反变异操作生成新个体替换原染色体，得到新种群作为下一代，保持了种群的多样性。

3.2.3 染色体选择交叉变异。（1）染色体选择：采用轮盘赌的方法对染色体进行选择。（2）染色体交叉：采用部分匹配交叉方法。（3）染色体变异：采用部分逆反变异方法。

3.2.4 适应值函数设置。适应值函数通常与目标函数关联。通过对所有ARMGa任务最大结束时刻、箱区作业时刻以及箱区作业成本这三个目标函数分别设置加权系数得到一个组合函数，并将这个组合函数的倒数作为适应值。

4 案例结果分析

4.1 案例说明

以青岛某自动化集装箱码头为例，整体布局和水平运输交通规则如图1 所示。岸桥装卸交换区域共7条行驶车道，堆场箱区数量为10个，每箱区共32个贝位，编号从海侧向陆侧依次递增，每个贝位宽13m，9列5层，可容纳45个集装箱。某船舶需要操作的进出口集装箱的位置及簇任务划分和约束关系可通过船舶配载计划获得。ARMGa 初始位置在1 贝位，ARMGb 初始位置在 32 贝位，L-AGV 初始位置在缓冲车道，各设备完成所有任务后须回到初始位置。

4.2 结果分析

为比较双对等式ARMG 接力模式与协同程度，设计以下四种调度组合策略，证明本文算法的优越性。分别设计4 类实验案例，每组任务规模设置为10、20、40、80、100。

策略1：接力调度+交接点固定；策略2：接力调度+交接点变化；策略3：协同调度+交接点固定；策略4：协同调度+交接点变化。

4.2.1 交接点决策分析比较。图3 显示了箱区装卸效率曲线，图4 显示箱区完成装船箱的最大结束时刻。通过比较策略4与策略3、策略2与策略1各曲线发现，交接点变化因减少双ARMG等待时间，既有利于箱区装卸效率，又提高了船舶完成装船箱效率，且随着任务规模的递增，调度方案效果更为明显。图5所示为箱区的装卸成本，策略1 与策略2 的曲线、策略3与策略4的曲线均基本重叠，表明交接点固定和相对变化对箱区装卸成本无明显差异。

综上，从效率和成本两个方面评价，箱区交接点变化更具有优势，对船公司和码头都是有利的。

图3 箱区结束任务时刻

图4 ARMGa装船任务结束时刻

图5 箱区装卸成本

4.2.2 调度策略分析比较。由图3可知，在交接点固定的情况下，相对于协同调度，接力调度时箱区结束更早。因为此时，前者ARMGb 重进重出的比例下降，增加双ARMG 空驶时间，降低了箱区的装卸效率。而图4 说明协同调度有助于船舶的装卸效率。因为双ARMG尽可能提高了岸桥装船箱相对于卸船箱的优先级。此外，图5表明不管是交接点固定还是变化，双ARMG 协同调度都会导致箱区成本上升。因为协同调度降低了箱区重进重出程度，增加被迫移动次数，导致空驶距离增加。

由此得出以下结论：一是船舶装卸效率与堆场箱区效率一定程度上存在负相关关系（前者为全局目标，后者为局部目标），即船舶装卸效率最大化，会导致堆场装卸效率下降，成本增加；二是调度策略影响装卸重进重出比例，其值越高越有助于降低堆场成本；三是交接点动态产生会减少ARMG 的无效等待时间，有利于堆场装卸效率。

5 结语

自动化集装箱堆场的协同调度有利于提高船舶的整体装卸效率。本文创新之处在于：一是考虑混堆模式下双对等式ARMG 的调度策略；二是引入空间上的交接方式因素。通过模拟实验比较各种情形的优劣，发现船舶装卸效率与堆场装卸效率和作业成本存在背反关系，其中，交接点的决策是影响堆场作业成本的重要因素。