基于混合蚁群粒子群的多AGV路径规划研究

魏宏源，茅 健

（上海工程技术大学 机械工程学院，上海 201620）

0 引言

近年来，工业4.0战略规划在促使整个工业生产体系进入全新的水平。作为工业4.0的核心组成部分，智能物流是连接客户、供应链和制造业的重要环节，也是构建未来智能工厂的基石[1,2]，自动导引运输车（AGV）是智能物流中重要设备之一[3]。其路径的好坏决定了仓库的运作效率，因此对AGV路线的规划也成为了研究热点，国内外学者已经做出了很多贡献。

刘高强[4]等人通过引入变异算子优化遗传算法，对AGV的路径分配进行优化，得到了更为优化的小车路径。汤旻安[5]等人利用改进的量子微粒群算法，克服了传统算法陷入局部最优的问题，对小车路径优化提出了改进。王娜[6]以VB6.0为开发系统，混合Matlab编程解决了AGV在路口的交互碰撞问题。王立春[7]等人结合实际情况，在A*算法中引入拐弯系数，提高了实际运行效率。WaldemarMa.opolski[8]把制造系统的资源数量和AGV的数量作为优化的对象，利用软件模拟对AGV的数量与成本进行了优化。Spyros A. Reveliotis[9]对传统的无冲突小车路径进行优化，针对AGV资源分配系统的类别开发了一种适合的结构控制策略。S. RAJOTIA[10]等人应用Dijkstra算法寻找车辆最不拥堵的最快路线，并且对双向流动路径进行了仿真研究，所提出的策略有助于减少车辆阻塞时间，提高系统的吞吐量潜力。

本文根据立体库的实际情况，基于混合蚁群粒子群方法，建立了多台AGV小车路径快速分配与优化模型，对多AGV小车路径优化问题进行研究，结果表明该方法可以加快AGV小车在仓库运输的速度，提高智能仓储的物流传输效率。

1 问题描述与建模

一般情况下，在立体货仓中，产品由滚筒线推送至分道口，触发AGV小车搬运货物至立体仓库中，整个过程可以细分为滚筒线运输货物，触发光电开关分配小车任务，小车搜寻路径将货物送至仓库中，如图1所示。

图1 立体仓库入口

AGV小车在接收到任务后，首先由起始位置到接受货物位置，然后从接受货物位置送货至指定货架，最后回到原来车库中。第一步任务中为单一路径，优化空间较少；第二步中为已知起点与终点的路径寻优问题。若利用传统的A*算法进行路径优化，会出现车辆排队，相互管制等问题，而且AGV的路线利用率较低。在以往AGV的路径寻优中，这种问题被归属于旅行商问题，即希望小车在到达货架后回到原来的车库，走过的路径最短。

在路径优化中，为了排除一些外界因素的影响，模型首先需要有以下假设：

1）车间的AGV总数为定量，忽略AGV的一些硬件故障问题。

2）路线的起终点已知，仓库中地图已知。

3）分配任务或者下达指令后无网络延迟问题，小车及时响应控制系统下达的命令。

4）所有AGV的起点均在充电桩或者车库，而且在运行中速度相同。

现在假设车间中有x辆AGV（x≥5），同时发出的任务数为k，每辆AGV为了完成任务都要走不同的路程。而且对于不同的任务，对应的路线也不一样。设Dmn为第m（m≤x）辆车执行第n（n≤k）个任务所要走的距离。AGV路径优化的目标在于使得这k个距离之和为最小值，目标函数如式(1)所示。同时，模型还需要满足同一时间一辆AGV仅有一个任务,这个可以在AGV控制系统中实现。同时对于多台AGV调度，在执行相近任务的时候每辆车的路径不能相同，如式(2)所示。

多AGV路径优化可视为一种特殊的旅行商问题（TSP），它也是组合优化中的一个困难的NP问题。如果不能很好的处理该问题，会导致车辆互锁，甚至碰撞等问题，如图2所示。1号AGV与2号AGV由于路径规划不好，面对面的行驶，最终两辆车发生互锁，都无法继续行驶。

因此，本文基于混合蚁群粒子群算法，提出了一种优化算法，改善AGV小车的路径规划问题，同时根据现场规划找出合适的返回路线，避免交通异常。

2 混合蚁群粒子群算法

2.1 蚁群算法

蚁群优化算法（ACO）[11]是由意大利学者Dorigo M提出的一种模仿蚂蚁觅食的新兴群智能算法。该方法利用蚂蚁在路上留下的信息素含量来判断路径的优化程度，具有正反馈与分布协作式的特点。

一般地，蚁群算法表述为：初始时刻有m个蚂蚁随机分布，并保证没有蚂蚁在同一位置。设在0时刻，各条路径上的信息素量τij（0）=const（const为常数），蚂蚁n（n=1，2，…，m）根据不同路上所含有的信息素含量决定路线。同时为了避免路径重复，往往在运动过程中使用禁忌表Ttabu记录当前蚂蚁走过的位置，先假设t时刻，蚂蚁n从位置i转移到位置j根据状态转移概率（t）决定；

式(4)中τij（t+n）为信息素更新函数， 1-ρ为信息素残留因子，ρ∈（0，1）； Δτij（t）表示蚂蚁在经过路径（i，j）时在本次循环中的信息素增加量。当t=0时Δτij（t）=0。

图2 AGV互锁现象

2.2 粒子群算法

粒子群算法（PSO）是一种基于鸟群智能的随机优化技术，也叫做鸟群算法，该算法具有群体智能、内在并行性、迭代格式简单、可快速收敛到最优解等优点[12]。PSO算法的优势在于可以较为简便的求出多个粒子共存或合作时的最优解。其优化思想在于对于每个粒子都有自己的速度与位置，粒子们在自己速度影响的同时也追随当前最优的粒子，从而迭代得到最优值。

定义单个粒子在飞行过程中所获取的最优解为个体最优解（pBest），在整个粒子群所获得的最优解记作全局最优解（gBest），用N维速度Vi=（vi1，vi2，…，viN）与位置Pi=（pi1，pi2，…，piN）进行粒子状态的表示，在算法中不断的通过自身速度与位置进行状态更新，可以产生新一代群体。

该方法的具体实现流程如下：

步骤1：粒子群初始化，将粒子群中各个参数设置好；步骤2：在适应度函数的基础上，将每一个粒子适应度值表示出来；步骤3：将粒子的当前适应度值与历史最优适应度值比较，更新历史最优值；步骤4：将当前适应度与种群历史最优位置适应度值比较，更新历史最优值；步骤5：运用方程(5)与方程(6)进行计算；步骤6：若获得最优值，则输出最优值结果，否则跳转步骤2继续进行迭代。

2.3 混合蚁群-粒子群算法

粒子群的优点在于其全局搜索能力强，参数的更新比较容易，搜索速度比较快，其缺点在于算法在前期求解速度较慢，而且容易早熟收敛。蚁群算法的优点在于信息素的存在，使得算法拥有正反馈的特性，缺点在于传统的蚁群算法计算量大，耗时较长。

在衡量了两个算法的优缺点之后，混合算法首先派出蚂蚁在全局进行搜索，然后结合粒子群算法，让蚂蚁在信息素与最优蚂蚁两者的作用下进行路径寻优。算法的主要实现步骤如下：

1）初始化蚁群算法与粒子群算法参数，让蚁群随机分布在求解空间内。

2）根据贪婪算法生成信息素分布，让蚁群按照信息素含量去更新位置。

3）记录蚂蚁的个体最优值pbest与全局最优值gbest，并记录蚂蚁路径的平均值mean。

4）再次根据信息素去进行迭代计算，同时找出路径值超过mean的蚂蚁。

5) 将超过mean的蚂蚁替换为临近的优解，重新加入运算。

6）若迭代次数超过设定值则输出最优值，否则进入步骤4）继续进行运算。

同时该算法在回库时设置靠近障碍物的信息素含量最高，这样可使AGV在回库时避免与送货AGV发生道路强占导致一些异常。

在Matlab模拟中设置蚁群算法中迭代次数为100次，信息启发式因子为2，期望启发式因子为5，信息素蒸发系数为0.1，信息素增加强度系数为1.2。在粒子群算法中惯性权重取0.5，学习因子c1、c2均为2。

3 应用实例

某公司立体库中的AGV现场实际路线如图3所示，在Matlab模拟中将有地标的点设为0，仓库设为1，障碍为2。从而得到模拟路线的运算图像。在该智能仓库中，路径比较单一，在送货路径进行寻优过程中算法一致性较强，均能使小车按最短路径到达货仓，但是在出库时，若用传统算法会导致AGV原路返回，可能会与下一辆送货AGV发生交通管制，同时，本文的混合算法在收敛速度上优于传统算法，可以使AGV控制系统更快的下发任务，提高仓库效率。

图3 现场仓库区AGV路线

分别用混合算法与A*算法去优化最远货架的路径，优化的结果如图4所示，两种算法在送货任务中，得到了同样的优化路径，且均为最短路径，但是在回库任务中，混合算法由于在障碍物两旁设置了最大信息素，使得算法优化结束后一定会给小车分配沿障碍物的路径回去，这略微影响了效率，但是可以有效的防止回库AGV与送货AGV路线冲突，避免了很多不必要的交通管制。从而提高了智能仓库的稳定性。

图4 不同算法分配的相同路径

图5 两种算法收敛情况比较

图5为两种算法的收敛速度比较，针对智能物流仓库的井字形地图，通过混合算法与A*算法得到的送货路径相同，不过混合算法在收敛速度上优于A*算法。在实际应用中，可以使得AGV控制系统更为快速的下发AGV任务，从而提高仓库效率。

综合看来，本文提出的混合算法在多AGV路径优化时，在送货段可以比传统A*算法更为快速的得到优化路径，提高了AGV控制系统的效率。在回库路线可以使车辆有序的从指定位置回库，避免了车辆互相管制，发生事故等问题，加强了仓库的安全性。

4 结论

本文针对立体化仓库中AGV的路径规划问题，在分析了蚁群算法与粒子群算法的特点后。结合两种算法提出了混合蚁群粒子群算法来解决路径规划问题。并通过软件模拟与传统的A*算法对比，该方法可以提高仓储物流的效率与安全。该研究对目前智能化仓库中的AGV路径优化问题有一定的实用价值。