基于离散鲸鱼优化算法的仓储物流AGV路径规划

张维君，薛成玉

（沈阳航空航天大学 计算机学院，辽宁 沈阳 110136）

0 引言

物流业的迅猛发展使得物流仓储在快递行业中的地位愈发重要，而自动导引车（AGV）因自动化、高柔性、高可靠性以及并行作业等特点，已成为物流运输中的重要工具，越来越多的物流仓储采用AGV进行运输，这极大便利快递的分拣。然而，当AGV数量增时，受作业环境、机器故障、操作失误、道路容量等影响会使得AGV出现死锁、碰撞等问题，这些问题严重制约AGV的运输效率，影响整个仓储的调度甚至造成系统瘫痪。AGV的路径规划和冲突的处理一直是研究领域的热点问题，路径规划是AGV在仓储环境内运行，找出一条满足约束的可行路径，冲突处理要求多AGV的路径是无冲突最优的。智能优化算法在处理路径规划问题时有着很高的计算性，许多智能优化算法被用于路径规划方面研究，例如：遗传算法、粒子群算法、模拟退火算法、鲸鱼优化算法、灰狼算法等。Lyu，等提出将一种带时间窗的Dijkstra算法相结合到遗传算法中解决无冲突路径规划问题；Cong提出将蚁群优化算法用于机器人路径规划上，并根据一组给定的映射证明所提出的方法的有效性。鲸鱼优化算法于2016年被提出。因其参数少、结构简单、搜索能力强等优点，大量学者对鲸鱼优化算法进行了研究。Zhou，等提出基于Lévy飞行轨迹的鲸鱼优化算法（LWOA），引入Lévy飞行轨迹促进算法跳出最优，在开发和利用之间取得更好的平衡；刘磊，等引入自适应权重和变螺旋位置更新策略提高寻优能力，引入最优邻域扰动策略跳出局部最优；刘小龙提出一种多种群纵横双向学习的种群划分思路，向纵横两向寻找最优值，避免局部最优。以上都是鲸鱼优化算法在处理连续优化问题的研究，在组合问题上的研究较少。但是，当AGV数量增多时，冲突问题随之而来。国内外学者针对多AGV冲突问题做了大量研究，Saidi-Mehrabad，等提出JSSP和CFRP组合的数学模型并用一种两阶段蚁群算法（ACA）求解车间调度无冲突路径问题；Yang，等针对码头无冲突路径研究，建立一个基于路径规划、集成调度、冲突和死锁的混合整数规划模型；Miyamoto，等建立整数规划模型，并用局部随机搜索进行有容量约束的AGV系统的调度和无路径冲突问题求解。

上述研究增强了人们对鲸鱼优化算法和AGV冲突的认知，为AGV系统路径规划和避障提供了思路。但在离散化WOA和无冲突路径上仍有不足，提出DWOA算法和基于预约表的避障策略。首先，由于传统鲸鱼算法在解决离散化问题上的不足，提出DWOA算法用于AGV的路径规划；然后，结合避障策略，通过预约表实现对冲突的预测。最后，通过仿真实验，证明基于预约表的避障策略可有效预测冲突，DWOA算法在仓储物流可以完成路径规划，并在路径规划时耗费时间缩短17.3%。

1 问题描述和数学模型

1.1 多AGV系统的路径规划模型

物流仓储内多AGV系统的工作可以描述为：多AGV共享同一仓储环境，将仓储内货物根据分配规则从货架运送到相应的卸货区。无冲突路径规划可以描述为：找到多AGV系统内满足约束的无冲突路径。为便于对多AGV进行路径规划，采用栅格法为仓储内环境进行建模，将工作区用平面图清晰表示。栅格法将AGV的工作空间分为只有白的和黑色的网格单元，如图1所示为一个20×20的栅格图，白色区域为可通行区域，用1表示，黑色区域代表障碍区域不可通行，用0表示。将AGV小车视作可在栅格内直径远小于栅格单位尺寸的可移动圆，其可行区域为以AGV为中心的八邻域区域的白色栅格。并将仓储内的AGV、货物、卸货区转化为环境模型中的节点。为方便建模，对AGV车辆和地图做如下假设：

图1 栅格地图

（1）AGV车速不变，电量充足，取货放货时间忽略不计；

（2）AGV为单作业模式，每次只可搬运一个货物，完成后方可接受其他任务；

（3）地图内AGV可双向行驶，转弯时间固定；

（4）考虑AGV中途损坏情况；

（5）每个栅格同一时刻只容纳一个AGV，且确保大小可通过单位栅格。

AGV系统是多个AGV组成的系统，为保证所有AGV到达目标点的情况下使得总时间最短，目标函数式为：

将栅格地图中节点分为3类：开始节点、终止节点、和路径节点，对AGV和地图做如下假设：

（1）每个路径节点一次最多容纳一个AGV；

（2）每个AGV在起始节点上的时间约束。

1.2 多AGV冲突问题描述

在AGV系统中当多AGV被规划出路径后，多AGV将按照规划出的路径执行任务，仓储内容量有限，多AGV一起行动将出现冲突等问题，这使得仓储内的运输效率降低。为解决上述问题，通常将冲突类型分为四类，相向冲突、障碍物冲突、节点冲突和多机冲突。冲突类型具体描述为：

（1）如图2(a)所示为相向冲突，两个相对方向行驶的AGV小车的下一个路径节点为同一个的节点；

（2）如图2(b)所示为障碍物冲突，故障AGV或者掉落货物占据一个可通行节点，阻碍行驶中的AGV；

（3）如图2(c)所示为节点冲突，两个不同方向AGV下一个节点为同一节点；

（4）如图2(d)所示为多机冲突，多个不同方向AGV的下一节点为同一节点。

图2 冲突类型

本章的研究目标是建立一个多AGV系统的无冲突路径规划模型。将仓储物流内部工作情况简化成一个二维平面图，实现对环境的建模；以完成时间最短为任务目标，建立对栅格、AGV和任务的约束；对节点冲突进行描述，为解决冲突问题做准备。

2 基本鲸鱼优化算法（WOA）

鲸鱼优化算法是一种新型的启发式搜索算法，该算法模拟座头鲸的狩猎行为进行复杂问题的寻优。算法中每条鲸鱼位置都代表一个可行解，算法包含收缩包围、泡泡网攻击和寻找猎物三种不同搜索方式。

（1）收缩包围。座头鲸在搜索猎物时，识别猎物位置并包围猎物。WOA算法模拟该行为时，以最优个体为参照，逐渐向着最优方向靠拢，并更新位置，其数学模型为:

其中，t表示当前迭代次数；X*(t)表示最优解的位置向量；X(t)表示当前个体位置向量；D表示最优个体和当前个体之间的距离；系数向量A、C的公式为：

其中，a代表收敛因子，随迭代从2到0线性递减；→是[0，1]内的随机向量。

（2）螺旋更新机制。当座头鲸找到猎物后，不断收缩包围圈并以螺旋形式游向猎物，其更新位置的数学公式为：

其中，→为当前鲸鱼和猎物之间的距离；b为定义螺旋形状的一个常数，为处于[-1,1]间的常数。

（3）随机搜索。在座头鲸未确定猎物位置之前，鲸鱼个体会以彼此之间的位置为参考随机搜索更合适的猎物。其数学模型为：

初始时的鲸鱼群随机均匀分布在搜索空间，|A|可以决定鲸鱼群在更新位置时的方向，|A|＞1时，为全局搜索阶段，采用随机搜索方式，扩大种群搜索范围；|A|＜1时，座头鲸处于局部开发阶段，利用收缩包围和螺旋更新方式缩小搜索范围靠近猎取，其概率各50%。

3 算法设计

原始鲸鱼算法善于处理连续优化问题，而路径规划问题属于组合问题，在路径的搜索时需离散化处理，因此需重新定义鲸鱼算法的随机搜索、螺旋更新以及收缩包围三个阶段。

3.1 改进随机搜索策略

在基本鲸鱼优化算法的随机搜索阶段中，鲸鱼以种群内随机个体位置为指导进行对空间的探索，更新鲸鱼个体位置时是随机的，是全局搜索阶段。不影响全局搜索的前提下，根据随机特性模仿鲸鱼优化算法的随机搜索阶段，步骤为：

（1）在当前序列X中随机找到两个节点z1和z2；（2）对z1节点进行加一操作，对z2进行减一操作；

（3）将z1节点和z2节点间的序列连接通顺；

（4）替换掉当前序列中z1和z2间的序列。

3.2 改进螺旋更新和收缩包围策略

在基本的鲸鱼优化算法中，由于收缩包围和螺旋更新总是朝着当前最优方向更新，因此最优位置的周围会存在更多的优秀的解，使得最优解只存在于最优解所在的局部位置，这使得种群丧失多样性，为更好地发掘最优解，提高其搜索能力，增强种群的多样性，且保留收缩包围和螺旋更新的特性。

螺旋更新阶段是鲸鱼个体以螺旋形状向着最优驱赶猎物的过程，步骤为：

（1）找出当前序列X和最优序列X*相同节点集合Q，在集合Q中随机搜索两个不同数r1和r2；

（2）找到r1和r2位于两个序列中的位置序号z1、z2和z3、z4；

（3）将最优个体中z3和z4节点间的路径移动到当前序列的z1和z2节点间,最优序列保持不变。

收缩包围阶段为当前鲸鱼个体向着最优个体方向攻击猎物，步骤为：

（1）找出当前序列X和最优序列X*不同集合Q，在集合Q中随机搜索1个数r；

（2）找到r位于两个序列中的位置序号z1和z2；

（3）对比z1和z2在栅格地图中的上下位置；

（4）将栅格地图以z1横坐标为中心，将栅格地图分为上下两部分，当z2位于z1上半部分时，z1进行加一操作，否则进行减一操作。

3.3 预约表的设计

为解决多个AGV导致的冲突问题，设置一个预约表，表内存储每个AGV的当前位置节点、下一个位置节点，以及邻域内可通行节点以及整条路径节点信息。当系统生成路径后AGV开始行动，此时通过各个预约表间的对比，预测路径内各个小车的冲突，及时规划出避障方案。面对不同冲突类型，避障策略如下：

（1）相向冲突。后续路径节点长的进行重新路径搜索策略,后续节点短的继续。

（2）节点冲突。当有连续相同节点时，停车等待策略会增大停车时间，浪费AGV和节点的资源，因此后续路径节点长的进行重新路径搜索策略；当相同节点只有一个时，表明两条路径冲突节点的下一个节点在相反方向，因此后续路径短的进行停车等待策略。

（3）障碍物冲突。标记此处障碍并通知管理员，重新搜索该AGV路径，待管理员移开障碍物后取消此处标记。

（4）多机冲突。此时同一个节点附近有多个冲突类型，先判断都属于哪种类型，先处理节点冲突，再处理相向冲突。

碰撞检测及避障策略流程图如图3所示。

图3 碰撞检测及避障策略流程图

3.4 路径规划及避碰策略流程

（1）环境建模。依次给每个AGV分配任务，按照分配先后进行路径规划。

（2）路径规划。

①初始化算法的相关参数：种群大小、最大迭代、问题维度等；

②对种群进行评价，计算种群内每个个体的适应度，找出全局最优解；

③遍历种群，生成随机数p，若p＞0.5，转为步骤④，否则转为步骤⑤；

④改进随机搜索策略；

⑤若|A|＞1，进行改进螺旋更新策略；否则，进行改进收缩包围策略；

⑥对种群进行重新评价，更新全局最优解；

⑦重复以上步骤，直至迭代结束。

（3）预约表设计以及避障策略。预约表跟随路径中的AGV的移动而时刻变化，比较预约表，若存在冲突问题，根据避障策略进行调节，并再次比较，直至路径无冲突。

4 仿真实验及结果分析

对DWOA算法和基于预约表的避障策略进行可靠性和有效性分析。在20*20的栅格内进行仿真实验。初始化任务见表1。

表1 初始化任务图

表2为采用DWOA算法规划的路径结果以及避障策略。根据预约表可知AGV1和AGV2在节点68处将处发生碰撞，AGV1和AGV3在节点108处发生碰撞。

表2 AGV路径结果及其避障策略

由冲突类型可知两个冲突均为节点冲突，68和108处碰撞处AGV1的后续节点多，因此AGV1进行等待。DWOA路径规划图如图4所示。

图4 DWOA路径规划图

为验证DWOA的有效性，用相同起始点（6，299）进行路径规划，将遗传算法和DWOA进行比较，图5、图6为DWOA、GA进行路径规划求解30次后，取最优一次的运行结果的最优完工时间收敛图和平均完工时间收敛图。由图5可知，DWOA在第19次达到最优，GA在32次达到最优，就收敛结果看，DWOA拥有更好的迭代速度，迭代次数更短。由图6可知，DWOA在40代时达到最优，DWOA收敛性明显优于GA，收敛结果也优于GA。

图5 最优完工时间收敛图

图6 平均完工时间收敛图

由表3可知：DWOA寻找最优解耗费时间比GA减少17.3%。求解最优解的迭代次数比GA减少36.7%，求解平均解迭代次数比GA减少了43%，提高了算法的收敛速度。由以上数据可知，DWOA在路径规划方面上收敛速度和寻优能力优于GA。

表3 DWOA和GA对比表

通过在20×20栅格地图上进行仿真证明了DWOA算法在仓储物流路径规划上的有效性，在冲突时可通过预约表有效预测冲突，并解决冲突。

5 结语

提出一种DWOA算法，并将路径规划和冲突综合考虑，在提高路径规划的实时性和有效性同时，通过冲突预判减少冲突的发生。在考虑AGV系统的冲突问题导致的作业运输效率低的问题上，建立以最小化完成时间为目标的AGV路径规划模型。仿真实验表明，该算法可以解决仓储物流内多AGV系统无冲突路径规划问题，使得AGV系统中AGV运输任务时大大缩短运输时间，提高AGV运输效率，从而提高仓储物流的分拣效率。

对AGV的规划是在基本作业环境和任务分配已知的情况下，而真实的情况可能更加复杂，比如工作场景中可能需要考虑磁道损坏，搬运的货物过小造成AGV的浪费，以及AGV电量和损坏等问题，有效解决以上问题将是未来研究的一大方向。