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

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

宫文新

身份证证号：1522011983****2514

摘要：设计算法能有效减少编码长度，得到的结果质量、运行时间和收敛情况都优于其他算法所得，该算法能够有效地解决不同规模下多AGV的调度和预防冲突的路径规划问题，减少AGV的能量消耗。

关键词：自动化集装箱码头；多自动引导小车调度；路径规划；

对自动化集装箱码头上多自动引导车（AGV）的调度和路径规划问题，在考虑AGV负载以及冲突的情况下，建立了以最小化AGV能量消耗为目标的数学模型。设计了两个阶段的算法对模型进行求解，第一阶段基于任务组合分解，利用灰狼优化算法在最短路径下优化AGV调度，第二阶段对于较优的AGV调度，进一步利用基于FIoyd的时间冲突预测算法对其路径进行优化，以达到预防冲突的结果。

一、总体算法的设计

算法整体设计如图1所示。其中第一阶段算法中优化任务调度，所有AGV不论是否满足辅助道路密度约束，全部按照最短路径运输，第二阶段算法根据第一阶段算法输出的调度及路径重新规划路径，使路径在满足辅助道路密度的情况下使目标最小化。为了避免在最优任务分配下，辅助道路冲突多，而主道路所耗时间长，重新规划的路径所花费时间过长，在第一阶段算法中保留３个较优任务调度，比较３个任务调度下路径重新规划后的目标时间，取时间最短的为最优调度，其对应的路径为该调度下最优路径。

图1总体算法流程图

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

1.ＧＷＯ算法原理。ＧＷＯ算法只需要调整两个参数，因此，对于大规模计算来说其速度非常有优势，且该算法采用了随机和固定两个操作来避免局部最优解，提高了算法的后期开发能力，有效避免了算法在局部最优停滞的情况，本研究中存在大量集装箱任务以及多极值情况，因此考虑求解速度以及解的质量ＧＷＯ算法是十分合适的。ＧＷＯ算法灵感来自灰狼，该算法模拟灰狼群在自然界中的等级机制和狩猎机制。ＧＷＯ算法认为α是最好的解，β、δ是第二、第三最佳解，其余解为ω，优化过程由α、β、δ引导，ω根据这３个解进行优化。

2.编码及解码设计。考虑第一阶段要解决任务调度问题，即要解决任务分配、处理顺序，编码采用实数编码，对每个待处理集装箱对应一个实数，按照集装箱编码的从大到小，将集装箱均匀地分配给序号从小到大的AGV，多出来的集装箱分配给序号最大的AGV。现有10个待处理集装箱，３个AGV，按照规则，每个AGV先分配３个集装箱，多出来的１个集装箱分配给AGV３，将集装箱按照编码从大到小的排序，并按３:３:４分配给AGV１、AGV２、AGV３，且AGV处理集装箱的顺序也是按照从大到小的顺序，由于编码长度与集装箱个数相同，当集装箱个数过多时会导致编码过长，若采取任务组合，可以使编码变短，同时初始解的空间也会减少。将一些集装箱根据规则组合起来，组合规则是：若集装箱ａ的卸载点与集装箱ｂ的装载点相同，则组合起来的任务点就是集装箱ａ的装载点、集装箱ａ的卸载点（集装箱ｂ的装载点）、集装箱ｂ的卸载点，任务点是有顺序的，集装箱也有顺序，形成新的任务，新的任务序列中的每个任务由集装箱和任务点组成。

3.算法步骤。根据前面两节的介绍，考虑任务组合分解的ＧＷＯ算法的具体步骤如下：步骤１将所有集装箱根据装卸任务点进行组合，得到新的任务。步骤２根据新的任务个数确定ＧＷＯ算法中的编码长度即解的长度。步骤３通过ＧＷＯ算法进行求解任务调度，其中在计算某个解的适应值时，需要对其进行解码，得到AGV相应的路径从而计算适应值。步骤４通过步骤３所得到的最终解，通过解码得到AGV所走路径、所分配到的任务及其执行顺序，此时还需要将AGV所分配到的任务进行分解，对应于步骤１中的逆操作，得到AGV所分配到的集装箱以及其执行顺序。需要说明的是，任务点之间的路径在这里按照最短路径规划。

三、基于FIoyd的时间冲突预测算法

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

1.算法原理。FIoyd算法是利用动态规划思想寻找给定的加权图中多源点之间最短路径的算法，是一种在具有正或负边缘权重的加权图中找到最短路径的算法。该算法的优点在于它可以算出任意两个节点之间的最短距离，但时间复杂度高，不利于计算大量数据。对于研究来说，规划路径时起始点和终点对于不同集装箱是不同的，即需要知道任意两个节点之间的最短距离，并且路径节点数有限且规模小，因此该方法是适用于本研究的。FIoyd算法的基本步骤为：（１）用Ｇ表示图的带权邻接矩阵，初始时所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。（２）定义矩阵Ｄ记录两点最短路径中必经节点，对于顶点ｕ和ｖ，判断是否有顶点ｗ使得ｕ到ｗ再到ｖ比已知的路径更短，若有则更新邻接矩阵Ｇ和矩阵Ｄ中有关信息。（３）最终得到的邻接矩阵Ｇ记录了两点之间的最短路径距离，而根据矩阵Ｄ可以找到两点间的最短路径。

2.算法设计。算法基本步骤如下：

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

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

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

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

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

步骤６若该AGV所有集装箱都处理完毕，即已经规划出新的路径，则转步骤２，否则转步骤７。步骤７若刚刚的起点和终点是处理完毕最后一个集装箱的装卸点，则现将起点设为该集装箱的卸载点，终点设为下一个待处理集装箱的装载点；否则将起点和终点设为下一个待处理集装箱的装卸点，转步骤５。

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

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

参考文献：

［１］刘有勇，自动化集装箱码头自动导引小车与轨道式龙门起重机的协同调度.2020.

［2］王宏宇，分析集装箱码头上多自动引导车的调度和路径规划.2022.