基于改进蚁群算法的交通网络最优路径规划方法

李生彪，彭建奎

(兰州文理学院 教育学院,甘肃 兰州 730000)

在交通网络中，最优路径规划是指寻找从起始地到目标地之间总代价最小的目标路径的过程，交通网络最优路径规划方法是智能交通领域研究的重点问题，解决该问题的传统算法主要有广度优先搜索法、Dijkstra算法等。 近些年，随着智能技术的出现，一些学者采用群体仿生理论来解决最优路径规划问题，主要有蚁群算法、遗传算法、神经网络算法以及各算法之间的组合优化算法等。

蚁群算法模拟蚂蚁合作觅食行为的性质，具有较强的全局搜索能力和并行性等优点。但传统蚁群算法有易陷入局部最优解、搜索时间长、有时无法跳出死锁状态等局限性[1]。国内外学者对蚁群算法提出了一些改进思路，如高尚等[2-3]加入混沌理论，赵宝江[4]提出基于自适应路径选择和动态信息素更新的蚁群算法，黄贵玲等[5]加入直线优化启发信息， FUELLERER等[6]加入几种其他启发式算法以提高算法效率，DONATI等[7]则完成了对多个目标的优化等。本研究针对传统经典蚁群算法的局限性，改进信息素浓度更新方式，通过优化信息素总量增强全局搜索能力，以使算法更好地满足于求解交通系统的最优路径问题。

1 环境建模

把交通网络中的道路起始点、目标点和交叉路口等抽象为节点，节点之间的道路抽象为弧，实际道路的长度、车辆通行的时间和道路拥堵程度等信息视为弧的权，那么实际的交通网就可以被抽象为一个带权的有向图。

对于给定的带权有向图G(V,{E})，其中，V是顶点集，E是弧的集合，c(v,w)是弧(v,w) 的权。Pst=(v0=vs,v1=,…,vn=vt)为V中由vs到vt的一条路径。则最优路径问题可表示为如下的数学模型：

minT(Pst)

(1)

在实际中，交通路段的信息实时变化，最优路径的规划也有不同的标准，如最少通行时间、最短距离、最低费用等。因此，针对不同的交通网络信息，需要选择恰当的算法才能找到最优路径。

2 传统蚁群算法及模型

蚂蚁在巢穴和食物之间的路径上会释放信息素，最开始时不论路径的长短都是等概率地选择下一步可行路径。后来，随着迭代次数的增加，蚂蚁在移动时会选择信息素浓度高的路线，这样就使得较短路线上的蚂蚁数量不断增加，较长路线上蚂蚁数量不断减少。因此，通过这些信息素，蚂蚁可以找到一条巢穴到食物的最短路径。

设m是蚂蚁的数量,τij(t)是t时刻路径(i,j)上的信息素浓度。在最开始的时刻，各条路径上的信息素浓度相等，即τij(0)=C，C是常数。假设所有蚂蚁均由路径规划的起点出发，然后，每只蚂蚁在选择其行进路径时依据所在结点i邻接各路径上的信息素浓度计算转移概率。在t时刻蚂蚁k(k=1,2,…,n)由结点i转移到节点j的转移概率

(2)

式中：Ak={N-tk}表示蚂蚁k禁忌表外可以走的节点，N为所在路径网络，tk为禁忌表；α是信息启发式因子，β是期望启发因子；ηij表示由节点i转移到节点j的期望程度，通常ηij=1/dij，其中，dij表示节点i到节点j的距离。

当蚂蚁完成一次对所有节点的搜索之后，则需要对信息素浓度进行更新处理。在此选用Ant-Cycle 模型[8]，则t+Δt时刻路径(i,j)上的信息素浓度为

τij(t+Δt)=(1-ρ)·τij(t)+Δτij(t)

(3)

(4)

(5)

3 基于信息素更新方式改进的蚁群算法

3.1 信息素浓度限定原则

在此设置每条路径上信息素浓度的最小值τmin和最大值τmax，这样就把每条路径上的信息素浓度限定在[τmin,τmax]上。 改进的蚁群算法中设置信息素浓度下限τmin，虽然选择这些路径的概率很小，但不会为零，这样就避免了蚂蚁出现停滞的现象，从而使蚂蚁能进行更高程度的搜索；由于在经典蚁群算法中，寻找最优路径时并不会考虑路网的承受能力，因此有可能会出现拥堵的情况，改进的蚁群算法考虑到实际交通网络中每条路径都有最大承载量，故设置了信息素强度的上限τmax。

3.2 信息素局部更新算法的改进

由于在实际的交通网络中有这样的现象：在某条道路上的通过时间会随着交通流量的增加而增加，而采用信息素局部更新的方法可使信息素浓度较高的边对后面的蚂蚁具有较小的吸引力，从而使蚂蚁对没有被选中的边有更强的探索能力，且实验表明，局部更新规则可以有效避免蚂蚁收敛到同一路径[9]，故文中将蚂蚁行走过程中的信息素更新方式设置为局部更新原则。采用平滑机制的思路，当蚂蚁通过路径(i,j)后，路径(i,j)上的信息素浓度作如下更新：

(6)

3.3 信息素全局更新模型的改进

虽然在局部信息素的改进中考虑了交通网络容量的特性，但当交通流量越大，依据Ant-Cycle 模型(3)计算出的蚂蚁在路网上留下的信息素浓度仍然是最高的，即后来的蚂蚁根据式(2)仍会选择这条路径，最终造成该路径崩溃[10]。现有的信息素更新方法多是对式(4)做出调整，引进路径上的阻抗函数。由于本文讨论的是动态的交通网络最优路径搜索问题，故在此引进能反映实时路况的广义路阻[11]来控制边上的信息素。路径(i,j)上的广义路阻T(i,j)为

T(i,j)=t(i,j)+r(i,j)

(7)

t(i,j)=t0(i,j)[1+k1(V/C)k2]

(8)

r(i,j)=r1(i,j)+r2(i,j)[1+k1(V/C)k2]

(9)

(10)

(11)

式中:t(i,j)、r(i,j)分别为路径(i,j)上的行驶时间和平均延误时间，t0(i,j)表示交通流为零时路径(i,j)的行驶时间；V为路径(i,j)上的交通量当量值；C为路径(i,j)的实用通行能力；k1、k2为回归参数，可根据交通网络的调查数据用最小二乘法确定；r1(i,j)、r2(i,j)分别为均匀延误和过饱和延误；k3、k4为常数；λ是进口路径处绿信比；T是周期；X=V/λC为交叉路口饱和度；C为进口饱和通行能力；S是修正系数。

这样，信息素浓度更新为

(12)

3.4 改进蚁群算法的实现步骤

将改进后的蚁群算法方法应用到实际的交通网络路径问题中，给出路径选择的改进蚁群算法步骤如下：

Step 1 信息素及参数初始化。蚂蚁逐个位于起始点；初始化α、β、tmin、tmax、τij(0)、m、ξ、Q等参数。由于蚁群算法中的参数设定目前尚无理论上的依据，在此用经验确定其最优组合[12]: 1≤α≤5,1≤β≤5,0.5≤ρ≤0.99,1≤Q≤10 000。

Step 2 选择原则。每只蚂蚁依据转移概率在不在禁忌表中的汇点中选择下一个节点，且将所选节点放入禁忌表中。当每只蚂蚁走完一圈后，计算出蚂蚁所走路径的综合系数值。

Step 3 局部更新原则。当蚂蚁选中路径(i,j)后，就按式(7)更新路径(i,j)上的信息素浓度，以增加蚂蚁选择其他路径的概率。

Step 4 局部最优路径搜索。当m只蚂蚁从起始点到终点搜索完成后，则求得m个解，分别在这m个解的邻域中，采用局部搜索算法，求出局部最优解。

Step 5 全局更新原则。当得到m个局部最优解后(否则跳入 Step 2)，按照式(4)、(5)、(11)全局更新路径信息素量，更新路径阻抗，比较所有环游得出的综合系数值，找出最优的环游路径。

Step 6 找出全局最优解。截止到当前迭代次数，在求得的所有局部最优解中，值最小的解作为全局最优解。

Step 7 不断迭代直至迭代次数达到最大值，程序结束。

4 实验仿真及结果

4.1 问题描述

设有一家连锁店企业，有20家连锁分店，编号为1～20，其货物储存仓库(编号为0，坐标为(10，40))每天都向各个连锁分店进行商品补给，该企业每天可调度的车辆数是4辆。 为了方便测试，将储存仓库及20个连锁分店的位置坐标映射至XOY平面上，如图1所示。各连锁分店的位置坐标及每天所需补给量如表1所示。

图1 连锁分店及仓库坐标图Fig.1 Coordinate diagram of chain stores and warehouses

表1 连锁分店坐标及日需补给量Tab.1 Location coordinates of chain stores and daily supply demand

4.2 参数设置

蚁群算法中不同参数的设置对算法的实验结果有很大的影响，在此参照前面的参数最佳设置范围，结合本测试案例，相关实验参数设置见表2。

表2 相关实验参数值Tab.2 Relevant experimental parameter values

4.3 仿真结果及分析

对本案例分别运用传统蚁群算法(ant colony optimization，AC)、自适应转移蚁群算法(adaptive ant colony optimization， AAC)和本文改进蚁群算法进行仿真计算。表 3给出了3种蚁群算法基于本案例运行 10 次所对应的配送成本、收敛代数以及运行时长结果。

表3 3种蚁群算法的运行结果Tab.3 Running results of three ant colony algorithms

从表3可看出，AC算法的配送成本集中在475的附近，没有较大的突破，收敛代数最小31.31，最大54.54，变化较大，不具稳定性；AAC算法的配送成本主要集中在474附近，没有较大变化，收敛代数也没有明显的规律性，对比前两种蚁群算法，本文改进蚁群算法在配送成本方面有了一个实质性的进展和突破，突破了470的约束，以50%的概率归拢于467.4，最佳收敛代数也是最低的26.26。此外，对比3种算法的运行时长，本文算法在最佳值、最差值和平均值方面都优于前两种蚁群算法。

下面给出3种算法的配送成本、最佳配送方案以及收敛代数，见图2、图3、图4和表4。

(a)AC算法的配送成本 (b)AC算法最佳派送方案图2 AC算法规划的配送方案及配送成本Fig.2 Distribution scheme and cost of AC

(a)AAC算法配送成本 (b)AAC算法最佳派送方案图3 AAC算法规划的配送方案及配送成本Fig.3 Distribution scheme and cost of AAC

(a) 本文算法配送成本 (b) 本文算法最佳派送方案图4 本文算法规划的配送方案及配送成本Fig.4 Distribution scheme and cost in this paper

表4 具体配送方案及配送成本Tab.4 Specific distribution scheme and distribution cost

对照图2～4及表4，可以看出AC算法在第32代找到了最优路径，其1号车路线为0-20-16-14-13-12-0，在走完20号、16号分店后再到14号分店，显然违背了 “两点之间线段最短”的公理，故该路线肯定不是最优的。AC算法经过长期动荡搜索，最终收拢于475。AAC算法在第29代绘出最优路径，最终收拢于472，其1号车路线作了优化，但还有交叉路线，说明还有提升的空间。本文改进蚁群算法的最优路径在第27代完成，最终收拢于467，同比AC算法、AAC算法，在收敛代数上分别缩短了16.13%、7.14%，在配送成本上分别降低了1.77%、1.04%。本文改进蚁群算法1 号车的路线既不存在绕路现象，也没有交叉路径，显然为最优路径。此外，3种算法中4号车路线完全一样，都为可取路径。

综上所述，本文算法较传统蚁群算法在时间效率和配送成本方面均有明显程度的提升，在交通网络最优路径规划问题上更具高效性。