考虑充电过程的自动化码头AGV调度

杨其飞，兰培真

(集美大学航海学院，福建厦门 361021)

0 引言

以电池为电源的自动导引运输车(automated guided vehicle，AGV)，由于具有低排放、高能效特点，因此迅速在全球各大自动化集装箱码头得到普及。AGV的应用使得水平移动作业变得更加高效、安全和可控。目前针对自动化码头AGV的研究，主要集中在传统的作业调度配置和路径优化上，对AGV电池充电这一过程的研究较少。McHaney[1]通过数值实验验证了充电方案对AGV的作业时间、作业调度和AGV数量规划等方面的影响，提出使用电力驱动的AGV在实际作业过程中应考虑充电需求；文献[2]将AGV电量作为作业调度的约束，验证了使用电力驱动可节省10%的运行成本，但在AGV运行过程中没有安排充电任务；文献[3]考虑了AGV的电量限制，但当电量不足时则无法进行后续任务。近年来，一些学者将充电需求考虑到AGV作业调度中，同时考虑了AGV重空载耗电差异，充电、换电时机的选择和充电等待时间等因数[4-11]，提出一系列充电策略，如以离线充电为辅，在线充电为主的充电策略[7]，多频次充电策略[8]，机会式充电策略[9]等。综上可知，大多数研究主要针对AGV的充电策略，对影响充电的因素考虑较为单一，对AGV充电调度研究不够完善。针对以上问题，本文根据自动化码头AGV实际的作业调度现状，综合考虑AGV作业任务调度、AGV充电约束以及充电时间的选择和重空载耗电差异等因素，提出考虑充电过程的自动化码头AGV作业调度模型，以提高AGV的作业效率，缩短充电时间，寻求充电需求与码头作业任务之间的平衡。

1 问题描述

目前自动化码头使用的AGV小车多采用电力驱动，充电时间较长、续航能力有限。如果充电不及时，电量耗尽的AGV会停工，从而造成AGV作业效率的大幅度下降，因此必须考虑AGV充电过程对作业调度的影响。某水平式自动化集装箱码头分布如图1所示。AGV作业循环过程如图2所示。

在日常作业中，当AGV收到任务1后，且自身电量充足，则立即去岸桥缓冲区F1，装箱M1后运至堆场A01，完成任务后检查自身电量，AGV仍有足够的电量完成任务2，因此指派AGV行驶至缓冲区，装箱M2后运至堆场A02，在完成任务2，当电量不足时，AGV发送请求，经指派该AGV进行充电任务。同时需要考虑的是，由于AGV行驶中空载、重载的耗电量有所不同，因此要分别计算AGV不同状态的耗电量。

2 考虑充电过程的AGV作业调度模型

2.1 模型假设

本文主要研究AGV充电过程对自动化码头AGV调度的影响，考虑充电策略的AGV调度问题相对复杂，一方面AGV充电速率受其所剩电量的影响，另一方面AGV空重载行驶途中所消耗的电量也随着电量的消耗做相应的变化。寻找不同充电区间下的AGV作业时间与充电之间的关系变得更加困难，为方便模型的建立与求解，进行如下假设：每辆AGV每次运输一个集装箱；每辆AGV由调度中心进行任务分配，不考虑AGV在作业过程中可能产生的冲突等情况，均能正常完成任务；不考虑AGV的差异性，每辆AGV的运输效率相同，空载和重载的运行速度及耗电量不变；AGV到达充电位置点均能立即充电；AGV开始作业时刻为0。

2.2 符号说明

2.3 建立模型

本文以最小化最大完工时间为优化目标(见式(1))，最大完工时间即所有作业任务完工所需时间的最大值，同时将充电加入到AGV作业调度过程中，寻找不同充电过程下的AGV充电需求与码头作业任务之间的平衡。即

(1)

根据自动化码头AGV实际作业流程，设定约束条件。

1)电量约束。AGV在执行任务过程中，分为重载、空载两种状态，各种状态耗电量也不同，应区别对待两种状态。根据AGV电池荷电状态划分为强制充电区间、机会式充电区间、正常工作区间三个区间，故当AGV执行任务前应进行电量判定，决定是否接受任务。电量约束如下：

(2)

公式ei，v+Li，N+2≤Ev，∀i∈I，v∈V表示AGV剩余电量需足够返回离线充电点。

公式Li/s1=0，∀i∈C表示在执行充电任务时，AGV不允许接受其他任务并且处于静止状态。

每个实际任务应满足在其整个任务网络的流约束为：

∑j∈I+/{i}xjiv=∑j∈I+/{i}xijv=yiv，∀i∈I，v∈V。

∑v∈Vyiv=1，∀i∈I表示每个任务在被一台AGV执行一次后不能再被其他AGV运输。

xijv+xjiv≤1，∀i，j∈I，i≠j，v∈V表示每辆AGV在完成一项任务之前不能进行其他任务。

∑i∈IxN+1，i，v=∑i∈Ixi，N+2，v=1，∀v∈V表示对于执行运输任务的AGV都是从虚拟任务起点出发到虚拟任务终点处结束。

xi，N+1，v=xN+2，j，v=0，∀i∈I，v∈V表示为每辆AGV在虚拟任务之前不能有任务，在虚拟任务之后不能再有任务。

3 模型求解

3.1 遗传算法编码过程

根据AGV分配任务进行编码。设集装箱码头任务数为|N|、AGV的数量为|K|，染色体由|N|个1到|V|之间的正整数排列。图3为18个任务、6台AGV对应的染色体编码任务示意图，第i个编码为v，则表示第i个任务是由AGVv进行运输。

3.2 染色体解码过程

首先将|I|个运输任务分配给|K|辆AGV，并且要求在若干个循环中完成任务，因此要对AGV分到的相应的运输任务进行解码。图4是遗传算法过程中解码的流程图。其中：SOC(stale of change)表示存电状态，当SOC=0时，表示电池放电完全；当SOC=1时表示电池完全充满。

整个任务解码过程主要包括：1)判断是否进行充电，2)生成初始AGV任务路径，并在运行的过程中进行机会式充电。

3.3 适应度函数

本文初始的适应度函数是解码得到的AGV最大完工时间Max(f)，但是最终的目标函数是minMax(f)，故将得到的AGV最大完成工时Max(f)，取其倒数作为适应度函数，并通过该值来判断每个可行解的优劣程度。

3.4 遗传算子

采用随机遍历选择法、均匀交叉法和倒置变异法分别进行选择算子、交叉算子、变异算子的遗传操作。在选择算子遗传操作中，任意选取4个个体，分别计算适应度值，并进行比较，得到两个较优的个体。在交叉算子遗传操作中，选取两条父代染色体后随机选择两处切点，复制两处切点中染色体后，交换这两条切片染色体，生成新的子代。在变异算子操作过程中，随机在染色体上选择两个位置，颠倒两个位置间的基因序列，其中变异算子过程如图5所示。

4 模型检验

4.1 检验参数设置

在以上算法模型的基础上，通过Matlab软件进行编码和模型检验。将收集的数据放于特定的Excel表格中，令AGV载速度为3.5 m/s，空载速度为5.8 m/s，重载状态下耗电率为0.003 SOC/m，空载状态下耗电率为0.0015 SOC/m。通过对厦门远海码头实地调研得到岸桥和堆场之间的距离见表1。

表1 岸桥和堆场之间的距离Tab.1 Distance between bridge and yard m

4.2 检验场景

1)实验一

实验目的：对比不同充电策略，选出最优的充电策略。

检验设置：限定GA最大迭代次数为300，种群为30，交叉概率为0.8，变异概率为0.4，取AGV数量为10，分别取不同任务数(500～2000)。

(2)实验二

实验目的：根据实验一得出的结论，确定最佳的机会式充电区间范围。

检验实验设置：选取机会式充电策略，取AGV数量为10，任务数为1000，分别改变机会式充电区间的范围，其他设置与检验1相同。

4.3 实验结果分析

1)实验一结果分析

实验一设计以下3种充电策略。策略1即传统离线式充电方法，当前剩余电量低于40%时，强制进行充电，并且充满；策略2为改进传统离线式充电方法即按需充电，当前剩余电量低于40%时，强制进行充电，并且按需充电；策略3即机会式充电，当前剩余电量低于30%时进行强制充电，当前剩余电量高于30%低于45%时采用机会式充电，当前剩余电量高于45%时，正常工作。

对这3种充电策略进行检验，AGV运行40次，取运算结果的平均值作为参考值。AGV数量为10辆，当任务数分别为500、800、1000、1300、1500、1800、2000时，3种充电策略完成任务总时间见如表2所示。

表2 3种充电策略作业时间对比Tab.2 Comparison of operation time of three charging strategies任务数Number of jobs作业时间 Comparison of operation time/s充电策略 Charging strategy 1充电策略 Charging strategy 2充电策略 Charging strategy 350019 48917 87617 35480033 85931 08930 2751 00041 54938 58536 8491 30052 98249 45747 1251 50061 08958 16154 8941 80073 89169 78465 7892 00082 87177 59474 184

由表2可知：充电策略2整体上优于充电策略1，当任务数为1000时，策略2作业过程中每次充电后的电量如图6所示。这种按需充电策略，不仅解决充电时间过长的问题，提高了AGV的充电利用率和作业效率，而且解决了某些码头因充电装置过少而造成的充电排队等待的问题。

对比充电策略2和充电策略3，可以得出充电策略3整体上优于充电策略2，并随着任务量的增加，充电策略3的优势逐渐扩大。当任务数为500时，分别记录充电策略2和充电策略3的AGV的电量变化曲线如图7所示。可以看出机会式充电策略不但结合了按需充电的传统充电策略的优势，而且利用其等待空闲时间进行充电作业，大大提高了码头作业系统效率。

2)实验二结果分析

参考文献[9]提出的模型，在机会式充电区间(30，85)且区间长度为15、10两种不同情况下分别进行模型检验，并纪录最终完成任务时间、平均每辆AGV总充电时间以及充电次数这3项指标，得出结果如表3所示。

表3 不同充电区间的各项评价指标Tab.3 Evaluation indexes of different charging intervals

首先对比区间宽度为15的3组数据，发现当机会式充电区间为(70，85)时，其中每一项指标都比其他两个充电区间高，这是由于当机会式充电区间过高时，充电速率随电池SOC增高而降低，所以充电时间比其他两个充电区间多了很多。虽然电池在该区间段耗电较慢，但是此段电池的利用率比较低，这两点导致了最终完成时间的增加。当机会式充电区间为(30，45)时，得到的数据和充电区间(50，65)比较接近，但是根据文献[12]可知，当电池深度放电过多时电池交流内阻会显著提高，对电池性能、寿命造成严重影响。总体上对比区间宽度为15的这3组数据，机会式充电区间为(50，65)的综合评价最优。当区间宽度为10时，通过对比数据发现，充电次数总体上比区间宽度为15的多，并且当区间为(70，80)时，出现了与区间为(70，85)同样的问题。对比区间宽度为10的这5组数据，区间为(40，50)要优于另外4组。

通过对比区间(50，65)和(40，50)这两组数据，得出机会式充电区间为(50，65)的综合评价指标最优，此时AGV充电时间较短，并且耗电速率较慢，可以更多地减少AGV充电对码头作业调度的影响。

5 结束语

自动化集装箱码头AGV作业调度问题是影响码头作业效率的关键问题，本文在AGV作业调度的过程中考虑了AGV电池续航能力和空重载耗电差异，提出了考虑充电过程的AGV作业调度模型，并采用GA求解。对比3种充电策略，得出：与传统离线式充电策略相比，机会式充电策略能够有效的减少AGV充电对作业调度的影响，并且合理的机会式充电区间同总的任务完成时间相关，AGV充电和作业协同调度可有效的减少AGV充电次数和时间，进而提高码头的整体作业效率。由于本文重点关注自动化码头AGV的作业效率，未考虑AGV在运行过程中所产生的路径冲突以及AGV充电站位置、数量和规划等问题对作业调度的影响，这些问题今后将做进一步研究。