集装箱码头上多自动引导车的调度和路径规划

李 静，朱小林,2+

(1.上海海事大学 文理学院，上海 201306；2.上海海事大学 物流科学与工程研究院，上海 201306)

1 问题的提出

随着全球经济一体化的快速发展，国际贸易日益频繁，而海运作为最基本的物流和运输方式发挥着重要作用，其中自动化集装箱码头的地位日益突显。高效的自动引导车(Automatic Guided Vehicle,AGV)的调度成为保证自动化集装箱码头高效运行的关键，直接关系到整个码头的运行，与之相关的AGV路径规划也十分重要，它会影响AGV的运输效率，从而影响整个码头的运行效率。AGV根据路径规划的结果进行调度，而AGV的路径规划又受到调度的影响和约束。

整个自动化集装箱码头布局如图1所示，由岸桥、AGV运输区域、堆场组成。AGV的运输过程以进口集装箱为例，进口集装箱到达港口，通过某个岸桥将集装箱从船上卸载后装载到AGV上，然后AGV根据指定路线运输到集装箱对应堆场前卸载，出口集装箱运输路线相反。

目前，已经有很多学者对AGV调度和路径规划进行了研究。对于在码头上AGV的调度研究大多是AGV与岸桥、堆场起重机的协调调度研究，还有码头上多载AGV的调度问题的研究。杨勇生等[1]研究了AGV与轨道式龙门起重机(Rail Mounted Gantry Grane,RMG)的协同调度问题,建立了混合整数规划模型，小规模采用CPLEX软件和遗传算法分别求解，大规模采用遗传算法求解；ZHAO等[2]建立了自动化岸桥和AGV的协同调度模型，考虑了岸桥上传输平台的容量限制，并采用两阶段禁忌搜索算法进行求解；ZHONG等[3]对岸桥、AGV、堆场起重机综合调度进行优化，采用混合整数规划模型，对比各种基本的元启发式算法和改进的元启发式算法发现，所提出的模糊控制自适应自整定混合算法更有效；CHEN等[4]研究了自动化集装箱码头的堆场起重机和AGV调度，提出一种多商品网络流模型，采用乘数交替方向法(Alternating Direction Method of Multipliers,ADMM)来双重化硬约束，所提方法有效地协调了自动终端中的AGV和起重机；MA等[5]提出一种基于优先级规则的算法(带变异过程的蛙跳算法)解决多载AGV的调度。

因为AGV应用广泛，所以有许多在其他场景中对AGV调度的研究。刘二辉等[6]研究作业车间中的AGV调度，提出一种基于改进花授粉算法的调度算法；FAZLOLLAHTABAR等[7]研究了制造系统中多个AGV的调度问题，提出一种求解空间和寻优两个阶段的优化方法；JIN等[8]将处理时间的组成、某些任务的优先顺序作为主要限制因素，提出动态AGV的调度方法，并采用遗传算法进行求解；MOUSAVI等[9]研究了柔性制造系统中AGV的多目标调度，开发了数学模型，并将其与进化算法集成在一起；LIU等[10]考虑无人仓库自动分拣系统中的多目标AGV调度，在所建模型中考虑了AGV充电任务和可变速度；ZOU等[11]研究了线性制造车间物料处理过程中的AGV调度问题，提出了整数线性规划模型，并提出一种改进的基于最近邻的启发式算法以及离散人工蜂群算法。

然而，仅对AGV路径规划的研究不太多，大多都是针对特殊问题或特殊情况下的研究。NISHI等[12]提出一种Petri网(Petri Net,PN)分解方法来优化半导体制造库中AGV的路线规划问题；施剑烽等[13]对自动化码头上AGV路径规划的Dijkstra算法进行了研究；杨勇生等[14]研究了只卸不装的AGV路径规划问题，建立了多目标混合整数规划模型；ZHANG等[15]提出一种基于碰撞分类的AGV无碰撞路径规划方法，并使用网格方法描述AGV的环境图，每个任务的初始路径由改进的Dijkstra算法预先确定，然后检测潜在冲突，给出了4种碰撞分类和3种解决方法；TAI等[16]提出一种基于时间窗的优先AGV路径规划算法，解决了多个AGV延迟问题，提出的算法引入规划原理和局部可调路径，解决了时延问题并降低了时延；XU等[17]设计了一个AGV最多可装载两个集装箱的路径规划模型，并采用模拟退火算法对其求解，实现了AGV的双向装载；YUAN等[18]提出了一种双层路径规划算法来优化AGV的路线，上层使用A*算法规划全局路径，下层提出快速探索随机树(Rapid-exploration Random Tree，RRT)算法获取局部路径，大大减少了多个AGV路径冲突的发生。

同时，也有许多将AGV的调度和路径规划结合起来的研究。UMAR等[19]研究了柔性制造系统环境下AGV的综合调度以及路径规划，提出一种混合遗传算法，将多目标转变为单目标作为适应值，并利用模糊专家系统来控制遗传算子，即实现算法的自适应调整；ZAGHDOUD等[20]将AGV对集装箱的装卸问题分为分配问题、安排问题和路径问题3个子问题，并提出了用Dijkstra算法、遗传算法、启发式算法的混合算法来解决装卸问题；MIYAMOTO等[21]研究了容量性AGV系统的调度和无冲突路径问题(Dispatch and Conflict-free Routing Problem of Capacitated AGV，DCRPC)，提出了局部/随机搜索方法；LYU等[22]研究了自动运输系统的AGV调度和路径规划，并基于A*算法和复杂的调度策略解决AGV路径规划问题，提出一种基于单向图路径的规划算法；YANG等[23]考虑岸桥、AGV、堆场起重机综合调度下，AGV路径的规划，采用基于拥塞预防规则的双层遗传算法进行求解；FAROOQ等[24]研究了在智能纺纱生产系统中AGV分配和路径规划的混合流车间调度问题，通过优化分配效率和提高自动化程度来防止冲突和死锁；FAZLOLLAHTABAR等[25]研究了在制造系统中AGV的同时调度和路径问题，将该问题公式化为网络数学模型，并使用修改后的网络单纯形算法进行了优化；ZHONG等[26]将路径规划和调度问题结合起来考虑，实现了多AGV无冲突路径规划的集成调度，提出混合遗传-粒子群算法和模糊逻辑控制器算法对其求解；余娜娜等[27]研究在自动化分拣仓库中多AGV调度和路径规划，提出一种改进差分进化算法进行求解。

综上可知，对AGV的调度和路径规划的研究非常多，但对于自动化码头上将AGV的调度和路径规划结合起来的研究却很少，大多数研究将AGV调度和路径规划结合考虑时，在路径规划上只考虑最短路径问题，很少考虑AGV之间的冲突问题，即使考虑到冲突也是实时解决，很少有预防措施。基于此，本文研究了自动化码头上AGV的调度和预防冲突的路径规划，并考虑了路径上AGV是否负载，以此优化AGV的能量消耗。

2 问题描述与模型

本文主要研究AGV的调度与路径规划问题。AGV具体运输路径如图2所示，其中：节点2，4，6表示岸桥所在点，节点11，13，15表示堆场所在点，外循环是AGV主道路行驶方向，为顺时针方向，中间的双向道路为辅助道路。现考虑在已知若干进口、出口集装箱装卸点的情况下，如何给若干AGV进行分配任务、安排任务的处理顺序，以及如何规划若干AGV运输路径，使得AGV能量消耗最小，并且使AGV之间的冲突降到最低。在运输路径图2下，交叉口容易出现冲突死锁的情况，而对辅助道路进行容量限制则可以降低AGV之间发生冲突的可能性[26]，因此本文考虑辅助道路容量限制来预防冲突的发生。

2.1 设置和假设

(1)AGV都以同样的速度匀速运输，AGV彼此保持安全距离行驶，即在非辅助道路节点上不存在冲突情况,在辅助道路节点上遵守先到先得(First Come First Serve,FCFS)的规则，即先到的AGV先行驶，因为安全距离小，所以等待时间忽略。

(2)考虑将AGV整个路径分段，包括AGV分别负载每个所分配集装箱时的路径和AGV空载时，从上一个集装箱任务的卸载点到下一个任务的装载点时的路径。

(3)每条辅助道路上每个方向的道路限制容量不超过两辆AGV，以尽量减少拥堵和冲突的情况发生。若在辅助道路中某方向道路上同一时间出现了3辆及以上的AGV，则需要重新规划路径。

(4)AGV处理完成该集装箱任务是指到其装载点装载该集装箱，并到其卸载点卸载该集装箱。

(5)假设所有AGV同时从各自第一个集装箱任务装载点出发。

(6)所有集装箱的优先级相同。

2.2 符号说明

As为调用的AGV集合，As={1,2,…,k,…}；

Cs为进出口集装箱的集合，Cs={1,2,…,p,…}；

NODE为节点集合，NODE={nod1,nod2,nod3,…}；

Dirpathau为辅助道路节点间有向道路的集合；

lop为集装箱p的装载点，p∈Cs；

uop为集装箱p的卸载点，p∈Cs；

αpk表示AGVk是否处理集装箱p，处理αpk=1，否则αpk=0，k∈As，p∈Cs；

opk表示AGVk处理集装箱p的顺序，此时αpk=1；

xi*表示从节点nodi到任意节点的有向路径；

x*j表示从任意节点到节点nodj的有向路径；

tin(xk)表示AGVk进入xk路径的时间；

tout(xk)表示AGVk离开xk路径的时间；

AdjMatrix,AdjMatrix=(disij)表示节点间的邻接矩阵，其中nodi和nodj为邻接节点时，disij为从节点nodi到节点nodj之间的距离，否则disij=0；

cfk表示AGVk满载时单位时间内所消耗的能量；

cek表示AGVk空载时单位时间内所消耗的能量；

2.3 数学模型

目标函数：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

tin(x)≥0，tout(x)>0，α,β∈0,1。

(14)

(15)

其中：式(1)中f是目标函数，目标是使得所有AGV的耗能之和最小，其中耗能的计算包括空载和满载两种情况下的计算；约束(2)确保每个集装箱的装卸有且仅由一个AGV处理；约束(3)保证每个集装箱的装卸任务都被完成；约束(4)～约束(7)为AGV在有负载和空载的情况下进入、离开所走道路时间之间的关系，约束(4)将AGV负载时进入道路时间之间的关系分为3种情况：①道路起始点为负载集装箱的装载点且该集装箱是该AGV第一个处理的，进入该道路的时间为0；②道路起始点并不是所负载集装箱的装载点，则进入该道路的时间为离开上一段道路的时间;③道路的起始点为负载集装箱的装载点，但该集装箱并不是该AGV第一个处理的，进入该道路的时间为到达装载点的时间加上装载集装箱的时间；约束(5)将空载时进入道路时间分为两种情况：①该道路的起始点不是AGV上一个处理的集装箱的卸载点，则进入该道路的时间为离开上一个道路的时间;②该道路的起始点是上一个集装箱的卸载点，则进入该道路的时间为离开上一个道路的时间加上卸载上一个集装箱的时间；约束(8)和约束(9)保证集装箱装卸处理先后顺序及集装箱处理顺序；约束(10)保证除了每个AGV的首发点和最终点，每个节点的出入度是一样的；约束(11)保证每个AGV所走路径都是可行的；约束(12)保证辅助道路密度要小于等于2；约束(13)表示进入辅助道路的时间要么是某个AGV在装卸某个集装箱的过程中进入该辅助道路的时间，要么是某个AGV在从上一个集装箱的卸载点到下一个集装箱的装载点过程中进入该辅助道路的时间；约束(14)和约束(15)为变量的约束。

3 算法设计

3.1 总体算法的设计

算法整体设计如图3所示。其中第一阶段算法中优化任务调度，所有AGV不论是否满足辅助道路密度约束，全部按照最短路径运输，第二阶段算法根据第一阶段算法输出的调度及路径重新规划路径，使路径在满足辅助道路密度的情况下使目标最小化。

为了避免在最优任务分配下，辅助道路冲突多，而主道路所耗时间长，重新规划的路径所花费时间过长，在第一阶段算法中保留3个较优任务调度，比较3个任务调度下路径重新规划后的目标时间，取时间最短的为最优调度，其对应的路径为该调度下最优路径。其中两个阶段算法在3.2节和3.3节中详细介绍。

3.2 考虑任务组合分解的灰狼优化算法

对于第一阶段算法中的任务调度，考虑当一个集装箱的卸载点和另一个集装箱的装载点相同时，将两个集装箱组合调度，即分配给同一个AGV并连续处理这两个集装箱，这样可以有效减少初始解的空间[17]。本文采用灰狼优化(Grey Wolf Optimizer,GWO)算法在最短路径下对任务调度进行求解，其中GWO算法的适应值为目标函数的负数。

3.2.1 GWO算法原理

因为本研究中的优化问题比较复杂，且在规模较大的情况下，传统优化算法缺乏可行性，所以考虑采用元启发式算法解决。灰狼优化(GWO)算法[28]是2014年提出的新的元启发式算法，在与一些著名元启发式算法进行实验对比下，GWO算法表现出了较高的性能[28]。GWO算法只需要调整两个参数，因此，对于大规模计算来说其速度非常有优势，且该算法采用了随机和固定两个操作来避免局部最优解，提高了算法的后期开发能力，有效避免了算法在局部最优停滞的情况，本研究中存在大量集装箱任务以及多极值情况，因此考虑求解速度以及解的质量GWO算法是十分合适的。

GWO算法灵感来自灰狼，该算法模拟灰狼群在自然界中的等级机制和狩猎机制。GWO算法认为α是最好的解，β、δ是第二、第三最佳解，其余解为ω，优化过程由α、β、δ引导，ω根据这3个解进行优化。优化过程如下：

A=2×a×r1-a。

(16)

C=2×r2。

(17)

Dα=|C1×Xα-X|,Dβ=|C2×Xβ-X|,Dδ=|C3×Xδ-X|。

(18)

X1=Xα-A1×(Dα),X2=Xβ-A2×(Dβ),X3=Xδ-A3×(Dδ)。

(19)

(20)

其中:t为当前迭代次数;A、C为系数向量，计算如式(16)和式(17)所示。其中a向量在迭代中每一维从2线性下降到0，r1、r2每一维是[0,1]中的随机向量，灰狼们位置根据Xα、Xβ、Xδ位置进行更新。算法的具体流程如下：

(1)初始化灰狼群的位置和各a、A、C向量。

(2)根据位置计算每个狼的适应值。

(3)根据适应值找到α、β、δ。

(4)根据式(18)～式(20)更新每个狼的位置并计算适应值。

(5)更新α、β、δ。

(6)更新各a、A、C向量。

(7)判断迭代终止条件是否达到，若未达到则转步骤(4),否则转步骤(8)。

(8)输出当前α即为最优解。

3.2.2 编码及解码设计

考虑第一阶段要解决任务调度问题,即要解决任务分配、处理顺序,编码采用实数编码,对每个待处理集装箱对应一个实数,按照集装箱编码的从大到小,将集装箱均匀地分配给序号从小到大的AGV,多出来的集装箱分配给序号最大的AGV,具体用下面的例子来说明。

现有10个待处理集装箱,3个AGV,假设编码如图4所示,按照规则,每个AGV先分配3个集装箱,多出来的1个集装箱分配给AGV3,本文将集装箱按照编码从大到小的排序,并按3∶3∶4分配给AGV1、AGV2、AGV3,且AGV处理集装箱的顺序也是按照从大到小的顺序,最终结果如图4所示。

由于编码长度与集装箱个数相同，当集装箱个数过多时会导致编码过长，若采取任务组合，可以使编码变短，同时初始解的空间也会减少。假设上述例子中10个集装箱的装卸点如图5上半部分所示，将一些集装箱根据规则组合起来，组合规则是：若集装箱a的卸载点与集装箱b的装载点相同，则组合起来的任务点就是集装箱a的装载点、集装箱a的卸载点(集装箱b的装载点)、集装箱b的卸载点，任务点是有顺序的，集装箱也有顺序，形成新的任务，新的任务序列中的每个任务由集装箱和任务点组成。

新的任务序列形成过程如下：

(1)初始时待组合序列中为所有集装箱，任务序列为空。

(2)在待组合序列中按顺序将每个集装箱的卸载点、装载点分别与排在它之后的集装箱的装载点、卸载点进行对比，若找到，则与找到的第一个匹配的集装箱组合放入任务序列中，并将两个集装箱从待组合序列中去除。

(3)若待组合序列中的集装箱没有可以组合的，则将剩下的所有集装箱插到任务序列的最前面，得到的即为最终新的任务序列。

按照以上步骤对10个集装箱进行组合，得到的新任务如图5下半部分所示，此时由原来的10个集装箱任务变成了6个任务，编码长度也从原来的10维变成了6维。当集装箱数量庞大时，因为装卸点个数有限，所以组合概率也会变大，编码长度有效减少，在第4章实验中也验证了此观点。

编码方式不变，但因为集装箱的组合，所以解码时还要将组合进行分解，得到AGV所分配的集装箱以及处理顺序，以上述组合为例，示例如图6所示。可以看到，根据上面的解码方法可以得到任务的分配及处理顺序，需要根据任务所对应的集装箱找到集装箱的分配及处理顺序。以AGV1为例，根据初步解码，需要处理的任务及顺序为5→2，由图6下半部分可以得到，任务5对应集装箱6、5，任务2对应集装箱7，按照任务及集装箱在任务中的顺序可以得到AGV1所分配到的集装箱及处理顺序为6→5→7。剩余AGV按照同样的方法解码，最终结果如图6所示。

3.2.3 算法步骤

根据前面两节的介绍，考虑任务组合分解的GWO算法的具体步骤如下：

步骤1将所有集装箱根据装卸任务点进行组合(如图4)，得到新的任务。

步骤2根据新的任务个数确定GWO算法中的编码长度即解的长度。

步骤3通过GWO算法进行求解任务调度，其中在计算某个解的适应值时，需要对其进行解码(如图5)，得到AGV相应的路径从而计算适应值。

步骤4通过步骤3所得到的最终解，通过解码得到AGV所走路径、所分配到的任务及其执行顺序，此时还需要将AGV所分配到的任务进行分解，对应于步骤1中的逆操作，得到AGV所分配到的集装箱以及其执行顺序。

需要说明的是，任务点之间的路径在这里按照最短路径规划。

3.3 基于Floyd的时间冲突预测算法

对于路径规划中，如果在任务调度确定的情况下，当前的最短路径不满足辅助道路密度限制，第二阶段算法则根据时间冲突预测规则修改参数，利用Floyd算法重新规划路径，使重新规划出的路径满足道路密度限制。

3.3.1 算法原理

Floyd算法是利用动态规划思想寻找给定的加权图中多源点之间最短路径的算法，是一种在具有正或负边缘权重的加权图中找到最短路径的算法。该算法的优点在于它可以算出任意两个节点之间的最短距离，但时间复杂度高，不利于计算大量数据。对于本研究来说，规划路径时起始点和终点对于不同集装箱是不同的，即需要知道任意两个节点之间的最短距离，并且路径节点数有限且规模小，因此该方法是适用于本研究的。

Floyd算法的基本步骤为：

(1)用G表示图的带权邻接矩阵，初始时所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

(2)定义矩阵D记录两点最短路径中必经节点，对于顶点u和v，判断是否有顶点w使得u到w再到v比已知的路径更短，若有则更新邻接矩阵G和矩阵D中有关信息。

(3)最终得到的邻接矩阵G记录了两点之间的最短路径距离，而根据矩阵D可以找到两点间的最短路径。

3.3.2 算法设计

具体设计如算法1所示:

算法1路径重新规划算法伪代码。

输入:原始邻接矩阵map，所有agv的路径agv.route，所有agv所分配的集装箱agv.con，所有集装箱的装卸点con.lp、con.up；

输出:agv.route重新规划后的路径。

1:[D, R] ← floyd(map); //原始邻接矩阵下最短路径信息

2:predict_set ← [agv1, agv2]；

3: k ← 3；

4:while 1 do

5: p ← 判断所有 agv 在当前路径下是否使辅助道路密度大于 2；

6: if p == 1 && predict_set 中不包含所有 agv then

7: conflict ← predict_set 中使得辅助道路密度大于等于 2 的时间段集合；

8: predict_set = [predict_set, agvk]；

9: agvk.route = []； //将 agvk 中的路径清空，重新规划

10: a = agvk.con；

11: i = 1； //从处理第一个集装箱开始

12: s = a(i).lp； //以装载点为起点

13: e = a(i).up； //以卸载点为终点

14: tag = 0

15: while 1 do

16: map1 = map；

17: for 遍历每个辅助道路 L do

18: tp_L ← 以s为起点、t为起始时间，基于R预测通过辅助道路L的时间段

19: for 遍历 conflict(L) 中的每个时间段 t_c do

20: if tp_L 的时间段与 t_c 有重合 then

21: map1(L(1), L(2)) = map1(L(1), L(2)) + M； //增加该道路权重

22: end if

23: end for

24: end for

25: [D1, R1] ← floyd(map1)；

26: route ← 根据 R1、s、e 重新求解该段路径

27: agvk.route = [agvk.route, route]；

28: if tag==0 then

29: if i == length(a) then //所有集装箱任务都规划完毕

30: break；

31: else

32: s = a(i).up；

33: e = a(i + 1).lp；

34: tag = 1；

35: end if

36: else

37: i = i + 1；

38: s = a(i).lp；

39: e = a(i).up；

40: tag = 0；

41: end if

42: end while

43: k ← k + 1；

44: else

45: return agv.route；

46: end if

47:end while

算法基本步骤如下：

步骤1已知所有AGV的任务调度及初始运输路径，图的原始邻接矩阵，初始预测集中只有前两个AGV。

步骤2根据所有AGV当前的运输路径，判断是否使得辅助道路的道路密度大于2，是则转步骤3,否则转步骤8。

步骤3计算预测集中的AGV在其规定的路径下处理所有集装箱时，各个辅助道路上的道路密度，记录道路密度大于等于2时的时间段，形成该辅助道路的冲突集合。

步骤4加入新的AGV到预测集中，其路径重新规划所以置为空，记起点为第一个要处理集装箱的装载点，终点为其卸载点，当前时间记为0。

步骤5邻接矩阵设为原始邻接矩阵，通过当前时间及起点，预测AGV通过辅助道路的时间段，若与其对应的冲突集中的时间段重合，则增加邻接矩阵中该辅助道路的权重。所有辅助道路判断完成后，将得到的新的邻接矩阵重新通过Floyd算法计算最短距离，并根据起点和终点产生路径插到该AGV路径的最后面，现在的时间更新为到达终点的时间。

步骤6若该AGV所有集装箱都处理完毕，即已经规划出新的路径，则转步骤2，否则转步骤7。

步骤7若刚刚的起点和终点是处理完毕最后一个集装箱的装卸点，则现将起点设为该集装箱的卸载点，终点设为下一个待处理集装箱的装载点；否则将起点和终点设为下一个待处理集装箱的装卸点，转步骤5。

步骤8所得路径则为满足道路密度约束的路径。

其中辅助道路密度大于等于2的时间段集合包括每一种使得该辅助道路密度大于等于2的情况下的时间段，这个时间段是指：第2个AGV进入该辅助道路的时间到第1个AGV离开该辅助道路的时间，其中这里的第1、第2是按照AGV进入该辅助道路的时间，按照由先到后进行排序所得。因为无论之后有哪个AGV从进入到离开该辅助道路的时间与该时间段重合都会使得该辅助道路密度大于2，所以以这个时间段集合来进行预测。又因为主道路上不存在道路密度的问题，所以该算法一定可以规划出满足辅助道路密度限制的路径。

4 实验结果

本章研究了任务组合操作对算法的影响及第二阶段算法中路径规划的正确性，比较了在不同元启发式算法和各种问题规模下总体算法的最终结果与运行时间，对比了不同算法的收敛情况以及解的质量。本文算法是在MATLAB R2018b中实现的，所有实验都是在Windows 10操作系统下使用AMD Ryzen 7 4800U with Radeon Graphics 1.80 GHz和16 GB RAM的计算机进行的。

4.1 参数设置

本研究的AGV运输速度、运输道路长度参考厦门远海自动化码头，AGV的运输速度为5 m/s，AGV空载时消耗0.7 kWh，负载时消耗2 kWh，运输道路长度为240 m，宽度为100 m，其中辅助道路之间的距离为30 m，AGV在码头起重机(Quay Crane,QC)处装卸集装箱时，时间为10 s,AGV在堆场处装卸集装箱时，时间为5 s。考虑装卸集装箱数量从5～5000个不等，AGV数量从2～30个不等，QC数量8个，堆场数量8个，集装箱的装卸点随机产生。为了使算法进行公平比较，所有算法的编码解码方式相同，群规模及最大迭代次数相同。算法中的具体参数设置如下：粒子群优化(Particle Swarm Optimization,PSO)算法中:c1=c2=1,w=1;社会学习型粒子群(Social Learning PSO,SL_PSO)算法中:a=0.5,b=0.01。

4.2 任务组合的影响及路径规划正确性

在相同任务下，将集装箱任务经过组合分解所产生的最终解与直接参与调度产生的最终解进行比较，结果如表1所示。可以看到，随着集装箱数量的增大，编码长度的差距也在增大，最大差距达到了50%左右，目标值在小的问题规模下差距不大，但随着规模的增大，目标值的差距就达到了11%左右。从结果可以得出，将任务先组合后再求解可以有效减少编码长度，优化求解结果。

表1 任务组合与否比较结果

下面需要验证所求结果是否满足辅助道路密度约束，即第二阶段算法中道路规划的正确性，以集装箱100个，AGV 9个规模为例，第一阶段算法所得AGV随时间所走辅助道路如图7所示，图中纵坐标为辅助道路中的有向道路，横坐标为时间。可以看到，不是所有辅助道路密度都满足小于等于2这个条件，例如：①在450 s左右的时间段上，在15→20这条道路上AGV1、AGV4、AGV7、AGV9在时间上是有重叠的，即道路密度为4大于2；②在570 s、580 s左右的时间段上，在32→3这条道路上AGV3、AGV8、AGV9之间，AGV3、AGV7、AGV9之间在时间上有重叠，道路密度为3大于2。将所有AGV路径经过第二阶段算法重新规划，得到的结果如图8所示，可以看到每条道路上至多有两个AGV在时间段上有重合，其中在上文中所列举不满足密度条件的例子，在进行重新规划路径后情况如下：①目前只有AGV1、AGV4有时间重叠；②目前是分别只在两个AGV之间有时间重叠，分别是AGV8和AGV3，AGV7和AGV3，AGV7和AGV1。可以看到，重新规划后所有辅助道路密度都满足了小于等于2的条件，即路径重新规划成功，第二阶段算法有效。

4.3 总体算法实验

为了验证总体算法在不同规模下的有效性，进行了以下实验：在不同问题规模，总体算法框架不变的情况下将GWO算法分别替换成PSO算法、SL_PSO算法、蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)，在相同种群数量及最大迭代次数下运行30次，其中每种问题规模下的30次运行都是对同一随机产生的集装箱任务进行的，比较其运行结果如表2和表3所示，表2为CPU运行30次的平均运行时间，表3为30次运行结果的平均值。这4种算法都为群智能算法，其中PSO算法、SFLA是较早提出并应用广泛的，SL_PSO算法是对PSO算法的改进，和GWO算法一样是较新提出的算法。

由表2可知，GWO算法CPU运行时间小于其他3个算法，特别是在大规模问题中，GWO算法的优势更加明显，例如集装箱个数为2 000时，GWO算法的CPU运行时间相比于其余算法减少了8.10%～56.22%。由表3可知，GWO算法的结果基本上均为4个算法中的最优，即使不是最优也是次优，并且与最优的结果相差不大。

表2 CPU平均运行时间的对比 s

表3 平均目标值的对比 kWh

如图9所示，比较了各算法的收敛情况,其中图9a～图9d分别表示在集装箱—AGV个数为30-4、100-9、800-16、1000-20，最大迭代次数为300、400、500、600的情况下的收敛图。可以观察到，GWO算法的收敛时间是随着规模的增大而增大的，收敛的值相比其余算法更优。可以看到，在迭代初始阶段，GWO算法的收敛速度较快，即在探索阶段，GWO算法的全局搜索能力在4个算法中较优，特别是在图9a和图9b中，可以看到GWO算法在迭代前期目标值下降速度非常快。而在迭代后期，可以看到GWO算法的开发能力也是较优的，在图9中有些算法过早收敛，陷入局部最优，可以看到GWO算法因全局搜索能力较优，所以在别的算法已经收敛的情况下，GWO算法虽然还未收敛，但其值也较优，并且在较优的值情况下，GWO算法的局部搜索能力即开发能力使其在迭代最后可以找到比其他算法都要优的值，如图9c和图9d所示。综上所述，本文所设计总体算法在解决该问题上无论是小规模还是大规模问题都是较好的。

5 结束语

本文考虑了自动化集装箱码头上AGV的调度和路径规划，使得在降低冲突发生的情况下AGV能量消耗最少。通过实验可以看出，所设计算法的有效性，先将集装箱任务组合，可以有效优化算法所求得的结果，所提出的GWO算法与PSO算法、SL_PSO算法、SFLA算法相比，运行时间短，并且在各种规模下都有良好的结果，是更有效、更可靠的算法。

在本文中考虑装卸情况时，没有考虑AGV多载的情况，未来的研究可以考虑AGV装载两个及以上集装箱的情况。在AGV路径规划中，本文只考虑了辅助道路密度问题，今后可以考虑更多可能产生冲突的情况，以更大地降低冲突发生的可能性；运算时间在大规模集装箱下不够快，未来也可以考虑并行运算，从而减少运行时间。