考虑充电策略的自动化码头AGV调度

陈珲 韩晓龙

摘要：针对自动化码头自动导引车（automated guided vehicle， AGV）在作业调度中的充电问题，以最小化所有任务完成时间为目标，建立考虑充电策略的AGV调度模型。对比求解器（Gurobi）与遗传算法的算例求解结果，验证遗传算法的高效性。设计4种充电方式并对其优劣性进行对比，分析AGV数量和续航能力对作业时间和充电利用率的影响。得出结论：按需充电的方式可以有效减少不必要的充电时间，合理的AGV数量配置可以有效提高作业效率和充电利用率。

关键词：

自动化码头; 自动导引车（AGV）调度; 充电策略; 遗传算法

中图分类号：  U691+.3

文献标志码：  A

AGV scheduling of automated terminals considering charging strategy

CHEN Hui， HAN Xiaolong

（

Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

For the charging issue of automated guided vehicles （AGVs） in operation scheduling of automated terminals， aiming at minimizing the completion time of all tasks， an AGV scheduling model considering charging strategy is established. The results of the solver （Gurobi） and the genetic algorithm are compared through examples， and the efficiency of the genetic algorithm is verified. The four charging schemes are designed， and their advantages and disadvantages are compared. The influence of the number of AGV and the endurance on the working time and the charging utilization rate is analyzed. It is concluded that the on-demand charging scheme can effectively reduce the excess charging time， and the appropriate AGV quantity configuration can effectively improve the operation efficiency and the charging utilization rate.

Key words：

automated terminal; automated guided vehicle （AGV） scheduling; charging strategy; genetic algorithm

收稿日期： 2020-06-30

修回日期： 2020-11-26

基金项目：

上海市科学技术委员会工程中心能力提升项目（ 14DZ2280200）

作者简介： 陈珲（1995—），男，江苏南通人，硕士研究生，研究方向为港口运营与管理，（E-mail）1226191601@qq.com;

韓晓龙（1978—），男，山东潍坊人，副教授，博士，研究方向为物流与供应链管理，（E-mail）superhxl@163.com

0 引 言

随着经济全球化的发展，国际贸易活动越发频繁，港口集装箱吞吐量也逐渐增加。为更好地满足港口作业需求，需要进一步提高港口作业效率。纯电力驱动的自动导引车（automated guided vehicle，AGV）正逐渐成为新一代港口海侧运输作业的主要设备。

国外AGV调度的研究大多集中在作业分配和路径优化方面。CHANG等[1]提出一种基于遗传算法（genetic algorithm， GA）的仿真优化算法，采用响应面分析法优化GA参数，以提高AGV的作业效率。GELAREH等[2]设计了一种新型的智能车辆，通过灵活的作业分配缩短作业路径。WU等[3]用一种基于模糊逻辑控制的车辆路径规划方法提高AGV作业路径的安全性。针对多AGV路径规划问题，HAN等[4]提出三交换启发式算法，用来缩短单AGV作业路径和多AGV作业总路径。针对港口的协同调度问题，YANG等[5]以最小化作业时间为目标，建立双层规划模型，并利用滚动视距法和双层GA进行求解。

少部分学者考虑了充电对AGV调度的影响。MCHANEY[6]提出电池的使用

对AGV的作业调度有很大影响，但这种影响

在AGV仿真中常常被忽视。MOUSAVI等[7]以最小化AGV数量为目标，建立了考虑充电的AGV作业调度模型，并采用混合GA进行求解。ZHAN等[8]使用锂离子电池，采用双充电站的充电模式，建立了AGV调度模型，并通过实际案例证明该方法能有效提高AGV的作业效率。

与国外相比，国内自动化码头建设还处于初期，对AGV的作业调度还需要进一步研究。康凯等[9]分析了干散货港口装卸作业调度之间的联系，构建了作业系统集成调度模型，并采用GA进行求解。韩晓龙等[10]建立了岸桥、AGV、场桥和堆场的仿真模型，设计了不同的AGV调度策略，根据实验结果给出了AGV调度和数量优化的相关建议。刘高强等[11]通过改进GA的变异算子提高种群的收敛速度，获得了更优路径。张亚琦等[12]以最小化AGV作业时间为目标建立模型，并用GA进行求解，虽然考虑了AGV的充电过程，但对具体的充电决策研究不足。针对AGV的路径规划问题，赵大兴等[13]提出一种基于高适应度值的GA，仿真结果表明该调度策略合理高效。孟冲等[14]以最小化AGV作业时间为目标，将GA引入双阶段路径规划中，实验结果表明该策略提高了AGV调度系统的效率和鲁棒性。仲美稣等[15]采用“模型+实例+仿真”的方法研究自动化码头AGV路径优化问题，提出交通虚拟环岛策略，仿真结果证明了该策略的高效性。

国内外学者对实际作业中的充电问题研究较少，而充电策略对AGV的作业调度有很大的影响：充电站和作业点的位置关系会影响作业顺序;一旦AGV由于电量不足停在某个任务的路径中，会大幅降低作业效率。本文考虑AGV在实际作业中的充电问题，对具体路径优化中的充电策略展开研究，以缩短作业时间，提高充电利用率。

1 问题描述

自动化码头的AGV与电动汽车一样，不仅充满电所需的时间较长，而且续航能力有限。在实际作业中，AGV每完成一个任务后都需要计算当前的剩余电量，只有当剩余电量足够时才会进行下一个任务。

考虑充电策略的AGV调度问题相对复杂，一方面要满足AGV电量的及时补给需求，另一方面AGV充电受其剩余电量的影响。为方便计算，假定AGV的电量消耗与行驶路程成正比。

图1是集装箱堆场的俯视图。在日常作业中，AGV收到任务后，立即去相应的作业点执行任务;当电量不足时，AGV会发送充电请求，系统收到后会给该AGV分配充电任务;AGV收到充电任务后，回到充电站进行充电;AGV充电完成后再次进入作业状态。

AGV执行任意两个相邻任务的流程如下：AGV在任

务i的装载点装货后，到任务i的交付点卸货;完成任务i后根据剩余电量判断是否需要充电，若不需要则直接执行任务j，否则去充电站充电后再执行任务j。从开始执行任务到返回充电站充电，称为一个作业循环。

2 考虑充电策略的AGV调度模型

2.1 模型假设

每辆AGV每次只能运输一个集装箱;岸桥和场桥的单位集装箱装卸时间是固定的;AGV匀速行驶;AGV从初始位置出发，各自作业，相互独立;充电站内有足够多的充电接口，AGV到达充电站后均能立即充电;不考虑作业过程中的突发状况，

AGV均能正常完成任务;AGV开始作业时刻为0。

2.2 符号说明

I为所有任务的集合，I={1，2，…，N};集合I+={1，2，…，N，N+1，N+2}，其中N+1和N+2分别为虚拟开始任务和虚拟结束任务;K为AGV集合，K={1，2，…，|K|}，k∈K;C为充电任务集合（未知），C={N+3，N+4，…};M是一个足够大的数;Lij为从任务i的交付点到任务j的装载点之间的距离;Li为从任务i的装载点到任务i的交付点之间的距离;Tij为AGV从任务i的交付点到任务j的装载点的时间;Ti为AGV从任务i的装载点到任务i的交付点的时间;tik为AGV k针对任务i的装卸作业时间;b为充电时间参数，为充电时间与充电电量的比值;a为[0，1）之间的常数，表示AGV最低剩余电量占电池充满电时电量的比值;G为AGV续航能力;xijk为0-1变量，若AGV k完成任务i后紧接着去执行任务j则取1，否则取0;yik为0-1变量，若AGV k执行任务i则取1，否则取0;qik为AGV k到达任务i的装载点时的剩余电量;Qi为充电任务i的目标电量;Q为电池充满电时的电量;f为完成最后一个任务的时刻;Zi为任务i的开始时刻;dik为AGV k完成任务i的累计行驶路程;Rk为AGV k的实际行驶路程;Sk为AGV k的理论可行驶路程;r为AGV的充电利用率。

2.3 建立模型

以最小化所有任务完成时间为目标函数（见式（1））建立模型如下，其中下标k∈K。

min f

（1）

s.t.

xi，N+1，k=0， i∈I+

（2）

xN+2，i，k=0， i∈I+（3）

f≥Zi+Ti， i∈I+（4）

xijk+xjik≤1 （i，j∈I∪C;i≠j）（5）

kyik=1， i∈I（6）

Zj+（1-xijk）M≥Zi+tik+Ti+Tij

（i，j∈I;i≠j）（7）

Zj+（1-xijk）M≥Zi+tik+Tij，

tik=b（Qi-qik），Qi>qik

（i∈C; j∈I）（8）

aQ≤qjk≤qik-（Li+Lij）Qxijk/G+Q（1-xijk）

（i，j∈I;i≠j）（9）

aQ≤qjk≤Qi-LijQxijk/G

（i∈C; j∈I）（10）

qN+1，k=Q（11）

djk+（1-xijk）M≥dik+Lij+Lj

（i，j∈I+∪C;i≠j）（12）

Li=0 （i∈C）（13）

i∈I+＼{j，N+2}xijk=l∈I+＼{i，j，N+1}xjlk=yjk

（j∈I）（14）

式（2）和（3）分別表示虚拟开始任务之前和虚拟结束任务之后AGV没有任务执行;式（4）表示最后一个任务完成时刻与各任务完成时刻的关系;式（5）表示各AGV完成单方向的作业序列，即不允许重复同一个作业;式（6）表示每个任务必须由一辆AGV单独完成;式（7）和（8）表示连续两个任务开始时刻的关系;式（9）和（10）表示连续两个任务开始时剩余电量的关系;式（11）表示执行任务之前AGV处于充满电状态;式（12）表示AGV执行连续两个任务的累计行驶路程之间的关系;式（13）表示充电过程中AGV停止不动;式（14）表示连续任务之间的流约束。

3 GA

3.1 编码

本文根据AGV的任务分配进行编码。任务i对应AGV k，表示任务i由AGV k完成。先随机生成N个位于（0， |K|）区间内的随机数，然后给这些随机数按顺序标上任务编号，并将这些随机数分别去尾取整后加1，得到任务对应的AGV编号（如对1.23处理后得到的AGV编号为2）。图2是一个由3辆AGV进行12个任务作业的染色体编码。

3.2 解码

先将N个任务分配给|K|辆AGV，然后按照每辆AGV获得的任务进行解码。各AGV在被分配任务后，对任务按任务编号由小到大排序，接着根据任务顺序进行作业，这样既满足了任务的分配，也考虑了任务本身的顺序。

染色体的解码过程如图3所示，其中：m表示任务N-4之前的任务编号。每辆AGV的任务及其

顺序确定后，结合模型得到其执行完任务后的累计

行驶路程以及执行每个任务的开始时刻，根据式（7）和（8），得到所有任务完成时间。

3.3 适应度函数

本文适应度函数为min f，即最小化所有任务完成时间，以此来判断每个可行解的优劣程度。

3.4 选择

选择的目的是将优秀的个体尽量遗传下去，但为了避免种群收敛太快陷入局部最优解的情况，在选择时也要考虑非优秀个体。本文采用随机遍历选择法，使适应度值不同的个体被选择的机会均等。任意选取4个个体，计算其适应度值，得到2个较优个体。

3.5 交叉

采用基于位置的交叉方法生成新的染色体，见图4。

步骤1 令2条较优的染色体分

别为p1、p2，2条新染色体分别为c1、c2。

步骤2 把p1的前半部分的基因值赋值为c1的前半部分的基因值，然后把p1剩余的基因值赋值为c2的后半部分的基因值。

步骤3 把p2的前半部分的基因值赋值为c2的前半部分的基因值，然后把p2剩余的基因值赋值为c1的后半部分的基因值。

步骤4 重复前面3个步骤，直到新的个体数量满足种群要求。

3.6 变异

在染色体中随机选择2个基因位b1、b2进行调换，得到新的染色体，如图5所示。

4 数据实验

在以上模型和算法的基础上，使用Python 3.7进行代码编写和数据实验，实验设置见表1。实验1对比了GA与混合整数线性规划（mixed integer

linear planning， MILP）算法的求解结果（调用求解器Gurobi）;实验2对比了不同充电方案的作业时间（用GA计算）;实验3研究了AGV数量和续航能力对作业时间和充电利用率的影响（用GA计算）。

4.1 不同算法的求解结果（实验1）

当任务数分别为8、9、10、11、12、16、20时，不同算法的求解结果见表2。

由表2可知：GA的计算结果与精确解的误差较小;当任务数超过11时，MILP算法的计算时间显著增加，而GA的计算时间很短且解的质量较优。实际问题中任务较多且求解要求较高，因此用GA求解实际问题更为合适。

解的平均偏差率计算公式为

D=Ww=1fw-fminfmin

W×100%

（15）

式中：W表示实验次数;fw表示第w次实验得到的作业时间;fmin表示所有实验中的最短作业时间。

为验证GA求解结果的稳定性，通过反复实验找到最优的交叉与变异概率组合，再用GA求解任务数为1 000的作业时间，重复实验40次，得到最短的作业时间为28 631 s。根据式（15）得到解的平均偏差率D仅为0.44%，说明采用GA给出的方案是可靠的。

4.2 充电方案对比（实验2）

在研究AGV的充电策略时，要考虑充电时机和每次目标充电量这两个问题。

充电时机会影响AGV完成相同任务所需的充电次数，较多的充电次数会增加无效的空载时间。因此，在现有的续航能力约束下要尽量减少充电次数。针对该问题，有2种策略：剩余电量不足10%时充电;当利用剩余电量无法完成下一个任务时，或完成下一个任务后无法前往充电站时充电。

针对每次目标充电量问题，也有2种策略：每一次都充满;根据下一作业循环的实际需求充电。综合以上4种策略，设计4种充电方案，见表3。

对这4种充电方案进行实验。设置AGV数量为12辆，AGV的续航能力G为20 km;根据前述反复实验结果，取交叉概率0.7，变异概率0.4;根据收敛情况，确定最大迭代次数为500。当任务数分别为1 000、1 100、1 200、1 400、1 600、1 800、2 000、2 400时，4种充电方案作业时间对比见表4。

由表4可知：方案3、4整体上优于方案1、2;虽然在任务数為1 200和1 400时，方案4略优于方案3，但是作业时间差距很小，方案3总体上最优。

为更好地说明方案3的优势，分别记录任务数为1 000和2 000时，12辆AGV在作业过程中每次充电后的电量，见图6。当任务数为1 000时，每辆AGV只需充电1次即可完成任务;当任务数为2 000时，每辆AGV需要充电2次才能完成任务;每辆AGV每次充电量不同，这由下一作业循环所需电量决定。当所需电量较多时多充，反之则少充，满足电量需求即可。这种灵活的充电方式，能够有效减少不必要的充电时间，在提高充电利用率的同时，也采用方案3充电后电量缩短了总的作业时间。

4.3 AGV数量和续航能力对作业时间和充电利用率的影响（实验3）

充电利用率r的计算公式如下：

r=kRkkSk

（16）

Rk=max{dik}， i∈I+，k∈K

（17）

Sk=i∈Ctikb+QGQ， k∈K

（18）

采取充电方案3，以最小化所有任务完成时间和最大化充电利用率为目标，取续航能力G为20 km，任务数为1 000，设置AGV数量为9～20辆进行实验，结果如图7a所示：随着AGV数量的增加，作业时间逐渐减少;充电利用率在AGV数量不超过15辆时高达98%，在超过15辆时明显下降。考虑配置AGV的成本以及充电利用率，当任务数较大时，给3台岸桥配置15辆AGV进行作业比较合适。

取AGV数量为15辆，任务数为1 000，研究续航能力对作业时间和充电利用率的影响。从图7b可以看出，随着续航能力的增强，作业时间先是大幅度减少，而后趋于稳定。续航能力的增强，会使AGV的充电次数减少，从而使充电时间以及AGV往返充电站的空载时间减少。当续航能力达到足够大（如G=25 km）时，AGV在作业过程中不需要进行充电，总的作业时间与充电无关，趋于稳定。另外，随着充电次数的减少，AGV的累计行驶路径长度也会减少。根据式（17）和（18）容易得到，任务数一定时，充电利用率会随着续航能力的增强而不断降低，这是由AGV完成任务后剩余电量较多造成的。

当任务数一定时，AGV数量的增加和续航能力的增强都会使每辆AGV在完成相应任务后剩余电量较多。前者是由每辆AGV执行的任务数减少且不需要充电导致的，后者是由电池总电量增大导致的，二者都会导致充电利用率降低。因此，为提高充电利用率，AGV数量不宜过多;在续航能力较强时，应当给AGV分配较多的任务。

5 结束语

本文从自动导引车（AGV）作业的实际情况出发，研究充电对作业调度的影响，建立了考虑充电策略的AGV调度模型，给出了不同的充电方案，并对比了它们的优劣。通过实验得到以下结论：

（1）考虑充电策略的AGV调度问题属于NP难问题，当任务较少时，可以用混合整数线性规划（MILP）算法求得精确解;在任务较多时，求解器无法在短时间内求得结果，必须采用GA（GA）等智能搜索算法。实验结果证明采用GA求解该问题是高效、可靠的。

（2）在AGV运输速度、装卸作业时间、任务安排一定的情况下，作业的完成时间很大程度上取决于AGV的充电策略。在利用剩余电量无法完成下一个任务时充电且按需充电是一种较好的充电方案，它能够节省不必要的充电时间，提高充电利用率，进一步缩短作业时间。

（3）在任务数一定时，AGV数量的增加可以减少作业时间，但同时也会降低充电利用率，导致资源配置的不合理。因此，不能一味地增加AGV数量，需要寻找AGV数量与任务数的最佳配比。实验结果表明，在任务数较大的情况下，给3台岸桥安排15辆AGV较为合适。另外，提高续航能力能减少充电次数，提高作业效率，适合完成作业量较大的任务。

本文未考虑AGV满载与空载时不同的电量消耗、充电站的容量配置等对AGV调度的影响，这方面还需要进一步研究。

参考文献：

[1]CHANG Xiaokun， DONG Ming， YANG Dong. Multi-objective real-time dispatching for integrated delivery in a Fab using GA based simulation optimization[J]. Journal of Manufacturing Systems， 2013， 32（4）： 741-751. DOI： 10.1016/j.jmsy.2013.07.001.

[2]GELAREH S， MERZOUKI R， MCGINLEY K， et al. Scheduling of intelligent and autonomous vehicles under pairing/unpairing collaboration strategy in container terminals[J]. Transportation Research Part C， 2013， 33： 1-21. DOI： 10.1016/j.trc.2013.04.006.

[3]WU K H， CHEN C H， KO J M. Path planning and prototype design of an AGV[J]. Mathematical and Computer Modelling， 1999， 30（7/8）： 147-167. DOI： 10.1016/S0895-7177（99）00171-5.

[4]HAN Zengliang， WANG Dongqing， LIU Feng， et al. Multi-AGV path planning with double-path constraints by using an improved genetic algorithm[J].PLoS One， 2017， 12（7）： e0181747. DOI： 10.1371/journal.pone.0181747.

[5]YANG Yongsheng， ZHONG Meisu， DESSOUKY Y，et al.An integrated scheduling method for AGV routing in automated container terminals[J]. Computers & Industrial Engineering， 2018， 126： 482-493. DOI： 10.1016/j.cie.2018.10.007.

[6]MCHANEY R. Modelling battery constraints in discrete event automated guided vehicle simulations[J]. International Journal of Production Research， 1995， 33（11）： 3023-3040. DOI： 10.1080/00207549508904859.

[7]MOUSAVI M， YAP H J， MUSA S N， et al. A fuzzy hybrid GA-PSO algorithm for multi-objective AGV scheduling in FMS[J].International Journal of Simulation Modelling， 2017， 16（1）： 58-71. DOI： 10.2507/IJSIMM16（1）5.368.

[8]ZHAN Xiangnan， XU Liyun， ZHANG Jian， et al. Study on AGVs battery charging strategy for improving utilization[J].Procedia CIRP， 2019， 81： 558-563. DOI： 10.1016/j.procir.2019.03.155.

[9]康凱， 张敬， 张维存， 等.干散货港口装卸作业系统集成调度模型与算法研究[J].物流技术， 2014， 33（7）： 121-125， 188. DOI： 10.3969/j.issn.1005-152X.2014.04.040.

[10]韩晓龙， 樊加伟. 自动化港口AGV调度配置仿真分析[J].重庆交通大学学报（自然科学版）， 2016， 35（5）： 151-154， 164. DOI： 10.3969/j.issn.1674-0696.2016.05.29.

[11]刘高强， 刘利桁， 刘婷. 基于改进GA的多AGV调度优化[J].机电技术， 2017（5）： 44-46， 50. DOI： 10.19508/j.cnki.1672-4801.2017.05.014.

[12]张亚琦， 杨斌， 胡志华， 等.自动化码头AGV充电与作业的集成调度研究[J].计算机工程与应用， 2017， 53（18）： 257-262， 270. DOI： 10.3778/j.issn.1002-8331.1605-0003.

[13]赵大兴， 余明进， 许万. 基于高适应度值GA的AGV最优路径规划[J].计算机工程与设计， 2017， 38（6）： 1635-1641. DOI： 10.16208/j.issn.1000-7024.2017.06.043.

[14]孟冲， 任彧. 基于多种群GA的多AGV调度[J].电子科技， 2018， 31（11）： 47-50， 68.

[15]仲美稣， 杨勇生. 卸船作业模式下自动化码头AGV路径仿真优化[J].水运工程， 2018（4）： 122-127.

（编辑 赵勉）