自动化码头多资源协同调度优化模型与算法

初良勇， 周于佩， 姚艺飞， 许小卫

(1.集美大学 航海学院，福建 厦门 361021； 2.福建航运研究院，福建 厦门 361021； 3.大连海事大学 交通运输工程学院，辽宁 大连 116024)

自动化码头作为一个复杂的整体系统，单独研究单一或者2个子系统的协同对整个自动化码头效能的提升并不显著，也不符合自动化码头作业的实际情况，在自动化集装箱码头装卸任务的过程中，由于岸桥、自动导引车(automated guided vehicle, AGV)、场桥这3种装卸设备的工作范围是灵活可变的，集装箱在三者之间的流转分配成为了一个复杂的问题，因此越来越多的研究学者逐渐转移到对岸桥，AGV和场桥三者的协同调度研究上来。AGV作为自动化集装箱码头水平运输和连接场桥岸桥之间的重要工具，其运输时间也会对集装箱整体的装卸效率带来影响。

在3个设备资源协同调度方面，Meersmans等[1]采用以完工时间最小为目标的分支定界算法来解决自动化集装箱码头设备调度问题，这是AGV、岸桥、场桥综合调度的首次尝试；Homayouni等[2]将提出的遗传算法性能和Meersmans等提出的最优解进行比较，得出Homayouni所提出的遗传算法更接近最优解。栾晨等[3]以总运输时间最小化为目标，利用基于启发式的自适应遗传算法进行求解；Sadeghian等[4]对自动化集装箱码头装卸作业的质量控制以及装卸作业的综合调度进行了研究;Yang等[5]研究比较了滚动时域算法和基于拥堵预防规则的双层遗传算法，结果表明基于拥堵预防规则的双层遗传算法是有效的；Luo等[6]在研究装载过程中船舶停泊时间最小化的问题中，采用自适应启发式算法来进行求解。

除此之外，对于AGV的避碰问题，泰应鹏[7]通过对时间窗的排布和赋予小车优先级别来处理碰撞问题；凌忠奇[8]提出在AGV节点间发生冲突时，采用等待策略，优先级高的AGV先通过。

由此可见，在国内外对集装箱码头多资源协同调度问题的研究中，考虑岸桥、AGV和自动化轨道吊(automated rail mounted gantry crane，ARMG)等多资源的协同的研究较多，但考虑3种设备资源协同调度的同时加入对AGV行驶过程中碰撞问题的研究较少，且现有的文献都是考虑在任意时间只能通过一辆AGV来减少等待时间，忽视了多个AGV同时运行的情况。本文在研究3种设备协同调度时，考虑了多个AGV运输情况下可能会产生的路径冲突问题。通过设计3种智能优化算法的对比研究，从资源配置和调度执行2个方面给出了设备资源的协同调度方案。

1 多资源协同调度问题描述

本文将水平运输与垂直运输车道根据车道方向分别进行标记，见图1，其中i′与j′车道的方向为重载小车从岸桥驶向堆场，i′′与j′′车道表示空载小车从堆场向岸桥的行驶车道。同时引用杨雅洁等[9]的路径选择方法，创新点在于将岸桥q与箱区b之间的AGV路线上水平运输区与堆场作业区的不同车道的不同组合定义为该岸桥到该箱区的不同路径，如“Q2L→H2L→3→H1L→2→P2E→P2M→箱区2”为岸桥q到箱区b的一条路径。如果重载AGVn在冲突点H2L选择车道3，其冲突车道集合Dpnt={1，2，3}，见图2。即AGVn在t时刻行驶到冲突点的3车道时，其他小车在同一时刻选择冲突车道集合中的任意一条都会发生碰撞，不能同时经过冲突点。如果选不出避碰车道，即选择默认车道1或6，以此达到减少AGV冲突的效果。

图1 改建自动化码头AGV路径分布

图2 冲突点的路径分布

2 协同调度优化模型构建

2.1 模型假设

1)岸桥的每个小车作业时间固定；

2)ARMG作业时间固定；

3)AGV行驶状态分为重载、空载与转弯3种，每种状态下均为匀速行驶。

2.2 模型参数

2.2.1 集合

Q： 岸桥的集合，(1,2,…,q)∈Q；

C：集装箱的集合，(1,2,…,i)∈C；

V：AGVs的集合，(1,2,…,n)∈V；

B：堆场箱区的集合，(1,2,…,b)∈B；

BL：空载AGV出发的箱区集合；

BU：重载AGV到达的箱区集合；

Ckp(t):t时刻岸桥k的转运平台缓存集装箱的集合；

Dpnt：AGVn在t时刻的车道位置上的冲突车道集合；

S：冲突点集合；

L：路径集合。

2.2.2 模型参数

TQSkj：岸桥k开始处理任务集装箱j的时刻；

TAFjb：箱区b处理完任务集装箱j的时刻；

TQS2kj：岸桥k的门架小车开始处理集装箱j的时刻；

TQFkj：岸桥k将集装箱j装载到AGV的时刻；

TBLib：运送集装箱i的AGV空载离开箱区b的时刻；

TBRjl：AGV运送集装箱j的到达箱区l的时刻；

V1Dj：运送任务j的AGV作业空载阶段的等待时间；

V2Dj：运送任务j的AGV作业重载阶段的等待时间；

TASjl：集装箱j到达箱区l后场桥开始的时刻；

TAFjl：集装箱j到达箱区l后场桥结束的时刻；

ADjl：箱区l的场桥处理集装箱j中的等待时间；

QDj：岸桥处理任务集装箱j时的等待时间；

v1：空载AGV的行驶速度；

v2：重载AGV的行驶速度；

xnjr：重载AGVn运送任务集装箱j是否经过路径r；

ynjr：空载AGVn驶向任务集装箱j所在岸桥是否经过路径r；

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

a：AGV小车的车长；

e：AGV小车的车宽。

2.3 协同调度优化模型

2.3.1 目标函数

最小化所有任务的最大完工时间如式(1)所示，为全局目标函数，目的是为了使AGV空载运输过程耗时最少：

(1)

最小化每一个任务作业时间如式(2)所示，为局部目标函数：

(2)

2.3.2 决策变量

决策变量如下所示：

βkjl：岸桥k的集装箱j存放在箱区l时为1，否则为0；

γkjn：由岸桥k处理的集装箱j分配给小车n时为1，否则为0；

λsr：冲突点s与路径r有交集时为1，否则为0；

xnjr：重载AGVn运送集装箱j经过路径r时为1，否则为0；

ynjr：空载AGVn驶向集装箱j所在岸桥经过路径r时为1，否则为0；

φn′ntir：pn′t∈Dpnt时为1，否则为0。

2.3.3 约束条件

约束条件如下所示：

(3)

(4)

其中，式(3)与式(4)表示AGV连续作业。

(5)

(6)

式(5)与式(6)表示每一个任务都有唯一的作业岸桥与存放箱区。

(7)

式(7)表示每一个任务都有唯一的AGV运输。

(8)

(9)

式(8)与式(9)分别表示从岸边到箱区与箱区到岸边选择的AGV路径没有冲突点。

∀k∈Q,∀j∈C

(10)

式(10)表示岸桥前后小车多任务操作，并保证单个任务等待时间最少。

(11)

(12)

式(11)与式(12)表示AGV 2个作业阶段的等待时间。

(13)

式(13)表示AGV在岸桥任务箱作业结束之前到达任务岸桥。

(14)

式(14)表示在岸桥主小车作业结束后辅小车开始作业。

TBRjl+M·(βkjl-1)≤TASjl，

∀j∈C，∀l∈B,∀k∈Q

(15)

式(15)表示AGV在ARMG抓箱之前到达任务箱区。

∀j∈C，∀k∈Q

(16)

(17)

式(16)与式(17)分别表示岸桥与ARMG作业过程中的等待时间。

TQFkj-TQFk(j-1)≥2(TQSkj-TQSk(j-1))，

∀j∈C，k∈Q

(18)

式(18)表示连续的2个任务的时间衔接。

3 算法设计

3.1 算法思想

通过研究初良勇等[10-12]的文献，模拟退火(simulated annealing，SA)算法与粒子群优化(particle swarm optimization，PSO)算法的应用能够得到：SA算法可以混合群智能算法以提高算法性能；单一优化算法中，SA算法求解的目标函数值较遗传算法(genetic algorithm，GA)与PSO算法更优，在大规模算例中表现尤为明显；HGA-PSO(hybrid genetic algorithm-particle swarm optimization)算法求解的目标函数值与SA算法求解所得目标函数值相差较小，可混合PSO与SA算法进行实验。因此本文设计SA-PSO作为模型的求解算法，该算法在PSO算法框架下混合模拟退火思想，弥补了PSO算法在高维复杂问题中会遇到早熟收敛的缺点，提升算法的全局搜索能力，同时具备较强的收敛能力。

1)初始化种群设定。

选择合适的种群规模，将每次实验的任务数量设置为粒子群维度，设定粒子的位置边界与最大移动速度，在位置边界内随机产生种群初始位置，并在速度约束内随机产生相应的初始速度。

2)速度与位置更新公式。

采用标准粒子群算法的速度与位置更新公式：

v(2)=ω·v(1)+c1·rand·(xLocalbest-x(1))+

c2·rand·(xGbest-x(1))

(19)

x(2)=x(1)+v(2)

(20)

式中：v(1)、x(1)表示当前粒子速度与位置；v(2)、x(2)表示更新后的粒子速度与位置；xLocalbest为局部最优位置；xGbest为全局最优位置；ω为惯性权重；c1、c2为学习因子。

3)适应度函数。

以全部任务的最大完工时间为函数值设计适应度函数，计算全部任务在最优化的协调配置下的总时间消耗，便于实验结果对比。

4)退火策略。

以初始种群全局最优适应度值的2倍作为初始温度，选取适当的退火系数，根据Metropolis准则，计算当前温度下每个粒子的适配值，并做归一化处理，再找出全局最优解，通过PSO算法更新寻优，最后以适应度值绝对值的平均数的0.01倍为最终温度。

5)参数设定。

根据本文模型特点与研究问题的特点，设定种群规模N为60，维度D为任务数，粒子位置上下界xmax与xmin分别为200、-200，粒子移动最大速度vmax为400，学习因子为1.2，退火系数c为0.99。

3.2 算法步骤

本文所设计的SA-PSO算法步骤如下, 具体流程如图3所示。

图3 SA-PSO算法流程

1)初始化参数，在约束条件下随机生成初始位置x与速度v，评价适应度函数，找到全局最优位置xGbest；

2)进行交叉变异操作；

3)根据Metropolis准则，计算当前温度下每个粒子的适配值，并做归一化处理，再找出全局最优解；

4)更新位置与速度，计算适应度值，更新全局最优位置xGbest；

5)温度判断，若当前温度大于最终温度，降温处理后进行3)，否则，直接进行6)；

6)若满足终止条件，输出最优解；否则，返回2)。

4 多资源协同调度算例分析

本文中假设3台岸桥同时对一艘靠泊集装箱船进行卸货作业，8个箱区均有任务集装箱存放。为了方便求解，对任务集装箱和AGV分别进行顺序编号。实验参数来自远海自动化码头，具体数据见表1。实验所用计算机为Windows10系统，i5处理器，8 GB内存，并采用MATLAB 2016a软件运行程序。

表1 实验参数

4.1 资源配置分析

当任务数量相同时，配备AGV数量越多，最大完工时间越小，如实验1、2、3，实验12、13等；实验3、6、9、11的适应度值变化较小，对比实验13、15、17，在岸桥与AGV配比为1∶6时的实验中，当任务数量大于120时，3个算法求得的最优适应度值变化较大；以实验12为分界点，对比岸桥与AGV配比为1∶4的实验与1∶6的实验，可以发现，当任务数量大于120时，岸桥与AGV最优配比为1∶6。当任务数量小于120，岸桥与AGV配比在1∶4时，既能完成任务，也可节省成本投入，这对于自动化码头协同调度安排具有实际意义；实验18前后对比，可以看出，当任务数量达到320之后，随着任务集装箱数量增加，问题的复杂度增加，算法运行时间与码头最大完工时间都会较大程度增加，具体情况见表2。

表2 不同数量设备资源配置实验结果

4.2 算法对比分析

1)算法收敛对比分析。以实验11和实验23这2组实验的算法收敛情况为例，如图4所示，SA-PSO算法都表现出最优的收敛结果。SA-PSO算法在两组实验中表现在10代、70代左右收敛，在收敛效率方面只有实验11优于PSO与AGPSO算法，表明SA-PSO算法收敛结果较优，其综合收敛能力优于其他算法，但是其收敛效率稳定性有待提升。

图4 算法收敛对比

2)算法表现与运行时间对比分析。每组实验中PSO、AGPSO与SA-PSO算法求得最优适应度值为模型目标函数值，整合23组实验数据得到算法表现分析图5；对比3个算法在每组实验中的运行时间，绘制对比结果于图6。在最优适应度值求解能力方面，SA-PSO算法优于PSO算法与AGPSO算法，以PSO算法能力最弱，尤其在任务数量大于320的大规模实验中，SA-PSO算法优势更加明显，如图5所示；从算法运行时间上看，PSO算法与AGPSO算法的运行时间基本一致，说明AGPSO算法在提升PSO算法的运行效率方面能力较弱，而SA-PSO算法运算时间较短，提高了PSO算法运行效率，如图6所示。

图5 算法表现分析

图6 算法运行时间对比

4.3 算法任务调度求解对比分析

以实验15为例，如图7所示，SA-PSO算法求解得到的作业时间在2 500 s左右，比其他2个算法求解结果少300 s左右；PSO与AGPSO算法求解的任务调度总时间决定于最后单任务作业时间，整体任务调度安排没有SA-PSO算法结果集中；SA-PSO算法整体任务调度安排集中，说明作业衔接表现较好。综上所述，可以得到结论：SA-PSO在求解任务调度效率方面明显优于PSO与AGPSO算法，同时，其整体任务调度安排分配集中，任务作业衔接表现优异，设备等待时间较少，算法求解得到的任务调度合理性明显优于其他算法。

图7 算法求得的最佳任务调度时间甘特图(实验15)

4.4 实验结论

1)任务调度安排的合理分配方式。当任务数量相同时，在岸桥、AGV与堆场箱区具有最佳合理配置以内，配备AGV数量越多，最大完工时间越小；在岸桥与任务数量相同的情况下，AGV与箱区数量配比大的作业效率高；在AGV与箱区数量配比适当的情况下，合理配备岸桥数量对于提升码头作业效率影响较大。

2)本文设计的SA-PSO算法性能综合表现优异。主要体现在SA-PSO算法具有较强的适应度求解能力，运行时间快、运行效率高，综合收敛能力强；在求解任务调度效率方面整体任务调度安排分配集中，任务作业衔接表现优异，设备等待时间较少。

5 结论

1)本文创新性地考虑了AGV路径的选择、3种设备资源的协同调度问题，得出了从资源配置和调度执行2个方面进行设备资源配置的协同调度方案。

2)本文设计的混合整数规划模型和模拟退火粒子群算法可以更好地适用于解决自动化集装箱码头设备资源协同调度优化问题。

本文的分析结果为自动化集装箱码头多资源调度的实践提供方法参考。未来可以对不确定环境下的多设备资源协同调度优化问题进行进一步的研究。