汽车保有量的急剧增加，致使城市交通拥挤、停车困难等社会问题不断涌现，严重影响了市民的居住环境，因此，停车难已成为社会亟待解决的难题.而基于自动导引小车(AGV)的平面移动式智能停车库凭借占地面积少、有效停车数量多以及智能化程度高等优点而备受社会各界广泛关注.研究平面移动式智能停车库的核心，就是要解决AGV存取车路径规划问题.车库路径规划的主要目的是让AGV运行在有障碍物的未知环境中，根据某些评价标准(如最短时间、最短距离或最少转弯次数)，寻找一条从预存停车位到目标停车位的最优无碰路径，确保车辆在最短时间内完成存取，提高停车位利用率，减少存取车等待时间，实现停车设备自动化管理.针对路径规划问题，国内外学者已对其进行了深入研究，并相继提出了多种算法，主要有可视图法、图搜索法以及人工势场法等.随着智能算法的不断发展，Dijkstra算法、A^*算法、遗传算法、粒子群算法以及蚁群算法等也被广泛用于解决各领域路径规划问题^[1-2].

Dijkstra算法是一种典型的单源最短路径算法，因其采用遍历搜索方式求解最短路径，故得到的最短路径往往具有可靠性高、鲁棒性好的特点，但也存在时间复杂度高、搜索效率低、占用内存大等缺陷^[3].蚁群算法是一种新型的仿生算法，该算法凭借并行性、强鲁棒性、全局最优以及易与其他启发式算法相结合等优点，被广泛用于解决TSP问题、路由问题、二次分配问题以及车间调度问题等，并取得了不错的效果^[4-9].Johnson等^[2]研究了蚁群算法中信息素对车辆路径选择的影响，仿真结果显示在允许时间范围内，蚁群算法可有效解决逆向物流车辆路径规划问题；康冰等^[4]将折返蚂蚁策略应用到蚁群算法中，极大地提高了算法的收敛速度；黄震等^[8]将蚁群算法和遗传算法进行了有效融合，通过将时间窗因素引入蚁群算法来产生初始种群，然后由遗传算法对其进行交叉和变异操作，得到了更优路径；Chaari等^[9]针对机器人在静态环境中的路径规划问题，提出将蚁群算法与遗传算法进行有效结合，并通过仿真实验验证了算法的可行性和有效性；王美珍等^[10]将粒子群算法和蚁群算法进行了有效融合，极大地提高了算法的搜索效率，缩短了路径长度；何少佳等^[11]利用Dijkstra算法的优点对蚁群算法进行了改进，解决了逃生路径规划问题.

针对AGV存取车路径规划问题，将Dijkstra算法和蚁群算法的优点结合起来，提出一种基于Dijkstra-蚁群(ACO)的混合算法.利用链接可视图法建立环境模型，采用Dijkstra算法规划出AGV的初始路径，通过节点随机选择机制及信息素局部更新和全局更新相结合的方式对基本蚁群算法进行优化改进，然后选用改进的蚁群算法对初始路径进行优化，并通过仿真测试验证混合算法的可行性和有效性.

1 问题描述及环境建模 1.1 问题描述

为实现算法在AGV路径规划中的应用，须对运行环境作如下假设^[12]：1)假设AGV运行环境为二维有限空间；2)假设图中障碍物已知，位置确定，以不规则多边形表示，且忽略其高度方向；3)假设AGV在运行环境中匀速行驶，忽略AGV的启动、转向、制动以及液压系统举升操作等因素；4)以AGV实际尺寸为基准，适当扩大障碍范围，为便于仿真，将AGV视为质点.

1.2 环境建模

利用AGV自带的摄像头、雷达传感器及红外传感器等采集AGV运行环境信息，其包括AGV的起始车位、目标车位、障碍物以及AGV待充电位置等，根据上述信息通过链接可视图法创建AGV运行环境模型.图 1所示为采用链接可视图法在MATLAB环境下创建的环境模型，模型规格为250 m×250 m，模型用6个黑色凸多边形表示障碍物区域.图中各障碍物区域以及边界区域顶点之间的虚线为自由链接线，黑色实线为AGV的可行路径，以V开头的序列数代表各链接线的中点，S和T为AGV的起点和终点位置.

1.3 建立目标函数

在智能停车库中，AGV路径规划的任务是根据当前位置以及存取车位置，在有效避开障碍物的前提下，快速找到一条自起点(车位预存取位置或目标停车位)至目标点(目标停车位或车位预存取位置)的无障碍最优路径，并确保该路径长度最短^[13]：

${\text{Length = min}}\left\{ {{\text{Length}}\left( {{\text{iter}},m} \right)} \right\},$

(1)

式中:iter表示迭代次数，iter∈{1，2，3，…，n}；Length(iter，m)表示在混合算法搜索过程中，第m只蚂蚁在第iter次迭代中所走过的路径长度.

2 Dijkstra算法规划初始路径 2.1 初始路径

E.W.Dijkstra提出的Dijkstra算法具有最短路径可靠性高和鲁棒性好的特点，被广泛用于求解路径规划中任意两点间最短路径.基于此，文中采用该算法规划了AGV从起点S到目标点T的初始路径，算法实现流程如下^[14]：

Step1：根据图 1可行路径，计算各节点间距离并建立权值邻接矩阵D，对于不连通节点间的权值可赋值inf (无穷大)；

Step2：初始化参数，令D(V₁，V₁)=0，D(V₁，V_j)=w_1j(j=2，3，…，n)，建立空表R和Q，并把图中节点分别放入R和Q中，R={V₁}，Q={V₂，V₃，…，V_n}；

Step3：在Q中寻找一顶点V_k，使D(V₁，V_k)=min{D(V₁，V_j)}，V_j∈Q，将V_k加入R中.判断R=∅是否成立，若是，则算法终止，否则算法转入Step4；

Step4：根据节点k修正D(V₁，V_j)，令D(V₁, V_j)=min{D(V₁，V_j)，D(V₁，V_k)+w_kj}，然后转入Step3；

Step5：重复Step3和Step4，即可计算出AGV从起点到其他节点间的路径长度，然后反向追踪即可得到起点至目标点的最短路径.

图 2所示黑色粗实线为利用Dijkstra算法规划的初始路径：S → V₁ → V₂ → V₃ → V₄ → V₅ → V₆ → V₉ → V₁₀ → V₁₁ → V₁₂ → T，最短路径长度为319.628 1 m.

2.2 空间解表示

采用Dijkstra算法规划了AGV初始路径，该路径依次通过节点S，P₁，P₂，…，P_d和T，在此基础上，对初始路径所经过的自由链接线L_i进行定长分段处理，定长设为δ，各条链接线上的分段数可由式(2)确定^[15]：

${N_i} = \left\{ \begin{gathered} \operatorname{int} \left( {\frac{{{L_i}}}{\delta }} \right),\;\;\;\;\;\;\operatorname{int} \left( {\frac{{{L_i}}}{\delta }} \right)为偶数, \hfill \\ \operatorname{int} \left( {\frac{{{L_i}}}{\delta }} \right) + 1,\;\;\;\operatorname{int} \left( {\frac{{{L_i}}}{\delta }} \right)为奇数, \hfill \\ \end{gathered} \right.$

(2)

蚁群算法在初始路径所经过的链接线L_i上，寻找一组优化参数组合(λ₁，λ₂，…，λ_d)，确保链接线上各分点坐标能够满足方程(3)，便可在离散化的空间中得到一条新的优化路径：

$\begin{gathered} {P_i}\left( {{\lambda _i}} \right) = P_i^{\left( 0 \right)} + \left( {P_i^{\left( 0 \right)} - P_i^{\left( 0 \right)}} \right) \times {\lambda _i}, \hfill \\ {\lambda _i} \in \left[ {0,1} \right],i = 1,2, \cdots ,d, \hfill \\ \end{gathered} $

(3)

式中:P_i⁽⁰⁾和P_i⁽¹⁾代表链接线L_i的2个端点; λ_i表示链接线比例参数; d表示链接线划分节点数.

3 蚁群算法设计 3.1 传统蚁群算法

传统蚁群算法的基本原理是：蚂蚁在觅食过程中，各蚂蚁间通过遗留在路线上的信息素相互传递信息并根据信息素强度的高低来指引下一步行进方向，基于这种正反馈机制，最终搜索出一条最短路径^[16].通常情况下，食物周围环境是未知的，在选择路径时，蚂蚁需要根据转移概率p_ij来确定，状态转移概率可由式(4)计算得到：

$p_{ij}^k = \left\{ \begin{gathered} \frac{{\left[ {{\tau _{ij}}{{\left( t \right)}^\alpha }} \right] \cdot \left[ {{\eta _{ij}}{{\left( t \right)}^\beta }} \right]}}{{\sum {\left[ {{\tau _{ij}}{{\left( t \right)}^\alpha }} \right] \cdot \left[ {{\eta _{ij}}{{\left( t \right)}^\beta }} \right]} }},j \in {\text{allowe}}{{\text{d}}_k} \hfill \\ 0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;其他. \hfill \\ \end{gathered} \right.$

(4)

式中:allowed_k={0，1，…, n-1}表示下一步允许选择的节点集合；τ_ij(t)表示在t时刻蚂蚁k遗留在路径(i，j)上的信息素；η_ij表示距离启发函数因子，通常用η_ij=1/d_ij表示，d_ij表示节点i, j间的距离；α为蚂蚁信息素轨迹的相对重要性因子；β为启发函数的相对重要性因子.

随着时间的推移，蚂蚁遗留在路线上的信息素会逐渐挥发丢失，为避免因信息素量过多或过少而影响蚂蚁节点选择，在蚂蚁完成1次循环后，须通过式(5)对可行路径上的信息素进行调整：

${\tau _{ij}}\left( {t + 1} \right) = \rho {\tau _{ij}}\left( t \right) + \Delta {\tau _{ij}}\left( {t,t + 1} \right),$

(5)

$\Delta {\tau _{ij}}\left( {t,t + 1} \right) = \sum\limits_{k = 1}^m {\Delta \tau _{ij}^k\left( {t,t + 1} \right)} ,$

(6)

$\Delta \tau _{ij}^k\left( {t,t + 1} \right) = \left\{ \begin{gathered} \frac{C}{{{L_k}}},第k只蚂蚁在本次循环中经过路径\left( {i,j} \right) \hfill \\ 0,\;\;\;\;{\text{其他}}. \hfill \\ \end{gathered} \right.$

(7)

式中:ρ表示信息素挥发系数；Δτ_ij^k表示第k只蚂蚁在本次循环中留在路径(i，j)上的信息素; Δτ_ij表示本次循环中蚂蚁留在路径(i，j)上的信息素增量; L_k表示第k只蚂蚁完成1次循环的路径长度; C为常数.

3.2 改进蚁群算法

在AGV存取车路径规划中，选用传统蚁群算法虽然能够使AGV规划出一条从起始位置到目标位置的强鲁棒性优化路径，但依然存在诸多不足，表现为全局搜索能力弱、收敛速度慢、搜索效率较低、易出现早熟或停滞以及易陷入局部最优等.针对上述问题，通过节点随机选择机制及信息素局部更新和全局更新相结合的方式对基本蚁群算法进行改进.

3.2.1 节点选择策略

当蚂蚁在链接线L_i上移动时，为提高节点选择多样性，避免陷入局部最优，采用随机选择机制选择下一链接线L_i+1上的节点，具体计算方法如式(8)所示^[17].当节点j需在q>q₀的条件下确定时，则应先计算节点i到节点j的转移概率p_ij，在此基础上，再采用轮盘赌法确定下一节点j.

$j = \left\{ \begin{gathered} \arg \mathop {\max }\limits_{k \in I} \left\{ {{{\left[ {{\tau _{ik}}\left( t \right)} \right]}^\alpha } \cdot {{\left[ {{\eta _{ik}}\left( t \right)} \right]}^\beta }} \right\},\;\;\;q \leqslant {q_0}, \hfill \\ p_{ij}^k\left( t \right) = \frac{{{{\left[ {{\tau _{ik}}\left( t \right)} \right]}^\alpha } \cdot {{\left[ {{\eta _{ik}}\left( t \right)} \right]}^\beta }}}{{\sum\limits_{w \in I} {{{\left[ {{\tau _{ik}}\left( t \right)} \right]}^\alpha } \cdot {{\left[ {{\eta _{ik}}\left( t \right)} \right]}^\beta }} }},q > {q_0}, \hfill \\ j \in {\text{allowe}}{{\text{d}}_i}. \hfill \\ \end{gathered} \right.$

(8)

式中：p_ij表示蚂蚁由节点i向节点j转移的概率；η_ik为距离启发函数因子；τ_ik表示链接线(i，k)上的信息素；allowed_i表示下一步允许选择的节点集合，i表示链接线上所有分节点集合；q为随机变量，q∈[0, 1]；q₀为可调参数，q₀∈[0, 1].

3.2.2 信息素更新策略

为进一步增强算法的全局搜索能力，加快收敛速度，提高搜索效率，提出了局部更新和全局更新相结合的信息素更新方式.

1) 局部更新.在路径搜索中，当蚂蚁每经过一条链接线(i，j)时，都需利用式(9)更新刚经过的链接线：

${\tau _{ij}}\left( {t + 1} \right) = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + \rho {\tau _0},$

(9)

式中:τ₀为初始条件下的信息素; ρ表示信息素挥发系数，取值范围为[0, 1].

2) 全局更新.当所有蚂蚁在完成本次迭代路径搜索后，选取本次迭代所有路径中长度最短的一条，并对该条路径上每一点的信息素进行全局更新，信息素更新可按照式(10)计算：

${\tau _{ij}}\left( {t + 1} \right) = \left( {1 - \rho } \right){\tau _{ij}}\left( t \right) + \rho \Delta {\tau _{ij}}\left( {t,t + 1} \right),$

(10)

$\Delta {\tau _{ij}}\left( {t,t + 1} \right) = \frac{1}{{{L_h}}},$

(11)

式中:Δτ_ij为全局更新中蚂蚁留在路径(i，j)上的信息素增量；L_h表示本次迭代所有蚂蚁搜索到的最优路径长度.

3) 信息素阈值限定.采用上述信息素更新策略虽然能够提高最优解的质量和算法的搜索效率，但也可能导致算法出现过早收敛的问题，基于此，提出通过引入信息素阈值限定策略来解决蚁群算法的过早收敛问题.在算法的每次迭代中，全局更新最优路径上信息素阈值的上下界可由下式确定^[18-19]：

${{\tau }_{ij}}=\left\{ \begin{align} & {{\tau }_{\min }},\ \ \ {{\tau }_{ij}}\le {{\tau }_{\min }}, \\ & {{\tau }_{ij}},\ \ \ \ \ {{\tau }_{\min }}<{{\tau }_{ij}}<{{\tau }_{\max }}, \\ & {{\tau }_{\max }},\ \ \ {{\tau }_{ij}}\le {{\tau }_{\max }}. \\ \end{align} \right.$

(12)

式中τ_max和τ_min分别表示信息素浓度的最大值和最小值.

3.3 算法具体实施步骤

Step1：采用链接可视图法建立环境模型；

Step2：利用Dijkstra算法规划出一条AGV从起点至终点的初始路径；

Step3：蚁群算法参数初始化；

Step4：蚁群算法开始搜索，蚂蚁根据当前节点位置i按照式(8)选择下一节点j；

Step5：下一节点j确定后，蚂蚁需对刚走过的路径(i，j)上的信息素进行局部更新；

Step6：判断蚂蚁是否到达终点，若是，则转至Step7，否则转至Step4；

Step7：统计当前m只蚂蚁搜索到的最优路径，选出其中长度最短的一条，将其代入式(10)和式(11)，更新全局信息素；

Step8：判断迭代次数是否满足iter≤NC，若是，则转至Step4，否则程序结束，输出结果.

4 仿真实验分析

为验证混合算法在AGV存取车路径规划中的可行性和有效性，采用MATLAB对Dijkstra算法和混合算法进行仿真测试.AGV运行环境模型如图 1所示，算法中各参数设置如下：α=1，β=2.5，τ₀=0.00 008，ρ=0.1，q₀=0.9，蚂蚁数量m=20，最大迭代次数NC=500.上述2种算法仿真结果如图 3至图 6所示.

图 3至图 6分别表示不同路径规划要求下，AGV存取车路径运行轨迹迭代图.图 3表示AGV从起始点S到目标点T的路径轨迹迭代图，图 4表示AGV从S到V₁₃的路径轨迹迭代图，图 5表示AGV从S到V₂₄的路径轨迹迭代图，图 6表示AGV从S到V₂₆的路径轨迹迭代图.上述图形中的(a)图表示AGV运行路径仿真曲线图，(b)图表示算法的路径迭代曲线图.在图(a)中，粗实线表示AGV在Dijkstra算法下的存取车运行轨迹，粗虚线表示AGV在Dijkstra-ACO混合算法下的运行轨迹.图(b)中实线表示Dijkstra算法下AGV的路径迭代变化曲线，虚线表示Dijkstra-ACO算法下AGV的路径迭代变化曲线.分析图 3至图 6可知，上述2种算法均能使AGV在存取车过程中有效避开障碍物，然后搜寻到一条从预存泊车位到目标泊车位的无碰优化路径.

对比表 1数据，结合图 3至图 6可知，在路径长度方面，当AGV从起始点S到目标点T运行时，采用Dijkstra算法规划的路径长度为319.628 1 m，Dijkstra-ACO算法规划的为264.266 5 m，Dijkstra-ACO算法比Dijkstra算法减少了55.361 6 m；当AGV从起始点S到目标点V₁₃运行时，采用Dijkstra算法规划的路径长度为237.208 5 m，Dijkstra-ACO算法规划的为195.779 8 m，Dijkstra-ACO算法比Dijkstra算法减少了41.428 7 m；当AGV从起始点S到目标点V₂₄运行时，采用Dijkstra算法规划的路径长度为300.848 7 m，Dijkstra-ACO算法规划的为279.922 9 m，Dijkstra-ACO算法比Dijk-stra算法减少了20.925 8 m；当AGV从起始点S到目标点V₂₆运行时，采用Dijkstra算法规划的路径长度为301.029 1 m，Dijkstra-ACO算法规划的为282.294 5 m，Dijkstra-ACO算法比Dijkstra算法减少了18.734 6 m.在路径平滑度方面，与Dijkstra算法相比，Dijkstra-ACO算法规划的路径具有较好的平滑度.在收敛代数方面，当S→T时，Dijkstra-ACO算法在第81代开始收敛；当S→V₁₃时，Dijkstra-ACO算法在第28代开始收敛；当S→V₂₄时，Dijkstra-ACO算法在第18代开始收敛；当S→V₂₆时，Dijkstra-ACO算法在第21代开始收敛.

综上分析可知，在S到T，S到V₁₃，S到V₂₄及S到V₂₆的存取车路径规划中，AGV采用Dijkstra-ACO算法搜索得到的路径的平滑度和长度均明显优于Dijkstra算法.另外，从图中迭代曲线变化情况可以看出，Dijkstra-ACO算法具有较快的搜索速度、较高的搜索效率和较短的搜索路径长度.

5 结论

针对智能车库AGV存取车路径规划问题，提出了一种混合算法(Dijkstra-ACO算法)，根据MATLAB软件仿真测试结果，可得如下结论：混合算法能够使AGV在存取车过程中有效避开障碍物，然后搜寻到一条无碰优化路径；与Dijkstra算法相比，混合算法规划的路径长度和路径质量明显优于Dijkstra算法；收敛图显示混合算法具有较好的收敛性、较快的搜索速度、较高的搜索效率以及较短的搜索路径长度等优点.