干扰约束下考虑分组作业面的岸桥AGV联合调度

梁承姬，申 哲，张 悦

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

1 引言

近年来，伴随着全球贸易的进行，集装箱货运量也在不断的增长。如今，自动化集装箱码头已经逐渐成为未来码头的一大发展趋势，岸桥和AGV 作为自动化码头的重要设备，存在一些固有的干扰约束，易对设备的作业和调度产生限制或负面影响。岸桥依靠轨道进行移动，无法跨越作业，且为了作业安全，相邻的岸桥之间还存在安全距离的约束；AGV有规定的、固定的行进路线，在多个AGV 共同运作情况下易出现堵塞干扰现象。因此，在干扰约束下，如何对岸桥和AGV进行合理的调度显得尤为重要。

岸桥调度问题（QCSP）是在已知船舶岸桥服务数量的前提下，为了达成船舶在港时间最短的目标，在满足相关的约束情况下，对岸桥的任务作业顺序进行优化。针对这一问题，Kasm等[1]在考虑单一船舶不可交叉和安全距离约束下，提出了一个新的精确且计算快速算法来解决岸桥调度问题。Liang 等[2]从岸桥的任务调度和数量配置两个方面研究岸桥调度问题，通过分析两个问题之间的关系，建立两者之间的耦合关系并设计了一种循环迭代法来求解耦合模型。Si等[3]以最小化最大完工时间为目标研究了泊位分配问题和岸桥分配问题，并将泊位时间、岸桥、泊位变为矩形评价块，将整个问题转化为新的三维矩形模型并与传统建模方法和算法进行了比较。范志强[4]考虑到岸桥实际作业范围的约束，无法全岸线移动，结合岸桥其他特有约束，构建新的混合整数规划模型，并设计算法来提高调度效率。张皓博[5]分析了岸桥作业与堆场任务均衡之间的关系，建立双目标混合整数规划模型，在最小化船舶在港时间的前提下，减少作业的不均衡量。Bierwirth 等[6]考虑了泊位分配，岸桥调度的综合方法的模型的特征对文献进行分类。确定了该领域的趋势，讨论并评估了模型和算法的优劣。

AGV 是自动化码头的另一重要设备，它将岸线与堆场连接起来，负责集装箱的运输工作，良好的AGV调度与路径优化能够有效减少运输时间和成本。目前，码头多采用全岸线作业面调度模式，AGV 空闲就能被调用。在这一方面，吕品等[7]在总结大量集卡调度研究的基础上，采用作业面调度模式建立同时对两条船舶进行装卸作业的集卡路径优化模型，验证这一模式能够有效提高集卡工作效率。王军等[8]为了避免集卡大量的空载导致资源浪费效率低下，考虑了集卡运输路径中各部分的工作时间，建立作业面模式下的集卡动态调度模型，规划最优运输路径，提高装卸效率。仲美稣等[9]结合道路交通理论，为避免大量的AGV 在码头行驶时产生交叉堵塞，提出交通虚拟环岛策略，并设计仿真模型证明其优化能力。丁荣涛[10]引入基于时间窗的冲突反馈机制，设计基于能力约束判断的资源协作模型，解决吊装作业溢出问题。为避免局部收敛，模型应用了改进的量子遗传进化算法进行求解。

关于设备的协调调度，近年来也有一些研究。Tang等[11]就集装箱码头岸桥和集卡的联合调度问题，对于仅有进口箱的单向流动问题，集卡在不运行出口箱的情况下返回码头，以最小化完工时间为目标制定混合整数规划模型。然后开发了一种改进的粒子群优化算法（PSO）来解决这个问题。Vahdani等[12]整合了岸桥分配与内集卡共享，通过将内集卡分享到不同的码头岸线，来实现码头工作量与内集卡之间的平衡，建立双目标模型，在最小化运营成本的前提下，降低码头最大溢出工作量。He等[13]讨论了集成岸桥调度，集卡调度和场桥调度的问题。建立混合整数规划模型，并开发了一种基于仿真的集成优化方法来解决该问题。Chen 等[14]提出了一个考虑堆场、集卡、场桥的整数规划模型。目标是最小化所有卸载操作已完成且所有容器已堆叠在存储块中的时间。并开发了局部序列切割（LSC）方法来解决该问题。Narges等[15]开发了一种混合整数规划模型，用于联合调度岸桥和集卡。并开发了遗传算法与贪婪算法相结合的算法来解决这一问题。

从上述的研究中不难发现，AGV 调度基本采用全岸线作业面或作业线的模式。作业线模式空载率高，效率低下，全岸线作业面模式下AGV 会出现更多的交叉堵塞。而在联合调度中则主要针对岸桥进行忽略AGV的优化。为此，本文将从岸桥与AGV 协调调度角度出发，动态调度岸桥。针对岸桥任务变化，本文提出分组作业面这一新的调度模式对AGV 进行调度，以达到全岸线多设备的快速联动，从而得到最佳的岸桥AGV 联合调度方案。

2 问题描述

岸桥和AGV是自动化集装箱码头海侧作业的重要设备。传统的作业模式中岸桥的服务遵循单船服务，即岸桥在结束当前船只所有任务后，根据调度计划的指示为下一艘船只服务或者进入闲置等待状态。这一调度模式下，岸桥的作业能力会因船只任务量的不均衡被限制。AGV则是遵循全岸线作业面调度。在码头整个岸线长度范围内，目标箱出现时就调度空闲AGV，不考虑两者之间的距离问题。相较于AGV只服务于一个岸桥的作业线调度，作业面调度减少了大量的AGV 空载时间，提高了AGV的运输效率。但是由于AGV是固定路线工作，全岸线长度范围、多AGV的调度易造成行进路线上更多的堵塞等待现象。

针对上述问题，本文从整体出发，以贝位为基础将集装箱码头岸线划分为若干个长度相同的单位。船舶入港后岸桥按照船舶占据的贝位进行工作（不足一个贝位的按照一个贝位计算）。对岸桥和AGV 进行联合调度，改进两种设备的作业方式并通过岸桥作业时刻表将两者联系起来。

岸桥调度方面，对岸桥进行动态调度。岸桥可以根据船舶任务量在执行完当前任务中途停止作业并更换作业船舶，使岸桥作业量趋近平衡，提高整体作业效率，减少岸桥最大完工时间。

AGV 调度方面，本文提出一种分组作业面的调度形式。将全岸线分为多个小的作业面，并划分AGV 所属的作业面。AGV在这个小的作业面中依旧遵循作业面作业的规则，即空闲就调用，但AGV的移动范围仅限于该作业面。这一新的调度模式，旨在尽可能减少AGV 路径交叉堵塞时间与长距离跑动次数的前提下，最小化AGV的最大作业时间。具体形式如图1所示。

图1 分组作业面示意图

3 模型建立

本文研究岸桥与AGV 的联合调度问题。首先，以贝位为单位将岸线划分若干个区域。其次，在船舶靠泊位置，时间和集装箱量已知的情况下，对码头岸桥进行动态调度。最后，依据岸线长度将AGV 作业面分组划分为多个小作业面，再根据岸桥调度计划表对AGV 进行作业面调度。

3.1 模型假设

（1）岸桥在同一轨道上行进作业，不可交叉，即不可跨越作业；

（2）相邻的两个岸桥之间存在安全距离，安全距离为G；

（3）岸桥移动速度恒定，作业效率相同；

（4）岸桥初始作业时刻已知，初始位置已知；

（5）一个岸桥同一时刻只能处理一个任务，一个任务只能由一个岸桥完成；

（6）AGV只能在规定的范围内进行作业，即不可跨作业面作业；

（7）任务出现时，分派给作业面内空闲AGV；

（8）AGV移动速度恒定；

（9）一个AGV同一时刻只能处理一个集装箱，一个集装箱只能由一个AGV完成；

（10）只考虑卸船作业；

（11）不考虑突发情况。

3.2 符号说明

（1）参数定义

B：表示贝位集合，编号为{1…i,j},i,j∈B；

Q：表示岸桥集合，编号为{1…k},k∈Q；

U：表示AGV集合，编号为 {1…u},u∈U；

S：表示堆存区块集合，编号为{1…s},s∈S；

C：表示集装箱集合，编号从左到右依次为{1…m,n},m,n∈C；

Pi：岸桥处理任务贝位i的任务时间；

Rm：表示集装箱m对应的堆存区块，Rm∈S；

li：表示贝位i有岸桥任务需要处理；

：表示岸桥k的初始位置；

：表示岸桥k完成分配任务后的终止贝位；

：表示AGVu从初始位置到集装箱m位置的距离；

：表示AGVu完成分配任务后从堆存区块s到终止位置的距离；

：表示集装箱m从自身所在贝位到堆存区块Rm的距离；

λ：表示岸桥单位移动时间，即移动一个贝位所需时间；

：表示岸桥k从初始贝位移动到第一个任务贝位i的时间；

：表示岸桥k从最后任务贝位移动到终止位置的时间，理论上应该为0；

G：表示相邻岸桥k与k+1 之间的安全距离，通常为1个贝位；

v：表示AGV单位移动时间；

：表示AGVu从初始位置到做第一个集装箱m的时间；

：表示AGVu做完最后一个集装箱m移动到终止位置的时间；

Xk：表示岸桥k的完工时间；

Zu：表示AGVu的完工时间；

Di：表示贝位i的完工时间；

θm：表示集装箱m的完工时间；

W：表示岸桥处理任务的最大完工时间；

L：表示AGV的总等待时间；

H：表示AGV处理集装箱的最大完工时间；

M：表示一个足够大的数；

α1：表示任务最大完工时间的权重；

α2：表示AGV总等待时间的权重；

α3：表示AGV最大完工时间的权重。

（2）决策变量定义

xik：若岸桥k分配给贝位i则为1，否则为0；

：若岸桥k执行完任务贝位i后执行任务贝位j则为1，否则为0；

：若岸桥k在t时刻时分配给贝位i则为1，否则为0；

yij：若任务贝位i的完成时间早于任务贝位j的开始时间则为1，否则为0；

zmu：若AGVu分配给集装箱m则为1，否则为0；

：若AGVu运输完集装箱m后运输集装箱n则为1，否则为0；

qmu：若AGVu和集装箱m在同一作业面则为1，否则为0。

3.3 目标函数与约束条件

集装箱码头作业需要各设备之间相互协调，在初始的联合调度方案中需要进行多设备的调整，本文对各个目标设置相应的权重进行计算。

约束条件为：

式（1）表示最小化岸桥最大完工时间和AGV 完工时间以及AGV等待时间；式（2）表示岸桥任务的最大完工时间为W；式（3）表示AGV 的总等待时间L；式（4）表示AGV 的最大完工时间为H；式（5）表示单个任务只能由一台岸桥完成；式（6）和式（7）分别说明每个岸桥的初始任务和最终任务有且只有一个；式（8）表示单个集装箱只能由一个AGV运输；式（9）和式（10）分别说明每个AGV的初始任务集装箱和最终任务集装箱有且只有一个；式（11）表示AGV 只能运输它作业面内的集装箱；式（12）表示两设备的作业顺序，集装箱岸桥完工时间小于AGV 开始作业时间；式（13）定义了任务的优先级，即任务i要先于任务j处理；式（14）表示任务j的完成时间，不小于紧前任务i的完成时间、任务j的处理时间以及岸桥在i,j贝位的移动时间之和；式（15）说明由于冲突的存在，部分任务无法同时处理；式（16）定义了岸桥作业时不能产生干涉；式（17）表示岸桥的初始任务完成时间，不小于岸桥从初始位置移动到任务贝位的时间与初始任务的处理时间之和；式（18）表示岸桥的最终完成时间等于最终任务的完成时间加上从该位置移动到最终位置的时间；式（19）表示集装箱n的完成时间，不小于集装箱m的完成时间与从集装箱m出发处理n的时间之和；式（20）表示AGV 的初始任务完成时间大于AGV从初始位置移动到集装箱位置的时间与运输时间的总和；式（21）表示AGV 的最终完成时间等于最终集装箱的完成时间加上从该位置移动到最终位置的时间；式（22）与式（23）定义了xik和的关系；式（24）与式（25）定义了zmu和的关系；式（26）确定岸桥在依次作业过程中，相邻岸桥间保持G个贝位的安全距离；式（27）说明了三个权重之间的关系；式（28）和式（29）确保了决策变量为0-1变量以及模型中的变量均大于0。

4 算法设计

上述模型中的联合调度问题是一个NP-hard 问题，问题规模愈大，计算的复杂程度就成倍地增长。遗传算法由于其通用性，鲁棒性强，能进行广泛的并行处理等特点，在求解此类NP-hard 问题上有较为明显的优势。由于本文将对岸桥和AGV 进行联合调度，因此将设计改进的遗传算法对问题进行求解。

4.1 染色体编码

本文岸桥部分采用矩阵式编码，染色体第一行代表每个贝位的任务各自分配给的岸桥；第二行开始则代表每个贝位集装箱的作业顺序，染色体长度与贝位最大集装箱量相等。这其中第一行每一列代表一个贝位直至贝位分配完毕，0代表该贝位无任务，不需要分配岸桥或者超出贝位上限不予处理；第二行开始，每一行的非零数总和分别和各个贝位的集装箱量相等。图2为有3个岸桥，10 个贝位的染色体编码，其中第一行为AGV 调度，第二行为第一个贝位任务顺序，后续贝位与该贝位规则相同。

图2 岸桥染色体示例

本文AGV 部分染色体采用分段式编码。如图3 所示，黄色部分为第一段，表示按照贝位将全岸线分成多个作业面，数字为作业面右边界，即1到4贝位为第一个作业面，5 到10 贝位为第二个作业面；蓝色部分为第二段，表示每一个AGV 所属的作业面，小数点前为AGV编号，小数点后为该AGV所属作业面；橙色部分为第三段，表示每个集装箱分配的AGV，每个贝位以0隔开，小数点前为集装箱编号，小数点后为AGV编号。

图3 AGV染色体示例

4.2 适应度函数设置

4.2.1 岸桥干扰约束

通过GA中的目标函数确定每个岸桥的初始位置，每个集装箱的岸桥作业起始和结束时间以及每个岸桥工作的位置，并存储在矩阵数据结构中。每次岸桥需要开始处理与岸桥当前贝位不同的贝位的新任务时，它将检查相邻贝位（在新任务贝位的左侧和右侧）的任务是否有其他岸桥占用。如果因为不同岸桥执行任务干扰其移动，则检查这些任务的完成时间。如果这些任务没有完成，那么目前的岸桥需要等待；否则，它可以继续移动到下一个任务的贝位并开始卸载或装载作业。

根据岸桥的当前贝位，下一步将要执行的任务的贝位和其他岸桥的当前所在贝位，按照干扰情况的不同可将岸桥状态分为以下四种：

（1）岸桥前往其任务贝位并处理该任务。

（2）岸桥需要等待，避免与另一台岸桥发生碰撞，然后运行到其下一个任务位置。

（3）岸桥保持闲置状态，并将停留在当前位置。

（4）岸桥保持闲置状态，但需要移动以避免与相邻的岸桥发生碰撞。

4.2.2 AGV干扰约束

同样的，通过GA中的目标函数确定每个AGV的初始位置。根据岸桥任务计划表，计算每个集装箱的AGV作业起始、结束时间以及每次任务AGV移动距离，并存储在矩阵数据结构中。AGV 的约束相对简单，可将其状态分为以下四种情况：

（1）任务贝位在AGV 作业面内，AGV 前往其任务贝位并处理该任务。

（2）AGV 在处理任务中途与另外的AGV 路线交叉，堵塞等待。

（3）AGV处于空闲状态等待下一个任务。

（4）任务贝位在AGV作业面外，放弃任务保持空闲状态等待下一任务。

4.3 遗传操作

4.3.1 岸桥部分遗传操作

岸桥本文采用轮盘赌的选择策略，在尽可能保留高适应度值染色体的前提下，有效地提高种群的多样性。

因为染色体设计的特殊性，本文选取染色体基因值分类的交叉策略，具体操作如下：

对第一行岸桥分配策略在排除无任务贝位的情况下进行多点交叉；对第二行开始的集装箱作业顺序随机选择行，在排除多余的0点后，进行双点交叉，最后对其进行修复。如图4 所示，父代1 和父代2 第一行和第二行黄色的基因值为交叉操作选定的位置；列出的子代1蓝色的基因值为进行交叉并修复后的值。

图4 岸桥交叉示例

变异则是统一使用逆转变异的方式，即随机选择第i行的两个基因值，将这两个值互换位置。

如图5所示，变异前第一行和第二行黄色的基因值为选中的需变异的值，变异后蓝色的基因值为进行变异并修复后的基因值。

图5 岸桥变异示例

4.3.2 AGV部分遗传操作

AGV部分的选择操作，本文采用精英保留策略，保留高适应度值的染色体，提高算法的收敛性。对不同的保留值进行测试后，发现在保留50%时，染色体能够在保持一定的种群多样性的基础上，有效地提高算法整体的收敛性。因此本文后续实验采用50%的精英保留策略。

交叉操作，由于第二段AGV 作业面归属与第一段作业面设置关联性较大，因此本文只对第一段与第三段进行交叉操作。

第一段作业面分组规划，本文进行单点交叉；第三段AGV作业分配，本文采用多点交叉的方式，最后对其进行修复。图6 为AGV 染色体交叉示例，各颜色意义与图4类似。

图6 AGV交叉示例

变异相较于交叉操作，作用范围更小，只针对AGV作业分配进行交叉操作。变异的方式与岸桥相似，采用逆转变异法，随机选择贝位，将其染色体值的小数点部分进行交换，具体操作如图7所示，各颜色意义与图5类似。

4.4 结束规则

图7 AGV变异示例

该遗传算法以适应度值为衡量指标，对种群进行优化，当达到最大迭代次数后停止算法，输出最优解。

5 算例与结果分析

本文通过设计不同情况与规模的算例，验证本文所提出的模型与算法的可行性。算例中岸桥卸一个集装箱所需时间2 min，AGV 装卸车时间2 min，空载与满载速度恒定为24 km/h，岸线总长度2 000 m，每个贝位之间距离50 m，岸线到堆场距离600 m，相邻的岸桥之间存在1 个贝位的安全距离，AGV 与岸桥的初始位置给定，贝位数量40，卸船箱生成贝位随机，设置权重α1=0.4,α2=0.3，α3=0.3。

遗传算法的参数，岸桥部分：交叉概率0.8，变异概率0.1，种群大小50，最大迭代次数300；AGV部分：交叉概率0.9，变异概率0.15，种群大小100，最大迭代次数200。实验在 Intel®CoreTMi7 的处理器，内存 8 GB 的PC上进行，使用Matlab2018a编写实现。

通过选取12个不同规模的算例对本文的模型及算法进行验证，由于遗传算法的特性，每一个算例由算法运行10 次得到平均值，并与传统调度方法求得的解进行对比，计算出优化效果，计算公式为：

在给定集装箱数量(N1)、岸桥数量(N2)、AGV数量(N3)后，表1的计算结果表明本文提出的岸桥与AGV联合调度方案，随着算例规模的增大，优化效果先增后降。在算例1 中，本文提出的岸桥AGV 联合调度模式效果劣于传统调度。出现这种计算结果是由于在小规模算例中，集装箱任务数量较少，岸桥动态调度优势不明显并且AGV 空闲时间长，而分组作业面调度下空闲AGV无法跨作业面作业，导致AGV等待时间大于传统调度，总体效果会不如传统调度。随着算例规模的增大，岸桥动态调度和AGV 分组作业面调度的优势开始逐渐展现，到算例8 时，新式调度的优化效果达到峰值16%。当算例规模继续扩大，即集装箱数量大于200，岸桥数量大于4，AGV数量大于18时，即便将AGV作业面进行了分组划分，但同一作业面中任务数量与AGV 数量也较多，AGV堵塞等待时间会有较为显著的增加，因此联合调度方案的优化效果会有略微降低，但即便如此本文提出的协调调度相较于传统调度优化效果仍在13%以上。

表1 不同规模算例计算结果

对单设备进行对比。本文提出的岸桥动态调度方案，岸桥能够中途更换作业船只，作业均衡性相较于传统调度有显著提升，因此从表1的计算结果可以明显发现在不同规模算例中岸桥完工时间均低于传统调度方案，并且随着算例规模的不断增大，岸桥动态调度的优势也在不断地增大；另一方面，在算例规模较小的时候，由于之前提到的原因，本文提出的AGV 分组作业面作业并没有优势，但随着算例的规模增大，AGV的等待时间相较于传统调度方案有明显优势，并且长距离运输导致AGV 作业时间传统调度也会高于分组作业面，从而总完工时间高于分组作业面调度方案。

将AGV 等待时间细分为AGV 空闲等待时间与AGV堵塞等待时间进行进一步的数值分析。并将全岸线作业面调度与分组作业面调度进行计算对比，计算公式为：

作业面调度遵循空闲就调用的原则，能够极大程度地减少AGV空闲等待时间，但在实际码头操作中，这一原则会使得AGV出现超远距离运输。分组作业面调度模式就是企图在尽可能减少远距离运输现象的基础上，提高AGV 的调用频次。如表2 显示，在所有算例规模中，对比AGV空闲等待时间，全岸线作业面调度要小于分组作业面调度。这是由于全岸线调度是单个作业面的调度而分组作业面则是多个作业面，AGV 无法跨作业面远距离运输，空闲等待时间相对较长。在AGV 阻塞等待时间方面，由于AGV 在码头行进有着固定的路线，长距离运输意味着更加复杂的线路与更加多的交叉点，而多个AGV 之间更多的交叉点意味着更多的阻塞等待。因此，从表2 可以看出，随着算例规模的不断扩大，全岸线作业面调度与分组作业面调度的AGV 阻塞等待时间之间的差距也在不断增大。

然而，在集装箱数量大于75，岸桥数量大于3，AGV数量大于10 的情况下，分组作业面调度模式的总等待时间才开始低于全岸线作业面调度模式。在算例规模较小时，分组作业面调度难以体现它的优势。由于集装箱数量与AGV 数量过少，在作业过程中很少会发生阻塞等待的情况，而分组作业面限制了AGV的作业范围，增加了空闲等待时间。在多方面作用下，会产生类似算例1、2无优化效果的情况。

在算例规模较大时，集装箱任务量大，分组作业面调度中AGV 即使无法跨作业面作业，单个作业面内大量的任务也减少了AGV 空闲等待时间。同时，单个作业面内大量的任务也会增加AGV的阻塞等待时间。因此，从表2 的后三个大规模算例可以看出，两种调度模式下AGV 空闲等待时间产生趋近的现象；分组作业面调度的AGV阻塞等待时间虽然仍远小于全岸线作业面调度，但是也开始骤增。由于这些原因，分组作业面对比全岸线作业面会在算例8 时优化效果达到峰值51.9%，而在集装箱数量大于200，岸桥数量大于4，AGV数量大于18 的情况下，优化效果下降，但由于在AGV阻塞等待时间上的巨大优势，分组作业面调度模式的优化效果仍然在47%以上。

表2 AGV空闲时间与阻塞时间对比

6 结论

本文对自动化码头的岸桥与AGV联合调度问题进行了研究。考虑岸桥作业中安全距离、不可交叉等约束，AGV 作业中路径交叉堵塞等约束，以减少岸桥等待、AGV等待以及最小化岸桥和AGV最大完工时间为目标，建立混合整数规划模型，同时设计嵌套式的遗传算法进行求解。结果表明，相较于传统调度模式，在非小规模算例中，本文提出的新的联合调度方案在岸桥完工时间、AGV 完工时间和等待时间上都有较为明显的减少。在岸桥调度方面，动态调度方案由于作业均衡性的提升，相较传统方案有着明显的优势。在AGV 阻塞等待方面，很好地展示了分组作业面的优势，减少长距离运输带来的堵塞。该模型能更加有效地优化岸桥与AGV 调度问题。本文通过算例验证了研究方案，可以为岸桥AGV 的调度提供科学合理的方案和决策依据。同时，本文也存在一些不足，随着问题规模的增大，优化的效果先增后降。在大规模算例中由于单个作业面中AGV与任务数量的增加，阻塞等待时间骤增，优化效果会受到负面影响，在算例规模不断增大的情况下，本文提出的联合调度方案能否保持优化效果未进行验证。考虑到大规模算例中AGV 阻塞时间骤增的现象，在后续的研究中，将在基于优化岸桥AGV 联合调度的基础上，设计分组作业面中单个作业面AGV 数量配置优化的研究。