基于遗传算法的自动化集装箱码头多载AGV调度

霍凯歌++胡志华

摘要：

为提升自动化集装箱码头的作业效率，减轻码头吞吐量增大带来的交通问题，降低自动化导引小车

（Automated Guided Vehicle， AGV）

的空载率，在自动化集装箱码头应用可以同时搬运不止一个集装箱的多载AGV，建立多载AGV调度问题的混合整数线性规划（MixedInteger Linear Programming， MILP）模型，应用遗传算法进行求解.借助算例，对比遗传算法与MILP算法的求解效果，分析交叉概率和变异概率对遗传算法的影响，比较多载AGV与单载AGV的作业时间，验证遗传算法的可靠性.该方法表明，遗传算法不仅求解效率高，而且对MILP算法不适用的大、中型多载AGV调度问题，也能给出值得信赖的近似最优解.

关键词：

自动化集装箱码头； 多载自动化引导小车（AGV）； 混合整数线性规划（MILP）； 遗传算法

中图分类号： U691.3

文献标志码： A

0引言

随着经济全球化进程的加快，集装箱码头得到了迅猛发展.为提高码头作业效率和增大效益，自动化技术开始被引进.上海自贸区政策的出台，标志着上海国际航运中心建设转入以现代航运服务业发展为重心的新阶段.2013—2015年出台的

《关于落实〈中国（上海）自由贸易试验区总体方案〉加快推进上海国际航运中心建设的实施意见》《关于金融支持中国（上海）自由贸易试验区建设的意见》和《全国海洋经济发展十二五规划》极大地推动了航运业的发展，使得越来越多的目光聚焦到航运业发展上来.作为集装箱进出口大国，中国上海洋山港、厦门港和青岛港也已经在建造属于中国的自动化集装箱码头了.

集装箱岸边与堆场之间的运输、堆场内的作业、道口进出等全过程实现自动化的集装箱码头就是自动化集装箱码头.自动化集装箱码头能够大幅度降低人工费用，提高码头的运作效率，24 h连续作业，满足船舶的大型化、高速化等需求.图1是自动化集装箱码头俯瞰图.自动化导引小车（Automated Guided Vehicle， AGV）负责岸边与堆场之间的水平运输，本文中统一采用可以同时搬运2个20英尺小箱或者1个40英尺大箱的多载AGV负责整个码头的水平运输.

图1自动化集装箱码头俯瞰图

国外关于自动化码头AGV调度的研究相对较多，但多数是关于单载AGV的.FAZLOLLAHTABAR等[1]和LUO等[2]为缩短自动化集装箱码头AGV提前到达和延迟到达的时间，提出了两阶段优化算法，并指出可以用混合整数线性规划（MixedInteger Linear Programming， MILP）算法求解小规模问题，用启发式算法求解大规模问题.HOMAYOUNI等[3]和CAI[4]等提出用遗传算法求解自动化集装箱码头岸桥、车辆和存储平台的综合优化问题，并考虑了包含不确定性的大规模规划问题的求解.GELAREH等[5]扩展了适用于AGV调度的MILP模型，并且通过引入基于拉格朗日松弛的分解策略与启发式算法，找出了高效的智能自主车（Intelligent and Autonomous Vehicle， IAV）调度策略.SKINNER等[6]提出了基于改进型遗传算法的优化策略，并用仿真方法验证了方案的有效性.HO等[7]和HAMZHEEL等[8]提出了同时求解多载AGV的负载选择和装载调度问题的多属性方法，并提出了用蚁群算法求解自动化集装箱码头的AGV调度问题的方法.PJEVCEVIC等[9]提出了一种适用于自动化集装箱码头作业环境的、基于数据包络分析的、高效的集装箱处理策略.AZIMI等[10]和ANGELOUDIS等[11]用仿真方法找出了多载AGV的最优调度策略，提出了适用于AGV实时控制的调度方法.

国内关于集装箱码头水平运输系统的研究主要还集中在集卡上，很少有关于AGV的研究.赵悦琼等[12]提出了改变调度计划中的集卡配备数量，计算卸载船舶停留和集卡使用的最小总成本的数学模型，同时引入了蒙特卡洛算法和穷举法进行仿真.杨华龙等[13]建立了以最小化船舶在港时间和最大化岸桥利用率为目标的模型，并针对该模型设计了挤压算法，将泊位岸桥联合调度看作二维装箱问题求解.严伟等[14]利用聚类分析方法，给出了集装箱码头出口箱的堆存策略.郑见粹等[15]介绍了自动化集装箱码头装卸工艺系统的发展、工作过程及应用情况，对不同类型的自动化集装箱码头装卸工艺系统方案的技术特点进行了全面的分析.马再洲等[16]提出了适用于自动化集装箱码头的集中式调度算法，并用案例验证了算法的可行性和有效性.

提高自动化集装箱码头的工作效率，可以从提高岸桥的工作效率、龙门吊的工作效率和水平运输AGV的工作效率等3个方面入手，但是伴随着自动化水平的提高，龙门吊和岸桥的工作效率得到了不断提升，水平运输系统随之成为了自动化码头的瓶颈.因此，本文从提高水平运输系统的效率入手，以自动化集装箱码头同时运输不同尺寸集装箱为背景，建立多载AGV的调度模型，并提出用遗传算法求解多载AGV调度问题的求解策略，最后用真实案例验证多载AGV的优越性.

1问题描述

AGV是自动化集装箱码头的水平运输工具，一般分为装载20英尺集装箱的小型AGV和装载40英尺集装箱的大型AGV两种.在多数自动化集装箱码头，为满足运输工具对运输任务的普适性，同时降低路径规划的复杂性，普遍采用统一规格的大型AGV单载完成所有的运输任务.不难发现，在运输20英尺集装箱时，AGV有一半的容量未被充分利用，而且随着码头吞吐量的增大，投入运输的AGV越来越多，这不仅产生了巨大的资源浪费，而且极大地增加了交通负担.因此，本文从增大AGV的运输能力，减小投入运输的AGV数量入手，提出多载AGV的调度策略.

传统情况下，可以将AGV调度问题看作m∶n的分配问题，其目标为运输时间或者运输费用最少，这很容易找出最优调度策略.但对于多载AGV的调度问题，已经超出了简单分配问题的范畴，调度中不仅需要分配运输任务给相应的AGV，而且需要安排好具体的装载和交付顺序，因为只有这样才能确保AGV的利用率尽可能高，运输时间、运输费用尽可能低，船舶停泊时间尽可能短等.

本文从单辆多载AGV的调度入手，假设各集装箱的装载顺序不受时间限制，AGV可以从任意任务的起点开始运输，其规划目标为运输时间最短.假设共有N个任务，每个任务有相应的装载点和交付点，所以可以用集合I={1，2，3，…，2N-1，2N}表示N个任务的全部装卸点.本文还引入虚拟端点2N+1和2N+2，用来表示起点和终点，于是任务点总数为2N+2，其中不同任务点可以代表相同的物理位置.现假设有3个运输任务，任务c1和c2为20英尺集装箱，任务c3为40英尺集装箱，于是多载AGV的调度方案见图2.

2模型建立

2.1符号说明

假设某自动化码头某时刻共有N个运输任务，P表示任务装载点的集合，D表示交付点的集合，I=P∪D表示装载点与交付点的总集合，并且I+=I∪{S，E}表示增加了虚拟起点和虚拟终点的任务点集合.运输任务的装载点坐标Pm，交付点坐标Dm和AGV运行速度θ已经给出，并且用Tm，n表示AGV从任务点m到任务点n的运行时间，dm表示AGV在任务点m的容量改变情况，Cm表示在任务点m完成操作后AGV容量的占用情况，C表示AGV的最大负荷能力.

如果AGV相继访问任务点m和n，则决策变量xm，n=1，否则xm，n=0；决策变量zm表示AGV在任务点m完成相应操作的时间.

2.2调度模型

以最小化最末任务完成时间f为目标，建立自动化集装箱码头多载AGV调度模型.该模型的目标函数与约束条件如下：

目标函数（1）是最小化最末任务完成时间，它服从式（2）～（16）的约束.式（2）限定最末任务完成时间不小于任何装载和交付操作的完成的时间.式（3）和（4）是对操作完成时间的限制：式（3）指出，如果xm，n=1，则zn≥zm+Tm，n恒成立，其中m，n∈I，m≠n；式（4）限定任何任务的交付时间一定不小于该任务的装载时间.式（5）限定任何运输任务的装载和交付操作一定不是孤立存在的，即一定有且仅有一个前驱和一个后继.式（6）限定任务序列中的任何操作能且只能被执行一次.式（7）和（8）限定虚拟起点有且仅有一个后继，虚拟终点有且仅有一个前驱.式（9）指出，如果AGV在任务点m完成操作后，立即去任务点n执行操作，那么在任务点n完成操作后AGV的负载Cm等于在任务点m完成操作后AGV的负载Cm加上AGV在任务点n的负载变化dn.式（10）～（12）是对AGV负载的约束.式（13）限定任意任务点m的操作不能作自己的前驱或后继，任何操作不能在虚拟开始前开始，任何任务不能在虚拟结束后开始.式（14）给出最小化最终完成时间f，任意操作的完成时间zm和从任务点m到任务点n的时间间隔Tm，n的下界.式（15）限定决策变量xm，n为01变量.式（16）给出了无穷大量M1的取值.

3遗传算法

VRP问题是数学上的组合优化问题，Golden等证明了该问题是NP难问题，随着问题规模的扩大，计算复杂度将呈指数增长，因此不妨用遗传算法来求解VRP问题的近似最优解.

3.1编码与解码

采用集装箱运输任务的序号进行染色体编码，用i表示第i个运输任务，则染色体序列可以表示为{1，2，3，…，N}，其中N是运输任务的数量，而且这些运输任务中既有小箱也有大箱.随机生成n个染色体的全排列，就构成了初始种群.图3就是一条长度为16的染色体.

图3染色体编码示意图

为清晰形象地表示解码的过程，给出解码示意图，见图4.图中Ci，j表示从任务i的装载点到任务j的装载点的最短运行时间，于是可以用从虚拟起点到虚拟终点的最短距离表示整个任务序列的最早完成时间.

3.2交叉

3.3变异

本文中的变异方法采用倒置变异，也就是在染色体上随机选择两个位置，然后颠倒两个位置间的基因序列，见图5.

4数学实验

4.1实验设置

将从自动化集装箱码头收集到的实验数据存放于data.xlsx中，其中多载AGV的行驶速度AGVSpeed取值5 km/h，作业点个数ODnum取值100.作业点的物理坐标存放于元胞矩阵XY中，运输任务的序号、装载点、交付点和任务大小等数据存放于元胞矩阵ODL中.

为评估算法的性能，用MATLAB编写该遗传算法，并用其求解一系列自动化码头的真实问题，并且在实验中作如下设置：设定小规模问题包含的任务量为1～15，中等规模问题包含的任务量为15～40，大规模问题包含的任务量为40～100.

4.2性能指标

实验中共引入两个性能指标：（1）最优性.小规模问题用MILP算法求出问题最优解的下界，大规模问题通过重复实验求出问题最优解的上下界.（2）计算时间.现实问题对实时性的要求较高，对计算时间有硬性要求，所以在这里把计算时间作为算法性能的另一指标.

4.3实验场景

在本文算例分析部分共做4组实验，具体场景设置见表1，其中：rc为交叉概率；rm为变异概率；ngen为遗传算法迭代次数.

4.4实验结果

实验1.根据调度模型在MATLAB中编写MILP算法，并用YALMIP工具箱中的GUROBI6.0求解器求解.容易得出：随着任务量的增大，MILP算法的计算时间呈指数增长趋势，而且当任务量大于8时，短时间内不能求出精确解.用遗传算法再次求解上述

各问题，并将两种算法求出的运输时间和所用计算

实验1分别用MILP算法与遗传算法求解该问题，并完成相应对比按照实验设置，重复实验；

限定ngen=100，Npep=50，rc=0.7，rm=0.4，rpareto=0.65

实验2设置不同的rc和rm，研究交叉概率与变异概率对实验结果的影响令rc=0.1，0.2，…，0.9，rm=0.1，0.2，…，0.9；其他设置与实验1相同；运行遗传算法，求出不同的交叉概率与变异概率组合对应的实验结果；根据实验结果，用等高线示意图法找出最优交叉概率与变异概率的组合

实验3对比单载AGV与多载AGV的运输效率令rc与rm分别等于最优交叉概率与最优变异概率，其他设置与实验1相同；求出用单载AGV完成指定运输任务的时间；求出用多载AGV完成相同运输任务的时间

实验4验证遗传算法所得结果的可靠性设置交叉概率和变异概率为最优交叉概率和最优变异概率；

重复实验，求出最短作业时间和平均误差率；平均误差率Dev=（Ni=1（（Vi-Vmin）/Vmin）/N）×100%，其中Vi是第i次实验得到的结果，Vmin表示N次实验中的最小实验结果

时间记入表2.不难发现，两种算法给出的调度方案的运输时间相差不大，但随着问题规模的扩大，遗传算法的计算时间改变很小，但是MILP算法的计算时间却飞速增长.由于自动化集装箱码头任务量通常较大，且对实时性要求较高，因此，遗传算法更适用于求解该多载AGV调度问题.

实验2.将遗传算法的交叉概率和变异概率分别取0.1，0.2，…，0.9，并将它们一一配对，生成81种不同的组合；分别将这81对交叉概率与变异概率的组合作为遗传算法的交叉概率和变异概率进行运算；为增加可信度，每组实验重复进行5次，取最优结果作为每组实验的结果.

令z（i，j）=100 000/T（i，j），其中T（i，j）为每组实验的实验结果，然后作出如图6所示的关于z的等高线示意图.利用遗传算法求出的运输时间越短，越符合码头方面的

需要，因此图6中的等高线示意图就相当于每对组合的优先性示意图.不难发现，rc=0.7，rm=0.3组合和rc=

0.7，rm=0.5组合的优越性明显高于其他组合，因为变异概率一般较小，所以该遗传算法的最优交叉概率和最优变异概率分别取rc=0.7，rm=0.3.

实验3.分别在不同任务量下进行实验，并对比单载AGV与多载AGV完成相应运输任务所需的时间，见图7和表3.显然，除了任务量为5个的情况，多载AGV都能在更短的时间内完成给定运输任务.

4.5实验总结

通过上述4组实验，容易得出：

（1）该自动化集装箱码头上的多载AGV调度问题是NP难问题.对小规模问题，可以利用YALMIP工具箱中的GUROBI求解器得出精确解，但中大规模问题已经超出精确算法的计算适用范围，只能用遗传算法等智能算法求出近似最优解.

（2）用遗传算法求出的结果与交叉概率和变异概率的赋值有关，如果交叉概率rc和变异概率rm赋值不当，调度结果的可靠性将受到影响.多次重复实验，得出该遗传算法交叉概率与变异概率的最优组合为rc=0.7，rm=0.3.

（3）通过实验3中的多载AGV与单载AGV的运输时间对比可以看出，多载AGV的效率更高，更能满足自动化集装箱码头对工作效率的要求，且在码头运作中小箱越多，越能发挥出多载AGV的作用.

（4）重复实验50次，并分析利用遗传算法求出的运输时间和平均误差率，可以得出：对小规模问题，遗传算法可以给出接近于精确解的调度方案，对于中大规模的问题，遗传算法可以给出稳定的近似最优调度方案.

5结论

为进一步提升自动化集装箱码头的作业效率，减轻码头吞吐量增大带来的交通负担，降低AGV的空载率，本文从增大AGV的运输能力，减少投入运输的AGV的数量入手，提出在自动化集装箱码头应用多载AGV的构想，并给出多载AGV调度问题的混合整数线性规划（MILP）模型.显然，该多载AGV调度问题属于NP难问题，MILP算法只能用来验证模型的正确性或求解小规模问题，对于中大规模的调度问题，需要用遗传算法等智能算法求解.进行多组实验后，得出结论：多载AGV的应用能够提升自动化集装箱码头的作业效率，减轻交通拥堵负担，且遗传算法能够快速给出可信度高的多载AGV调度方案.实际上，在自动化集装箱码头，每次参与运输的AGV数量对调度也有一定影响，而文中缺乏对该影响的考虑，因此，多载AGV的配置问题值得进一步研究.

参考文献：

[1]FAZLOLLAHTABAR H， SAIDIMEHRABAD M， BALAKRISHNAN J. Mathematical optimization for earliness /tardiness minimization in a multiple automated guided vehicle manufacturing system via integrated heuristic algorithms[J]. Robotics and Autonomous Systems， 2015， 72（C）： 131138.

[2]LUO J B， WU J. Modelling of dualcycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E： Logistics and Transportation Review， 2015， 79： 4964.

[3]HOMAYOUNI S M， TANG S H， MOTLAGH O. A genetic algorithm for optimization of integrated scheduling of cranes， vehicles， and storage platforms at automated container terminals[J]. Journal of Computational and Applied Mathematics， 2014， 270： 545556.

[4]CAI B H， HUANG S D， DISSANAYAKE G， et al. Rescheduling policies for largescale task allocation of autonomous straddle carriers under uncertainty at automated container terminals[J]. Robotics and Autonomous Systems， 2014， 62（4）： 506514.

[5]GELAREH S， MERZOUKI S， MCGINLEY K， et al. Scheduling of intelligent and autonomous vehicles under pairing/unpairing collaboration strategy in container terminals[J]. Transportation Research Part C： Emerging Technologies， 2013， 33（33）： 121.

[6]SKINNER B， YUAN S， HUANG S D， et al. Optimisation for job scheduling at automated container terminals using genetic algorithm[J]. Computers & Industrial Engineering， 2013， 64（1）： 511523.

[7]HO Y C， LIU H C， YIH Y. A multipleattribute method for concurrently solving the pickupdispatching problem and the loadselection problem of multipleload AGVs[J]. Journal of Manufacturing Systems， 2012， 31（3）： 288300.