基于遗传算法的自动化集装箱码头多载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的利用率尽可能高，运输时间、运输费用尽可能低，船舶停泊时间尽可能短等.