混合蚁群算法在车辆路径问题中的应用

张 潇，王江晴：混合蚁群算法在车辆路径问题中的应用 第37卷 第12期 191

3.2 线路改进

为了对所求得的路径进行进一步优化，本文主要采用2-opt法优化阶段最优解的子路径。其方法如下：以(i, j)、 (i+1, j+1)代替(i, i+1)、(j, j+1)，交换后线路路径(i+1,i+2,…,j)被反向。若交换后线路长度缩短，则交换并更新线路。 3.3 信息素浓度的调整

k

在时刻t蚂蚁k由客户i转向客户j的概率pij(t)为：

[τij(t)]α[ηij]β

j∈allowedk k

pij(t)= ∑[τis(t)][ηis] (5) s∈allowed

0 j allowedk

k

对τij设置相应的上下界限。

Step5 NC=NC+1；

动态调整信息素的挥发因子ρ； 评价并更新当前最优解。

Step6 if NC≤nc 转Step2。

Step7 算法结束，输出最优路径及路径长度。

5 实例仿真

限于篇幅，选取部分实验数据罗列，并对实例进行分析和结果比较。

参数设置：α=1，β=3，Q=1.0，每条路径的初始值τij(0)= 1.0。

实例1 有8个客户点和1个配货中心的配送系统，各客户点的需求给定。配货中心只有2辆车用于配送，每辆车的限载容量皆为8吨，配货中心与各客户点的距离以及各客户点需求见参考文献[6](其中，0表示配货中心)。要求合理安排车辆的行驶路线，使总运行费用最少，即总运输里程最少。

通过本文算法随机求解8次，计算结果如表1所示，其中4次得到的最短路径：0→1→2→6→0→4→5→3→8→7→ 0，最短路径长度为270 km。

表1 不同算法的求解结果比较

算法 ORL算法 遗传算法 蚁群算法 混合蚁群算法

最优路径长度/km

最优解概率/(%)

平均计算时间/s

270 38 1.9 276 0 7.0 270 25 3.1 270 51 1.2

其中，allowedk表示蚂蚁k可以往下移动的客户集；dij为 i到j的路径长度；ηij为经验知识(或能见度)，取ηij=1/dij；α,β是控制信息素浓度与可见度的重要参数，且是非负的，

它们决定τij(t)和ηij对蚂蚁转移概率的影响。

本文选用全局更新规则对路径上的信息素进行更新：

Q/Hk 蚂蚁k游历过i,j (6) k

τij(t,t+1)=

0 否则

k

其中， τij表示蚂蚁k在本次遍历(t,t+1)时间段中留在路径

<i,j>上的信息素浓度；信息素Q为常数；Hk表示蚂蚁k在

本次遍历中所走过的路径的长度。

为了防止算法陷入局部最优解，将τij限制在[τmin,τmax]之间，以有效避免某条路径上的信息素浓度远大于其他路径，从而导致早熟收敛。算法中τmin和τmax的取值如下：

τmax11

= (7) ,τmax=τmin

2(1 ρ)L(S)5其中，ρ∈(0,1)，(1–ρ)为信息素浓度的衰减系数，ρ为信息素

的挥发因子；L(Sgb)为全局最优解的路径长度。

3.4 参数动态控制

信息素的挥发因子ρ的大小直接影响算法的全局搜索能力及其收敛速度，本文在迭代过程中，根据迭代次数动态设立不同值：

0.5 NC≤nc/3

ρ= 0.7 nc/3<NC≤2nc/3 (8)

0.9 2nc/3<NC≤nc

其中，NC为迭代次数；nc为算法设定的初始迭代次数。

为了验证算法有效性，将本文所求得的解与ORL算 法[6]、遗传算法、基本蚁群算法进行比较，从表1中的实验数据可以看出，本文算法求出的最优解概率以及平均计算时间都优于其他3种算法，表明其具有较好的寻优效率和求解 速度。

实例2 以参考文献[7]中的测试集为例。该测试集中有20个城市，包含19个客户点及一个配货中心，配货中心只

有4辆车(其中，0为供货中心，它的配送量代表车载限量)。

本文算法计算得到的最短路径是：0→9→15→5→13→ 0→19→3→4→7→6→12→0→8→14→17→1→0→18→2→ 10→11→16→0，最短路径长度42.11 km(见图1)。

4 算法设计

算法描述如下：

Step1 初始化参数α、β、ρ、Q等。

for i=1 to cities do //cities为客户数量

for j=1 to cities do τij(t)=τij(0) Step2 for k=1 to ants do //ants为蚂蚁的数量 {if满足约束条件 选择下一个客户；更新禁忌表和车辆载重量。 else返回配货中心。} for k=1 to ants do

计算lengthk；

//lengthk为第k只蚂蚁的寻优路径长度 寻找阶段最优解。

Step3 对阶段最优解实施变异操作；

用线路改进算法优化阶段最优解的子路径； 评价并更新阶段最优解。

Step4 for each edgeij //edgeij为每条边

do {更新各路径上信息素}；

图1 本文算法的车辆路径情况

比较文献[7-9]中得到的最优路径长度分别为41.86 km、

42.32 km(见图2)、44.09 km(见图3)，解的质量上相对文献[7]有退步，但是仔细计算文献[7]中的子路径：(0→2→10→11→ 16→7→5→15→9→0)上的缺货量的和为9.5，大于车辆最大的限载量9，可见为不满足约束条件的一组解。再观察其次