自动化集装箱码头AGV换电管理与调度优化*

郑亚红 徐玖龙 谢 淳

(武汉理工大学交通学院 武汉 430063)

0 引 言

自动导引运输车(automated guided vehicle，AGV)纯电力驱动，采用无人驾驶技术，同集卡相比，具有节能减排、智能行驶、降低人工劳动强度等显著优势.如今设备的自动控制技术已经日趋成熟，整个码头的效率瓶颈主要集中AGV的调度优化层面.近年来国内外学者对自动化码头AGV作业的相关研究大多数仍集中在传统的调度问题，很少考虑其充电/换电过程.Vis[2]将AGV运输系统调度问题分为调度问题(dispatching problem)和调度及路径问题(dispatching and routing problem)，前者是基于作业任务对AGV进行分派并制定其作业时间表，后者同时进行调度和路径选择的决策.而大部分研究中的调度问题其实包含了路径问题，可以称之为一种广义的调度问题.目前关于这类调度问题的研究主要有两个方向：①对问题或模型的扩展，从文献[3]基于将所有的AGV分派到同一岸桥的假设的简单问题，发展到现在研究的多岸桥、考虑AGV行驶时间和岸桥作业时间延迟[4]、不同策略下的AGV自适应调度[5]、减少AGV的空载行驶以实现减排[6]等更切于实际的复杂问题，此外在决策变量类型、车辆性能、目标函数、约束条件、调度规则等方面有所区别；②对这类NP难问题的求解方法的探索，目前主要应用的方法有启发式算法、智能学习方法、神经网络学习、对混合整数规划模型的约束松弛、基于时间Petri网的建模等，还有的借鉴了FMS(柔性制造系统)中的研究方法.

AGV续航有充电和更换整体电池包(简称换电)两种不同方式，本研究基于前期对洋山四期自动化码头的调研展开，着重探讨换电这种方式.石楠路等[7]的研究，考虑了AGV的换电过程，以提高AGV作业效率为优化目标构建了AGV作业调度混合整数优化模型，并通过遗传算法求解.从研究结论看，虽然减少AGV换电排队时间，但是大大降低了AGV电池利用率，因为为了错开AGV换电时间，有的AGV在电量消耗很少的时候就前往换电站换电，从资源利用的角度看实际上产生了较大的浪费.张亚琦等[8]的研究，关注了AGV的充电过程，将AGV充电后的续航能力约束条件考虑进调度模型中，进行AGV充电与作业的联合优化.

文中在对洋山四期自动化码头的调研和国内外现有研究特别是文献[8]的基础上，结合自动化集装箱码头AGV实际生产作业流程和换电需求特性，以优化AGV换电模式为切入点进行换电管理优化，同时将AGV换电和作业进行协同，建立二者协同的调度模型，减少AGV在换电站的排队等待时间，兼顾考虑提高AGV电池利用率，最终实现提高AGV作业效率.

1 问题描述

AGV换电站及其配套设施占地面积较大，一般建设在AGV运行车道的尽头，见图1.AGV调度同传统码头中集卡调度的主要区别就是需要保证AGV的续航能力，杜绝AGV电量耗尽带来的系列问题.由于现有的AGV路径规划系统和AGV无人驾驶技术不够成熟，易出现由于一台AGV未能及时更换电池包导致没有足够电量返回换电站而停在车道的情况.更严重地，可能造成其他工作的AGV因为车道被占用为防止发生碰撞而触发车辆死锁现象，进而导致越来越多的AGV堵塞在行车道上，引发码头上的交通瘫痪.实际上一旦出现AGV电量不足而导致停工的情况，中控室将指派维修员对AGV进行临时充电，甚至需要重新规划调度系统，无疑会增加码头的人力成本和时间成本.因此，AGV正常运行的前提条件是，必须确保AGV有充足的电量使其在电量耗尽之前到达换电站.

图1 自动化集装箱码头AGV作业区域示意图

以卸船为例，自动化码头AGV工艺过程为：AGV 从AQC(自动化岸桥)接箱后，沿环形道路完成水平运输，由ARMG(自动化龙门吊)提箱，然后AGV沿环形道路返回AQC下方执行下一任务.AGV运输集装箱过程实际上是一个循环过程，见图2.假设AGV从换电站(或车场)出发时为满电状态，SOC(电量状态)值为1，指派该AGV从岸桥1(位置O1)运输集装箱T1至箱区1(位置D1)，完成该任务T1后，AGV根据实时SOC值判断是否能够继续完成别的任务，如果仍有足够电量则接着去完成任务T2，因此指派该AGV行驶至岸桥2(位置O2)，将集装箱T2运输到箱区2(位置D2)；而如果AGV的电池剩余电量不足以使其完成其他任务，则指派该AGV前往换电站(终点)进行换电，直至其换电完成，表示该AGV的一个循环过程结束；其后，AGV从该换电站出发，执行新的循环过程直至AGV完成所有任务.同时需要考虑的是，由于AGV空车行驶、重车行驶以及等待状态三种情况下耗电量有较大的差异，因此需要进行空驶行程、重载行程和排队等待过程的区分，分别计算不同状态下AGV的耗电量.

图2 AGV运输循环过程示意图

根据前期对洋山四期自动化码头的调研，得知其现有的换电模式为.当AGV电池包SOC值低于40%时即前往换电站进行换电.现有模式的弊端，一方面在于换电SOC临界值过大会引起电池电量利用率下降而提高电池使用成本，另一方面在于频繁的换电可能会造成换电过程中出现AGV在换电站排队等待的现象，从而进一步地造成AGV作业完工时间的延迟.因此，如何设计合理的换电模式、将换电模式同调度策略进行集成是建立调度模型的关键和难点.

2 模型构建

2.1 符号说明

2.2 数学模型

为减少AGV在换电站的排队及等待时间，降低换电过程对AGV调度的影响以提高整体作业效率，建立AGV作业与换电过程协同调度优化模型.模型的目标函数与约束条件如下.

(1)

s.t.

(2)

∀i≠j,v∈V

(3)

∀i∈I,v∈V

(4)

∀i≠j,v∈V

(5)

∀i≠j,v∈V

(6)

(7)

∑j∈I+(〗i}xjiv=yivn,∀i∈I,v∈V

(8)

(9)

xijv+xjiv≤1,∀i,j∈I,i≠j,v∈V

(10)

∑i∈Ix0+1,i,v=1,∀v∈V

(11)

∑i∈Ixi,O+2,v=1,∀v∈V

(12)

xi,O+1,v=0,∀i∈I+,v∈V

(13)

xO+2,j,v=0,∀j∈I+,v∈V

(14)

∀i,j∈I,v∈V

(15)

(16)

(17)

(18)

∑rvv′=1,∀v≠v′

(19)

(20)

(21)

3 遗传算法求解

3.1 染色体编码过程

一条染色体即问题的一个可行解，表征AGV分配到的任务，为了保证整个迭代过程中解的可行性，换电过程不直接显示在染色体中.2.1中总的集装箱任务数为|I|，总的AGV数量为|V|.每一台AGV完成多个循环运输，一条染色体由|I|个1到|V|之间的正整数组成.图3为15个任务、五台AGV对应的问题的染色体编码示意图，AGV编号对应的任务编号即为分配给该AGV的运输任务.例如，AGV2分配的任务列表task_AGV为{2 4 7 10}，对应的任务编号依次为2、4、7、10，因此AGV1执行任务的路径route_AGV为：车场/换电站→任务2→任务4→任务7→任务10→车场/换电站.

图3 染色体编码示意图

3.2 染色体解码过程

染色体解码过程即计算适应度值的过程.|V|台AGV需要在若干循环内完成|I|个任务，因此在遗传算法的解码操作过程中，需要考虑到每一台AGV在不同的任务循环周期内所分配到的任务.图4为遗传算法过程中染色体解码流程图.整个解码过程主要包括两个步骤，即生成初始AGV任务路径和判断是否进行换电两个部分.

3.3 适应度函数

3.4 遗传算子

3.4.1选择算子

采用轮盘赌的方法，每一条染色体在轮盘上占有的面积根据适应度函数值按比例表示出来，即个体适应度值越大，被选择的几率越大.经过实验对比，发现在其他算子不变的情况下采用谢菲尔德遗传算法工具箱中的轮盘赌rws函数得出的结果较好，见表1.

表1 AGV1需完成的4个任务的属性

3.4.2交叉算子

对于排列式染色体，通常采用单点或两点均匀交叉法，通过实验发现两者的差别不大，因此选择更为简单的单点交叉法：首先在种群中随机选择两条父代染色体P1和P2，然后随机选择一处切点，在这两条染色体中均复制从染色体的第一个基因到该切点间的染色体片段r1和r2，最后将r1和r2交换位置，得到两条子代染色体C1和C2，染色体交叉过程见图5.

图5 染色体交叉过程

3.4.3变异算子

采取随机改变1个基因位的基因的变异方法：在父代染色体P中随机选择1个基因位，将其替代为一个新的可行的基因，产生新的子代染色体.染色体变异过程见图6.

图6 染色体变异过程

4 数值实验

4.1 实验参数设置

为验证所构建模型的有效性和遗传算法的可行性，利用MATLAB软件对以下数值例子进行分析计算.随机产生100个集装箱任务样本，任务顺序即按照编号顺序，任务属性见表2，存放于Excel表格中.

表2 集装箱任务属性

为方便程序计算，设置2个换电站、8个堆场箱区、3台岸桥以及AGV停车场四类节点的坐标见表3.

共有15台AGV可供使用，假设AGV重车平均行驶速度为3 m/s，空车平均行驶速度为4 m/s，AGV在空车行驶状态下的耗电率为0.01%/m，重车耗电率为0.02%/m，因为考虑了等待时间，设置等待状态下的耗电率为0.005%/s.使用两个换电站，每个换电站同一时刻只允许一台AGV进行换电工作，换电站的作业时间误差不考虑，即每一个AGV换电时间相同，均为300 s/台，换电站内的电池储备充足.设置遗传算法中种群大小N_pop=100，最大迭代次数MAXGEN=200.其他参数都相同，换电SOC值为60%时，通过对在不同的Pc和Pm值条件下进行10次实验得到的平均makespan(最末完成任务时间)的对比，最终择优选择交叉概率Pc=0.7，变异概率Pm=0.05.

表3 节点坐标

4.2 实验结果分析

换电SOC临界值是换电模式的核心，也是模型中最重要的决策变量.依次设置SOC临界值为60%，70%，80%，90%和100%，进行五组实验对比，结果见表4.由表4可知，换电SOC值越大换电次数越少，最末任务完成时间并没有随着SOC值的增大而持续降低.在实际营运过程中，除了实现降低总的任务完成时间目标外，还需考虑AGV在前往换电站过程中以及在换电站的排队等待过程中的能量消耗，那么，设置一定的冗余电量来应对一些不确定性是有必要的.因此，综合来看，较优的方案为换电SOC临界值取值70%.

表4 不同换电SOC值条件下的结果对比

利用Matlab R2016b软件编程设计遗传算法进行问题的求解，采用上述参数，并设置种群数为N_pop=200，迭代代数MAXGEN=500，遗传算法迭代计算的收敛过程见图7，得出的近似最优解对应的AGV作业甘特图见图8.由图7可知，在170代的时候已收敛至近似最优解.图8中灰色矩形表示AGV换电时间.由图8可知，在该方案下有4台AGV进行了换电，且AGV在换电站排队等待时间较短.15台AGV的最大最末任务完成时间为3 103.8 s，同表2中最末任务的最早可开始时间2 992 s相比时间间隔很小，即该方案所需要的所有任务完成时间同初始设置的AGV最末任务开始执行时间之间的增量较小，可以认为是合理可行的调度方案.

图7 遗传算法收敛过程

图8 AGV作业甘特图

5 结 束 语

针对实际运营中的自动化集装箱码头AGV作业效率待提升的问题，从AGV换电管理优化和AGV换电与作业集成调度的视觉，构建调度模型并采用遗传算法求解.模型中区分了AGV实际生产作业中不同状态下AGV的耗电特性，模型决策变量除了集装箱是否分配到某台AGV之外，还包括AGV换电过程中的关键决策问题——换电SOC值.通过数值实验分析得出结论：合理的换电SOC值同换电次数及总的任务完成时间相关，AGV换电与作业协同调度可以有效减少AGV在换电站的排队等待时间，从而提高自动化集装箱码头AGV的整体作业效率.

需要指出的是，由于关注重点是AGV的作业效率，故只考虑了AGV等待岸桥或龙门吊准备集装箱的时间，没有考虑岸桥或龙门吊等待AGV的时间.从提高码头总的装卸效率的角度来看，设备之间的配合、协调，以及设备数量匹配等也都是非常值得研究的问题.