考虑不确定性的岸桥与集卡集成调度

张 思，孙启峰

（上海大学 管理学院，上海200444）

0 引言

航运贸易的繁荣使全世界港口的集装箱吞吐量不断增长，以全世界最大的港口——上海港为例，如图1所示，集装箱吞吐量10年来一直保持稳定增长：2010年的集装箱吞吐量为2 906.9万TEU，2017年突破4 000万大关达到4 023万TEU，2019已达到4 330万TEU。预计上海港未来集装箱吞吐量仍将保持中低增长趋势，集装箱码头能力适应度问题将会日趋严峻[1-2]。

很多港口对现有的作业设备进行调度优化，以提高作业效率，缓解持续增长的集装箱吞吐量带来的作业压力。其中，岸桥与集卡的集成调度是研究的重点之一。

图1 上海港集装箱吞吐量

部分学者研究了装船与卸船作业同时进行的双向流问题。曾庆成，等[3]构建上层调度岸桥、下层优化集卡路径的双层模型以实现协调优化，并设计遗传算法求解。为协调岸桥调度与集卡路线，计明军，等[4]使用进化算法求解研究。马超，等[5]设计双层遗传算法，通过主层调度岸桥，子层基于岸桥作业来调度集卡。Chen，等[6]加入场桥调度并设计三阶段算法求解，并与其设计的禁忌搜索算法[7]相比较，证明了三阶段算法的优越性。Tang，等[8]协调岸桥与集卡以减少二者的空闲时间，设计粒子群算法求解。Behjati，等[9]考虑岸桥不交叉和船舶可变靠泊时间等因素，力求最小化船舶完工时间，并采用帝国主义竞争算法进行求解。

双向流问题的流程复杂，模型难以兼顾某些实际约束，有些学者仅研究装船作业[10]或卸船作业[11-14]，以更清楚地描述作业流程。Cao，等[10]研究最小化装船作业的完工时间，采用遗传算法和基于约翰逊规则的启发式算法求解模型。乐美龙，等[11]考虑岸桥共享集卡车队来提升集卡的利用率，使卸船过程的完工时间最小化，采用禁忌搜索算法求解。Kaveshgar，等[12]考虑了任务的优先级、岸桥间的干扰等因素，将岸桥与集卡类比为混合流水车间调度问题，设计遗传算法与贪心算法相结合求解模型。Zhen，等[13]进一步综合调度岸桥与集卡，使二者的作业时间协调最优，采用粒子群算法求解。梁承姬，等[14]对于该问题设计遗传算法求解，取得了较好的效果。

以上文献都是研究静态或确定情况下的集成调度问题，随着研究的逐步深入，动态或不确定因素下的集成调度问题将成为研究的重点[15]。港口作业的不确定性主要体现在对设备操作时间的影响上。大多数研究是以任务为视角定义操作时间，即任务不同，设备的操作时间不同，这适用于将任务定义为集装箱组的研究。张思，等[16]考虑了岸桥处理集装箱组时的操作时间具有不确定性，建立岸桥调度模型，分别设计粒子群算法与禁忌搜索算法求解。在岸桥与集卡的集成调度模型中，任务定义为单个集装箱，操作时间更多地是取决于设备的不同，而非任务。有些学者以设备为视角定义任务的操作时间，研究了岸桥与集卡集成调度中的不确定性。樊陆彬，等[17]考虑了岸桥与集卡运行参数的不确定，采用学科变量耦合优化设计的方法建立模型。Lu，等[18]考虑了集卡运行速度和岸桥操作时间这两个不确定因素，采用粒子群算法求解模型。Noura，等[19]考虑了岸桥与跨运车操作时间的不确定性，提出一种基于仿真的遗传算法生成质量控制计划。

1 问题描述及数学模型

1.1 问题描述

本文研究卸船作业的岸桥与集卡的集成调度问题：船舶到港后，岸桥将进口箱从船上卸载到集卡上，由集卡运输至指定的箱区堆存，而后集卡返回岸边运载下一个进口箱。

在理想情况下，设备的效率被认为是固定的值，且每台设备的效率相同。但在实际情况下，设备状况、天气条件、人为因素等会给设备效率带来不确定性，使其在某个取值区间内波动。若忽略这些不确定性，将会导致调度计划无法应对突发状况。本文以设备为视角定义操作时间，考虑岸桥与集卡在作业过程中受到不确定因素影响所带来的效率差异，使调度计划能够更加稳健。

1.2 模型假设

在构建模型前，本文做出如下假设：

（1）任务均为40英尺标准集装箱且信息已知；

（2）所有集卡默认选择其最佳路径完成任务；

（3）场桥资源充足，集卡在堆场无需等待。

1.3 符号说明与数学模型

1.3.1 参数与集合

s-场景集合，s={1,2,...,|s|}，场景总数为|s|；

Ps-场景s发生的概率；

Ω-任务集合，Ω={1,2,...,|Ω|}，任务总数为

ΩO-ΩO=Ω⋃{O}，O为虚拟开始任务；

ΩF-ΩF=Ω⋃{F}，F为虚拟结束任务；

Q-岸桥集合，Q={1,2,...,|Q|}，岸桥总数为||Q；

K-集卡集合，K={1,2,...,|K|}，集卡总数为||K；

M-充分大的数；

Eq-岸桥q的最早工作时间；

lq-岸桥q的初始贝位；

Li-任务i所在的贝位；在场景s下岸桥q在每个贝位的移动时间；在场景s下岸桥q卸载集装箱的时间；在场景s下集卡k的行驶速度；di-集卡由船舶到集装箱i的指定堆场的往返距离；

φ-具有优先级的任务集合，若(i,j)∈φ，则任务i先于任务j完成。

1.3.2 决策变量

Xijq-若岸桥q处理完任务i后立即处理任务j(Li≤Lj)则为1，否则为0；

xiq-若岸桥q处理任务i则为1，否则为0；

Yijk-若集卡k处理完任务i后立即处理任务j则为1，否则为0；

Zij-若岸桥在任务j的开始前完成任务i则为1，否则为0；在场景s下岸桥卸载任务i的完成时刻；在场景s下的岸边最大完工时刻。

1.3.3 数学模型

s.t.

式（1）表示最小化所有场景的岸边完工时间的加权和；式（2）和式（3）分别保证岸桥调度从虚拟任务O开始，在虚拟任务F结束；式（4）保证每个岸桥处理的任务有且仅有一个紧前任务和一个紧后任务；式（5）保证每个任务有且仅有一个岸桥处理；式（6）表示变量之间的关系；式（7）表示编号较大的岸桥处理的第一个任务的贝位号也是较大的，保证在初始阶段岸桥不会产生初始堵塞问题；式（8）-式（11）表示集卡约束，分别对应岸桥约束式（2）-式（5）；式（12）表示任务j与任务i位于同一或相邻贝位，或者有优先级要求时，不能被岸桥同时处理，必有先后顺序；式（13）表示若任务i与任务j同时被处理，则处理较大贝位号任务的岸桥的编号也较大，保证岸桥间不能跨越；式（14）表示岸桥完成第一个任务的时刻；式（15）表示岸桥完成任务i后，移动到下一个任务j的贝位，卸载该任务的完成时刻；式（16）表示待运载任务j的集卡就位后，岸桥才能完成任务j的卸载；式（17）和式（18）表示若任务i先于任务j处理，则在任务j开始前任务i已经完成；式（19）定义了在场景s下的岸边最大完工时间，此时岸桥已处理完所有任务，集卡正将最后一个任务运载到堆场；式（20）和式（21）表示变量的取值范围。

1.4 模型验证

1.4.1 验证岸桥作业模式。由于岸桥与集卡的集成调度是一个强NP-Hard问题[13]，本身求解难度很大，多场景进一步加大了求解难度。为简化问题，本文在定义变量Xijq时设定Li≤Lj，将岸桥设定为沿贝位编号由小到大方向进行单向移动的作业模式。

一方面，岸桥单向移动的作业模式操作简单、可实现性强，而且减少了双向往返时的能源消耗，因此很多港口在实际作业中广泛采用岸桥单向移动的作业模式。另一方面，本文通过CPLEX进行算例实验，对比岸桥两种作业模式的求解时间和结果，进一步验证岸桥单向移动模式的效果，见表1。

表1 岸桥的作业模式对比

实验结果表明，岸桥单向移动模式的求解时间一直少于双向移动模式，在求解2个岸桥和4辆集卡处理14个任务的算例时，双向移动模式已达到1 239s，单向移动模式仅为3.5s。加入多场景后，岸桥双向移动模式的求解难度会呈指数暴涨，将不具备求解的可行性。在求解质量方面，岸桥单向移动模式最优值与双向移动模式最优值的平均gap为0.30%，说明将岸桥的作业模式设定为单向移动，在简化求解难度的同时，并未影响求解质量。

1.4.2 验证模型的正确性。在进行数据实验前，本文需要通过简单算例对模型的正确性进行验证，数据见表2，最优调度方案如图2所示。

表2 模型验证算例数据

图2 显示：在场景1中，岸桥1依次处理任务1→2→4，岸桥2依次处理任务5→6→3，集卡1依次处理任务5→6→4，集卡2依次处理任务1→2→3，最优值为392；在场景2中，岸桥1依次处理任务1→5→4→6，岸桥2依次处理任务2→3，集卡1依次处理任务1→4，集卡2依次处理任务2→5→3→6，最优值为396。

图2 场景1(左)与场景2(右)最优调度方案

将场景1的最优调度方案应用到场景2中，得到的目标值为438，与原最优解差距为10.61%，表现较差，可见作业过程中的不确定性给设备带来的效率变化会影响调度计划的质量。而本文模型计算的最优值为403，与两个原最优值的差距分别为2.81%、1.77%，较好地削弱了不确定性给港口调度带来的影响。

2 求解方法

目前粒子群算法（PSO）是求解岸桥与集卡集成调度的主流方法之一[13]，禁忌搜索算法（TS）也被较多地应用于求解该问题[6,11]和岸桥调度问题[20-23]。其中，PSO易实现、收敛快，其群体优势使其具有较强的全局开发能力，但当问题规模增大时会出现维数障碍，使算法早熟收敛；TS具有较强的局部搜索能力，但难以形成有效率的寻优路线，全局搜索能力较弱，因此，通常利用其它算法为其生成一个靠近全局最优的初始解以增加搜索到全局最优的概率。

两种算法结合可以使全局搜索能力与局部搜索能力形成互补，本文设计粒子群禁忌搜索混合算法（PSO+TS），利用PSO的群体优势全局搜索，若群体最优值连续m次迭代不更新，则认为PSO早熟收敛，此时依靠TS的局部搜索能力跳出，若n次迭代内找到更优解，则返回PSO继续寻优，否则结束算法。基本框架如图3所示。

图3 禁忌粒子群混合算法

2.1 初始解设计

PSO要求随机生成初始解以保持粒子的分散性，而随机初始解的质量可能不高，高质量的初始解可以提升算法效率。本文在保证随机性的同时对初始解进行优化：

（1）通常各岸桥均分任务的方案更靠近最优解，本文将任务随机且均分给各岸桥。

（2）不同的任务需要被运输至不同的箱区，使得集卡的行驶里程不同，本文随机分配任务给集卡并保证各集卡的行驶里程均衡。

（3）使岸桥尽可能都处于工作状态的方案往往更优，考虑到岸桥之间不可跨越，本文将贝位编号小的任务分配给队尾的岸桥处理，避免由于初始堵塞造成队尾的岸桥闲置。

（4）若两个岸桥处理的任务在同一贝位内，根据同一贝位任务的优先级要求，则由队列在前的岸桥处理优先级较高的任务，避免岸桥间的干扰等待。

2.2 粒子群算法设计

PSO是一种模拟鸟群觅食行为的进化算法，通过个体与群体共享最优信息，追踪群体最优值和个体最优值来更新粒子的速度和位置，不断向最优解靠拢，使鸟群逐渐从无序到有序地趋向最优位置。基本框架如图4所示。

图4 粒子群算法

PSO的寻优规则使粒子的运动过程不趋向劣解，即劣解粒子不具有引导运动方向的作用。本文设置不计算劣解以加快运行速度，不值得计算的劣解有两种：

（1）在岸桥与集卡的作业中，集卡的数量多于岸桥数量，所以若两个岸桥的初始任务由同一集卡处理，则在初始阶段会出现岸桥等待和集卡闲置。

（2）若两个岸桥处理的任务位于同一贝位，则队列在后岸桥处理高优先级的任务会造成两个岸桥的相互等待。

当PSO的群体最优值连续多次不更新时，群体中多数粒子可能靠拢到局部最优解处，使其无力跳出，此时进入TS。

2.3 禁忌搜索算法设计

TS通过设置禁忌表模仿人类的记忆功能，记录的解在一定迭代次数内不再出现以防止迂回搜索，从而跳出局部最优。它从一个初始可行解出发，按照一定的规则进行邻域搜索。基本框架如图5所示。

图5 禁忌搜索算法

本文设置插入、适配、随机三种规则进行邻域搜索：

（1）插入。将某一岸桥的任务随机插入另一岸桥的作业序列中，集卡的插入规则同理。

（2）适配。岸桥与集卡的调度计划难以相互匹配，使调度计划质量不高，本文在邻域搜索时调度集卡以适配岸桥的调度计划，或使岸桥适配集卡。

（3）随机。随机生成一个新的方案以保持方案的多样性。

TS邻域搜索时接受劣解作为当前最优解，如此迭代难以形成有效率的寻优路线，若TS找到优于PSO群体最优值的更优解，由于优质解的稀少性，TS可能陷入劣解的盲目迭代，此时则返回PSO继续寻优。

2.4 算法交互设计

本文建立PSO与TS的联系，使两种算法进行交互。

（1）运行PSO时，将每次迭代的最优粒子记录到禁忌表中，当PSO停止时，禁忌表中记录的解为局部最优附近处的解，一定程度上避免了TS在局部最优处徘徊，增强了TS在初始阶段的局部搜索能力。

（2）PSO陷入局部最优后，最优粒子已失去引导群体寻找到更优解的能力，并且使其他粒子向其聚拢，失去多样性。所以当返回PSO时，本文将搜索到的更优解替换掉最优粒子，并将TS禁忌表中记录的解对PSO中的部分粒子进行替换，使其脱离聚集状态，增强粒子群的多样性与分散性。

（3）随着迭代次数的增大，PSO愈容易陷入局部收敛，TS也获得了优质的初始解，逐渐克服了自身的障碍。本文设置算法资源逐渐向TS倾斜：当PSO变换到TS时，将PSO的迭代停止限度逐渐赋予TS，使TS迭代更多次。

3 数据实验

本文根据历史数据，假设每台设备的效率服从均匀分布，以体现作业过程中的随机不确定性，其中，岸桥移动时间服从均匀分布U[4,6]（单位：s），岸桥卸箱时间服从均匀分布U[80,120]（单位：s），集卡行驶速度服从均匀分布U[8,12]（单位：m/s）。实验平台CPU为intel core i5 2.3Ghz，采用CPLEX 12.6.1求解，代码在Visual Studio 2013的C#中实现。

3.1 小规模算例实验

在小规模算例中，设置CPLEX与PSO+TS分别求解，通过比较来验证算法的性能，见表3。

表3 小规模算例：CPLEX与PSO+TS对比

小规模算例结果显示，同等数量的任务-岸桥-集卡的算例，随着场景数量的增加，CPLEX和PSO+TS的求解时间均迅速增加，说明多场景会增加求解难度，进一步验证了本文设定岸桥单向移动作业模式的必要性。

随着算例规模增大，CPLEX求解时迅速增加，对于规模为50个场景下2个岸桥和4辆集卡处理14个任务的算例，其求解时间已达到8 535s，而PSO+TS为299s，具有时间优势。在求解质量方面，PSO+TS几乎都能找到最优解，与CPLEX的平均gap为0.13%，可以找到满意解。

3.2 大规模算例实验

CPLEX的求解已超过2h，不再适用求解大规模算例，故采用PSO+TS分别与PSO、TS进行对比（见表4），验证算法的效果。

大规模算例结果显示，PSO的求解时间具备优势，说明趋向群体最优的运动方式可以有效提升寻优速度。但PSO与PSO+TS的平均gap为11.44%，说明算法后期粒子集中在同一区域难以跳出，造成了PSO早熟收敛。

TS与PSO+TS的平均gap为7.00%，说明其禁忌功能避免了陷入局部最优，但寻优质量尚可提高，而且TS求解时间更长，说明通过接受劣解来迭代增加了寻优时间。

表4 大规模算例：PSO+TS分别与PSO、TS对比

PSO+TS的求解质量更优，说明TS在全局寻优时未能充分地搜索全局空间，使其没有搜索到全局最优，结合PSO的群体优势后，提高了求解方案落到距离全局最优附近的概率，提升了算法的速度与求解质量。因此，将PSO与TS进行有效结合，可以较好地均衡局部搜索能力与全局搜索能力，优化求解精度。

4 结语

针对岸桥与集卡在作业过程中出现的不确定性情况，本文建立混合整数规划模型，使调度计划在发生突发状况时保持稳健性。本文将粒子群算法与禁忌搜索算法相结合，设计粒子群禁忌搜索混合算法求解模型，通过小规模算例验证了该算法的求解效率，通过大规模算例证明该算法可以有效地避免陷入局部最优，并增加了搜索到全局最优的概率。

在未来的研究中，可以研究同时装卸作业的岸桥与集卡的集成调度问题，也可以尝试将场桥调度纳入集装箱卸船作业中，研究集成岸桥、集卡、场桥的调度问题。另外，随着港口自动化程度加深，探究自动化设备在港口作业的调度问题会成为未来的重点。