基于改进自适应遗传粒子群混合算法的多AGV路径规划研究

钱 成 董春芳

（东北林业大学，黑龙江 哈尔滨 150036）

0 引言

随着物流仓储领域对自动化水平要求的不断提高，AGV已经成为影响物流运输效率的关键工具。AGV 路径规划是规划1 条从起点到目标点的无障碍路径，路径规划能力将直接影响整个物流系统的工作效率[1]。

遗传算法凭借寻优能力强的优势，被广泛应用于路径规划领域。苑光明等[2]在传统遗传算法的基础上改进了精英选择策略，动态调整交叉、变异概率，提高了AGV 搜索路径的质量。粒子群算法具有原理简单、收敛速度快以及寻优稳定性高的特点，同样具有广泛的应用范围。丁承君等[3]提出一种具有遗传因子的改进粒子群算法，引入自适应惯性权重并对粒子进行交叉、变异操作，以降低算法迭代次数。

上述学者采用的方法在一定程度上提高了AGV 的路径质量，但是针对处理多AGV 路径规划还是存在寻优能力较差、运行时间长等问题，该文提出了一种改进自适应遗传粒子群混合算法（HpsoGA），根据迭代次数动态修改权重、学习因子，同时对遗传算法中的交叉、变异概率进行动态非线性调整，在适应度函数中引入拥堵系数来惩罚可能拥堵的路径，从而规划更优路径。

1 模型创建

1.1 问题描述

在物流仓库中，需要AGV 从起点出发，根据相应的路径到达目标任务点完成取货作业，同时需要避免与其他工作中的AGV 发生冲突。多AGV 路径规划的目标是在不产生冲突的前提下找到最优路径，从而提高整个系统的运行效率。需要考虑以下6 个约束条件：1） 已知每台AGV 以及目标点的位置。2） 环境地图已知且只存在动态障碍物，即移动中的AGV。3）每台AGV 采用四向移动策略，即能完成4 个方向（前、后、左和右）的移动。4） 每台AGV 对应1 个目标任务，将货物运输到对应目标位置即完成任务。5） 地图中的道路为单通道双向行驶，每个位置节点仅能容纳1 台AGV。6） AGV 保持匀速行驶，不考虑加减速以及能耗。

1.2 建立模型

系统中有多台AGV 以及目标位置点，将整个环境看作二维平面，建立平面直角坐标系。以O点为坐标原点，定义原点坐标为（0，0）。

在多AGV 系统R=（R1，R2，...，RM）中，系统为各AGV规划的全局路径是一组自由节点。记第i个AGV 的路径为Pi={（xi1，yi1），（xi2，yi2）}，...，（xiNsi，yiNsi），其中（xi1，yi1）为第i个AGV 路径中的第一个节点；Nsi为第i个AGV 的路径节点个数。多AGV 路径规划的目标是规划最优路径，各台AGV 到达任务点经过的路径总和最优，同时需要考虑AGV 之间的路径冲突。多AGV 路径规划的目标函数如公式（1）所示，总目标函数使多AGV 系统整体总运输路径最短，保证多AGV 系统中路径整体最优。

式中：k为第i个AGV 路径中的节点序号。

AGV 需要满足的连续约束条件如公式（2）所示。各AGV在移动过程中不能跨点移动，每次移动的步长不能超过节点之间的最大间距，即组成P的节点必须是一组连续的节点集合。

式中：αx、αy为横向、纵向的最大移动距离。安全约束条件如公式（3）所示。

式中：lα为安全距离，在移动的过程中，AGV 在任一路径节点（xik，yik）与障碍物的中心坐标（xh，yh）之间的距离不能小于安全距离；M为AGV 的总数目。

时间窗约束条件如公式（4）所示。

式中：TRim为第i台AGV 经过m个节点的时间；TRjm为第j台AGV 经过n个节点的时间；Tc为冲突限制时间；Ri为第i台AGV 的编号；Rj为第j台AGV 的编号；Nsm为第i个AGV 经过的路径节点个数；Nsn为第j个AGV 的路径节点个数。

公式（4）表示任意2 个AGV 到达任意路径节点的时间必须大于冲突限制时间Tc。

2 多AGV 路径规划的自适应遗传粒子群混合算法

2.1 基本粒子群算法

粒子群算法（PSO）又称鸟群算法。假设在D维空间中粒子的个数为M，其位置和速度按照公式（5）和公式（6）进行更新。

式中：v（k）为k时刻的速度；presenf（k）是k时刻的位置；pbest（k）为k时刻的个体已知最优解；gbest（k）为k时刻的群体已知最优解；r1和r2为2 个服从伯努利分布的0 或1 随机数；ω是惯性权重因子；c1为全局学习因子；c2为局部学习因子。

2.2 非线性递减惯性权重与学习因子优化

在基本粒子群算法中，较大的ω可以提高全局搜索能力，跳出局部极值，而较小的ω可以提高粒子群算法的局部搜索能力。文献[4]引入了一种非线性递减的惯性权重系数对粒子群算法进行改进，使粒子能更细致地对优化目标进行搜索，如公式（7）所示。

式中：ωk为当前迭代的权重值；ωmin为最小惯性权重；Nmax为迭代次数最大值；NT为当前迭代次数；ω为惯性权重系数。

该文提出了一种新的非线性递减惯性权重，如公式（8）所示。

式中：ωmax为最大惯性权重，ω的取值范围为0.4~0.9；m为随机权重调整因子，m=2.1；σ为惯性调整因子；NT为当前迭代次数；Brand为MATLAB 中的随机数生成器，能生成符合贝塔分布的随机数[5]。

为了更合理地对ω进行调整，使用贝塔分布并加入惯性调整因子来调整惯性权重，其中σ=0.1。

为了有效改善粒子群算法的搜索效果，在整个算法中c1逐渐变小，c2应逐渐增大。该文采用动态学习因子来改善粒子群算法的搜索效果，如公式（9）、公式（10）所示。

式中：c1为全局学习因子；c2为局部学习因子。

当迭代次数为1 时，c1≈c1max，c2≈c2min；当NT=Nmax时，c1≈c1min，c2≈c2min。随着算法迭代，学习因子也会随着迭代次数进行调整，从而避免陷入局部最优。

2.3 选择、交叉与变异

为了提高算法的收敛速度，根据算法进化过程中适应度值的变化，动态调整Pc和Pm。该文采用文献[2]中的交叉、变异概率调整公式，如公式（11）、公式（12）所示。

式中：Pc、Pm分别为交叉概率参数、变异概率参数；Pcmax、Pcmin分别为交叉概率的上、下限；Pmmax、Pmmin分别为变异概率的上、下限；Fmax、Fmin分别为群体适应度的最大值、最小值；Fc为交叉的2 个个体中较大的适应度值；Fm为要变异个体的适应度值。

2.4 适应度函数

AGV 路径规划常以路径总长度的倒数为适应度函数评价标准。考虑多AGV 的影响，以路径总长度以及转弯次数为评价指标，同时引入拥堵系数建立适应度函数fit，如公式（13）所示。

式中：lp为路径总长度；pn为转弯路径节点数；pk为拥堵系数；a、b为2 个权重因子，a+b=1。

由于运行过程中可能发生多AGV 之间的路径冲突，因此需要通过拥堵系数对拥堵程度高的路径进行惩罚，从而避免拥堵[6]。拥堵系数是表示一定时间内某一节点遍历的次数对总节点数的比率，如公式（14）、公式（15）所示。

式中：Pk为在节点k的拥堵系数；n为节点号；k为经过的节点号；H为时间段内节点的使用频率；M为节点出现的次数集合；A为AGV 在当前节点的出现次数集合；NAGV为小车数量。

Pk越大，适应度函数fit就越大。

2.5 改进自适应遗传粒子群混合算法多AGV 路径规划步骤

改进自适应遗传粒子群混合算法多AGV 路径规划步骤如下：1） 确定AGV 路径上各个节点的坐标位置。2） 初始化参数，对粒子个体进行编码，生成初始种群，设定粒子的初始位置和初始速度。3） 计算各粒子的适应度值，根据适应度值的优劣来更新粒子最优解pbest以及全局最优解gbest。4） 根据公式（7）~公式（10）分别对惯性权重系数ω、全局学习因子c1以及局部学习因子c2进行更新。5） 根据公式（5）、公式（6）更新粒子的位置和速度。6） 保留适应度好的前三层，最后一层用适应度值最好的个体代替。7） 根据公式（11）选择需要交叉的粒子，完成交叉。8） 根据公式（12）进行粒子变异操作，产生新的子代。对粒子进行解码，计算适应度值并记录。9） 判断是否满足终止条件。如果是，那么算法结束，输出结果；否则回到第三步。

3 实例仿真分析

为了增加合理性对比验证，对文献[2]中的改进遗传算法（HGA）、文献[4]中的改进粒子群算法（HPSO）和该文的HpsoGA 进行对比。根据某物流仓库中的实际环境以及AGV 运行情况建立具有20×20 节点位置的地图模型，地图中共有400个节点，设置M=9，目标任务数Nr=9，编号集合为TP=（TP1，TP2，...，TPNr）。采用HGA、HPSO 进行路径规划，其收敛时间-路径长度折线如图1 所示。

记录HGA、HPSO 每次运行的最优路径以及收敛时的迭代次数，结果见表1、表2。

表1 相对最优路径的数据对比表

表2 收敛时迭代次数对比表

由表1、表2 可知，与HGA 相比，HPSO 算法的收敛时间会缩短22.41%，但是HGA 规划的最短路径长度能比HPSO缩短了13.85%。

针对HGA 和HPSO 的优、缺点，该文采用HpsoGA 进行路径规划，在相同的参数下迭代100 次，其收敛时间-路径长度折线如图2 所示。

图2 HPSO/HGA/HpsoGA 对比图

记录3 种算法在迭代100 次的前提下达到收敛时的最优解以及相应的迭代次数，其运行结果、对比结果见表3、表4。

表3 3 种算法的运行结果

表4 3 种算法的对比结果

由对比结果可以看出，HpsoGA 平均迭代8 次就可以搜索到全局最优路径，最优路径平均值为55.8，比HPSO 的收敛速度快，寻优能力更强且算法稳定性更高。

4 结语

在多AGV 路径规划问题中，已有的改进遗传算法具有收敛速度慢的缺点，而改进粒子群算法容易陷入局部最优，过早达到收敛。该文提出了一种改进自适应遗传粒子群混合算法，采用一种新的非线性递减惯性权重优化并采用动态学习因子进行改进，引入拥堵系数构建适应度函数。结果表明，该算法能以更短的时间规划更优的路径，从而提高AGV 的运行效率。