自动化集装箱码头装卸系统的协同调度优化*

□ 栾 晨 □ 韩笑乐

同济大学机械与能源工程学院 上海 201804

1 研究背景

自动化集装箱码头因安全性、可靠性、作业效率和场地利用效率高，环境友好，以及人力成本低等显著优点，已在世界很多港口实现应用。自动导引车（AGV）、岸边吊桥（QC）、场地吊桥（YC）作为核心装卸运输设备，三者间的协同作业效率对自动化集装箱码头的整体效率有至关重要的影响，因此关于码头装卸系统调度的研究和应用，也一直受到业界关注。在现有的文献［1-6］中，大部分研究仅针对单类或两类设备进行调度，并假设其它设备不构成瓶颈，这一假设与实际情况存在差异。另有部分研究［7-14］考虑了三类设备的集成调度，但仅设定单装单卸作业模式，不能有效提升双循环操作下的设备利用率。针对这一现状，笔者研究了三类设备的装卸混合作业模式，考虑装卸任务的并行操作、任务间顺序约束和双循环作业，通过建立数学规划模型和设计启发式算法，对三类设备的集成调度进行优化，以提高自动化集装箱码头装卸系统整体的协同作业效率。

2 问题描述

在自动化集装箱码头装卸作业过程中，将集装箱任务经过QC、AGV和YC，并运送至堆场的过程称为一个卸载过程。反之，将集装箱任务经过YC、AGV和QC，并运送至船舶的过程称为一个装载过程。由于在装卸系统中没有设置缓冲区，设备间在任务交接时可能存在互相等待。考虑到在装卸系统调度问题中QC和YC的对称性，将此两类设备统一称为Crane，以简化模型表述。对其它问题设置进行描述。

（1）作业任务。已知信息包括装卸箱的运输起始点、装载量，集装箱任务之间存在预定义顺序约束。

（2）时间参数。所有固定时间设定为常量，可变时间设置为起始点与目的点之间距离的正比，不考虑不同转运设备之间的运行速率差异。

（3）资源配置。AGV的数量和位置已知，假定QC装卸任务时间恒定，任意车道及任意QC之间通行时间已知，同一堆场或岸桥既有卸载任务的集装箱，也有装载任务的集装箱。

3 建模

N=｛0，1，...，i，j，...，n，n+1｝，为任务集合,包括了虚拟的初始和终止变量：0，n+1。

V=｛1，...，k，|V|｝，为 AGV 集合。

C=｛1，...，l，...，|C|｝，为 Crane 集合，包括 QC、YC。

Tj为AGV从任务j接货点行驶至送货点所需的时间。

Sij为AGV从任务i送货点行驶至任务j接货点所需的时间。

HP为接货的任务交接时间。

HD为送货的任务交接时间。

Dijl为Crane l上连续任务i和j的时间差，存在以下四种情况：

（1）i为接货，j为接货，为一次取箱的往返时间；

（2）i为接货，j为送货，为取箱完成后继续送箱时间，可视为0；

（3）i为送货，j为接货，为送箱并取箱往返的时间，属双循环；

（4）i为送货，j为送货，为一次送箱的往返时间。

建模时，设M为足够大的数。

模型中的决策变量如下：

sj为任务j的接货时间。

cj为任务j的送货时间。

模型中的目标函数为：

笔者所研究问题的目标是总运输时间最少化。由于任务具有连续性，因此最后一个虚拟终止任务的结束时间即为总运输时间。

模型中的约束如下：

式（2）表示每个任务只能由一台AGV完成。式（3）～式（5）表示 x、y、z、u 的关系。 式（6）～式（9）保证每台AGV先完成任务0，最后完成任务n+1。式（10）、式（11）限制每个任务前后有且只有一个任务。式（12）表示每台AGV依次连续完成各个任务。式（13）和式（14）表示任务的接货时间选取接货点处Crane和AGV可用时间中的大值。式（15）和式（16）表示任务的送货时间选取送货点处Crane和AGV可用时间中的大值。式（17）～式（23）表示 Crane的调度约束，类似于 AGV的调度约束。

4 算法设计

基于遗传算法搜索框架进行定制化算法设计。染色体编码为任务的初始执行顺序，遗传操作、适应度函数及自适应算法采用文献［15］中的方法。解码采用基于任务顺序约束与染色体编码任务序列的启发式算法：结合任务顺序约束和染色体编码任务序列运用启发式算法确定任务执行顺序，顺序确定后对QC、YC和AGV进行协同调度，逐步安排所有任务。算法整体框架如图1所示。

4.1 自适应遗传算法流程

给定初始参数，包括最大迭代步数λmax、当前迭代步数λ、群体规模n、交叉概率Pc、变异概率Pm、当前全局最优解未发生变化的代数φ、判断是否发生早熟的阈值δ。遗传迭代中第λ代群体中第k个染色体用表示，第λ代群体中的最优解称为当代最优解，算法截至第λ代得到的最优解为当前全局最优解xbest。

（2） 判断 λ 是否≤λmax，若是，转第（3）步；否则，转第（9）步。

（4）若φ＞δ，表明当前全局最优解未改进，调用重启机制。

（5）计算每个个体的适应度值，轮盘赌方式选择新的个体。

（6）计算Pc和Pm，对种群中的个体进行交叉和变异。

（7）计算每个个体新的目标值。

（8） 得到新一代种群，令 λ+1，转第（2）步。

▲图1 算法整体框架

（9） 满足终止条件，输出 xbest。

4.2 启发式算法流程

（1）执行任务生成子算法，得到当前需要执行的任务 j。

（2）计算sij。由AGV前序任务矩阵MV确定该AGV前序任务的Crane l2，计算与本任务的Crane l1的距离，由距离计算出时间。

（3）计算sj。 根据 MV、Crane前序任务矩阵 MC得出 cj，若 Crane l1前序任务为接货，则若 Crane l1前序任务为送货，则 sj=max（ci1+

（4）计算cj。若Crane l2的前序任务为接货，则cj=max若 Crane l2的前序任务为送货，则

（5）计算所有可用AGV对应的sj和cj，找出cj最小且编号靠前的AGV，作为该任务的运输车辆。

（6）执行任务并行子算法，得到修正的sj和cj，以及更新的AGV信息。

（7） 更新 MV、MC、任务开始时间矩阵 Ms、任务结束时间矩阵Me。

（8）判断是否完成全部任务，是则停止，返回最后任务的结束时间；否则，转第（1）步。

4.3 任务生成子算法

任务执行顺序编码为｛x1，x2，...，xn｝，已经安排任务数为a，预定义任务间顺序约束为Pij，记录已经安排任务的数组为P。

（1） 在｛x1，x2，．．．，xn｝中从 xs任务开始，若令，则执行任务 xs，在 P 中记录 xs，令 a+1，转第（4）步；否则，令 s+1，转第（2）步。

（2） 检测 xs是否在 P 中，如果不在，转第（1）步，否则，转第（3）步。

（3） 令 s+1，转第（2）步。

（4）若a=n，则任务顺序确定，任务选择结束；否则，令 s=1，转第（2）步。

4.4 任务并行子算法

在启发式算法第（1）～第（5）步中，安排相应的AGV完成分配的任务，但是依据Crane前序任务完成后再安排后续任务，不符合实际运作过程出现的并行操作，为此需要修正对应Crane上的任务执行顺序。当前任务j接货点处Crane上已有任务数为b，接货点处Crane 上已安排任务序列为｛w1，wi，．．．，ws｝。

（1） 若 b＞0，转第（2）步；否则，转第（6）步。

（2）从虚拟任务wi开始作为任务j=ws的前序任务，修正sj，判断任务在当前Crane l1上操作，若是接货且当前 sj＜swi+1，转第（3）步；若是送货且当前 sj＜swi+1，转第（3）步；否则，令 i+1，重复第（2）步。

（4） 若 i≤b-2，转第（2）步；否则，结束。

（5）消除当前任务已经选定的AGV信息，依据更新的sj和cj重新选择AGV。

5 试验与结果分析

基于典型码头配置，笔者设计了9组算例，每组算例计算10个实例，考虑不同的QC、YC、AGV和任务数量，具体规模分别对应为 “1-2-2-10”“1-2-4-10”“1-2-3-6-10”“1-2-2-15”“1-2-4-15”“1-2-6-15”“2-4-6-20”“2-4-8-20”“2-4-10-20”。 参数设置时，QC的新任务取送时间为180 s，YC任务的取送时间满足［180，540］均匀分布，AGV 满载和空载的速度都设为10 m/s，在接货和送货时都有任务交接时间30 s，装卸箱任务比例各为50%概率。对于预定义任务顺序约束，主要采用约束密度控制的方法［16］来生成，令优先级密度参数ρ=0.4，任务i、j间存在顺序约束的概率φij为：

上界采用第一代染色体的最优值作为对比对象，下界采用Cplex优化软件求出的调度问题精确解作为对比对象，由此能反映算法的实际效果。运行数值试验的电脑配置为中央处理器频率3.5 GHz，内存16 GB，编程语言为C#。表1中数据是9组算例的平均结果，并以TGA和TCplex分别表示遗传算法运算时间和Cplex软件运算时间。

由表1可知，在不同任务规模下，应用笔者所提出算法得到的结果相比上界有较大提升，平均改善幅度为8.4%。同时对比应用Cplex求解软件所得出的精确解，最优差距在4%之内。由此可见，笔者提出的算法能很好地安排调度任务。对于实际运作中的实时性要求，TGA相比TCplex有明显优势。

表1 试验结果

6 结论

针对自动化集装箱码头装卸系统三类设备在装卸混合模式下的协同调度问题，建立了相应的数学优化模型，并设计基于启发式的自适应遗传算法，经试验验证，笔者所提出的协同调度方法能为码头运作提供有效的调度决策支持。