面向物流车辆路径规划的自适应蚁群算法

郑娟毅，付姣姣，程秀琦

(西安邮电大学通信与信息工程学院，陕西西安 710121)

1 引言

随着城市信息化的快速发展，物流发展的愈加迅速，企业间的竞争也愈加激烈，若能在物流末端配送环节加以改进，则能更好的满足需求[1]。车辆路径问题是物流车辆路径规划的关键环节，车辆路径问题(vehicle routing problem,VRP)是指由一个负责配送货物的车队选择较为合适的配送路线，完成具有一定数量的配送点要求并回到配送中心且满足所有约束条件后达到路径最优的问题[2]。在求解VRP中，启发式算法一直是研究路径优化问题的重点，启发式算法主要有节约法[3]，扫描法[4]，遗传算法[5]，粒子群算法[6]，蚁群算法[7](ant colony algorithm，ACA)和模拟退火算法[8](simulated annealing，SA)等，蚁群算法具有较好的并行性和鲁棒性，并且易于其它算法结合，模拟退火算法运算效率高，求解方向与算法的初始状态无关。文献[9]采用并行搜索方式进行信息素交互的双种群最大最小蚁群算法，改善了解的质量但是收敛速度下降了。文献[9]提出一种解决Job-Shop的模拟退火蚁群算法，算法的收敛速度提高了，但出现早熟现象。文献[10]提出求解旅行商问题的模拟退火蚁群算法，它在一定程度上避免了早熟现象，但是收敛速度降低了。

针对以上算法在求解车辆路径问题易陷入局部最优和收敛速度较慢等问题，本文提出一种自适应蚁群算法，将模拟退火算法得到的解作为蚁群算法的初始值；在蚁群算法的状态转移规则引入道路阻抗系数，以满足实际路径需求，并对信息素挥发因子进行自适应调整，结合2-opt邻域搜索算法对蚁群算法得到的解二次交换，改变解的质量并进行优选，前期避免陷入局部最优，后期加快算法收敛速度。

2 车辆路径问题的数学模型

在车辆路径问题中假定配送中心满足配送点的要求，能够合理安排服务车辆的配送路线，使得配送成本达到最低。假设满足以下条件：

1)已知只有一个配送中心与多个配送点位置坐标；

2)从配送中心出发的车辆必须返回配送中心，车辆类型一致；

3)每辆车的车载量尽量达到满载，但不能超过车容量限制；

其中s表示配送中心，有m辆配送车辆为n处配送点服务。dij表示城市i与j的距离，w表示服务车辆配送货物时的配送成本，c表示服务车辆出行任务时的固定成本，每辆车的负荷量为D，每个配送点的需求为vi.则相应的数学模型如下。

目标函数

(1)

约束条件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(1)是求解车辆路径规划配送所需费用最低的目标函数，其中配送所需费用与路径成正比例关系；式(2)-(4)保证每个配送点仅有一辆车进行配送服务；式(5)保证每辆车的负荷量不超过其自身最大负荷量；式(6)保证每辆车的轨迹路线必须为一个闭环，且每辆车必须从配送中心出发。

3 基本蚁群算法的最短路径寻优

蚁群算法是一种仿生优化算法，它主要通过人工模拟蚂蚁的行为实现最短路径的获取。因为蚂蚁对周围环境并不敏感，环境的变化不会影响蚂蚁在短时间内找到新的最短路径。对于蚂蚁而言，真正起到决定性因素的是一种名叫“信息素”的物质，它是蚂蚁释放的一种特别的分泌物，在找寻最短路径的途中，通过感应这种物质来找到最短路径。每只蚂蚁在经过的路径上都会释放信息素，可以根据每条路径上信息素浓度的不同找到最短路径。

对于最短路径问题，基本蚁群算法描述如下：

1)城市车辆路径集群为Path，蚁群数量为m，节点i和节点j间的距离为Dij，t时刻路径的(i，j)信息素浓度为Tij。

2)每只蚂蚁的爬行方向由信息素浓度确定，用禁忌表存储蚂蚁所经过的节点。

3)在路径搜索过程中，通过信息素浓度和启发信息计算状态转移概率。

4)当蚂蚁完成一次遍历后，需要对其路径上的信息素浓度进行调整。

5)当达到搜索最大次数时，找到最短路径。

基本蚁群算法具有正反馈机制、鲁棒性强的优点，同时也具有许多不足之处，如初期信息素缺乏，导致初始解精度不高，长时间搜索导致选择趋于两极化，算法收敛速度和解的质量降低。为了克服基本蚁群算法的不足，提高收敛速度和解的质量，本文对其进行改进。

4 混合算法的改进

4.1 模拟退火算法的引进

针对基本蚁群算法因初期信息素浓度缺乏，导致初始解精度不高问题，引进全局搜索智能模拟退火算法。初始时从一个较高温度出发产生一个解，然后逐渐降低温度产生一个新解，计算当前新解和前一个解的差值，再根据Metropolis抽样准则来判断在最低温度时能获取能量最低态。模拟退火算法的冷却过程为

Ta+1=hTaa=1，2，……，A-1

(9)

4.2 状态转移概率的改进

蚁群算法中，蚂蚁会根据每条路径上的信息素浓度的含量来选择下一个觅食点，假设蚂蚁在t时刻以概率p选择下一个觅食点，此时状态转移概率公式如下

(10)

当蚂蚁完成一次遍历后，对路径上的信息素浓度按照式(12)进行更新

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

(11)

(12)

(13)

其中α表示信息启发因子，β表示期望启发因子，τij表示路径间信息素浓度，ρ表示信息素挥发因子，Q表示信息素总量；Lk表示在当前遍历中最优蚂蚁所经过的路径。

在实际路况中，车辆路径问题需要考虑出现道路拥堵的状况，因此引入交通工程学中的道路阻抗系数，此时将状态转移概率式(10)修改为

(14)

(15)

本文引用蚁群系统[12](AntColonySystem，ACS)的状态转移规则，对蚁群算法状态转移规则进行调整。因此改进后的状态转移规则为

(16)

其中qij表示单位时间内通过的车辆数，cij表示单位时间内车辆的成本，a和b为阻滞系数，a的取值范围(0.1，0.2)，b的取值范围(1，4)。q0是设定好的的阈值，q为[0，1]的随机值。

4.3 信息素挥发因子的改进

信息素挥发因子表示信息素浓度的挥发减少程度，它是影响蚁群算法全局搜索能力和收敛速度的。信息素挥发因子过大，会使各条路径上的信息素浓度挥发的比较快，导致算法收敛速度慢；信息素挥发因子过小，会使各条路径上的信息素浓度挥发的比较慢，路径上的信息素聚集过多导致陷入局部最优。为了避免算法收敛速度过慢或者陷入局部最优等问题，对原有算法的信息素挥发因子进行改进，在算法前期，将信息素挥发系数设置较大，使算法具有较强的全局搜索能力，在达到一定迭代次数后，将信息素挥发系数逐渐减小，使蚁群算法具有较好的收敛速度。因此将信息素挥发系数改进为

(17)

4.4 2-opt算法

2-opt算法可以通过对较优解的两条边进行交换来获取另一个解，这样经过交换搜索可以改变解的质量[12]，是一种局部搜索算法。在所有配送点中随机选择第n1、n2次访问的配送点，交换两者的位置。

图1是常规选择路径图，假设其顺序为A-B-C-D-A，若将其应用到2-opt算法中则如图2所示其顺序为A-D-C-B-A，为提高算法的精度，本文对蚁群算法每一次迭代产生较优解的路径利用2-opt算法进行优化。具体做法如下：首先对每一次迭代产生的较优路径按照2-opt算法的交换方法进行调整，重新计算路径的较优解，若新的解优于调整前的解，则更新蚁群算法的最优路径，否则保持路径不变。

图1 路径选择图

图2 2-opt方法选择图

5 改进算法的流程

改进后算法的思想是将模拟退火算法得到的解作为蚁群算法的初始解，然后采用2-opt算法对蚁群算法得到的路径进行交换得到一个新的路径，并对蚁群算法和2-opt法相应路径解的距离值进行比较获得全局最优解。组合算法流程如图3所示。

图3 改进后算法流程图

算法具体实现步骤：

Step1：模拟退火参数初始化并得到较优解；

Step2：将模拟退火算法得到的较优解作为蚁群算法的初始解，并对参数进行初始化；

Step3：num=1，将各个蚂蚁放在配送中心，并根据式(16)改进的状态转移规律选择下一个节点，并得到当前最优解L1；

Step4：在L1的较优路径通过2-opt算法的找到另一个解L2；

Step5：比较L1和L2的大小，并判断是否接受新解作为当前解；

Step6：对路径上的信息素按照式(11)改进的全局信息素公式进行更新；

Step7：num=num+1，判断num是否达到最大迭代次数，若达到转Step8，若没有达到则转Step3;

Step8：输出最优解。

6 仿真分析

本文在Window10操作系统，Matlab2012a的运行环境下进行验证。算法参数选择如下：α=7，β=10，m=30，h=0.9，T=10000，TA=10，NCmax=100。

为证明算法的有效性和稳定性，以文献[14]中的算例(E-n22-k4，A-n32-k5，A-n36-k5A-n37-k6，A-n38-k5)作为数据源进行仿真对比。其中n后面的数字代表配送点的个数，k后面的数字代表最少需要的配送车辆，最大迭代次数为100次，将改进后算法的最优解与文献[14]及基本模拟退火蚁群算法的最优解进行比较，结果如表1所示。

表1 最优值比较(/km)

由表1可知，本文算法的最优值与基本模拟退火蚁群算法、文献[14]的最优值相比有一定的改进。因此改进后的算法具有更好的性能。表1中本算法的路径图和算法迭代仿真对比图如图4所示：

图4 本文算法最优值路径图与迭代次数对比图

1)(a)表示E-n22-k4的路径图，(b)表示改进后算法和基本模拟退火蚁群算法的迭代次数比较图，解的质量提高9.76%，收敛速度提高41.4%。

2)(c)表示A-n32-k5的路径图，(d)表示改进后算法和基本模拟退火蚁群算法的迭代次数比较图，解的质量提高7.05%，收敛速度提高42.6%。

3)(e)表示A-n36-k5的路径图，(f)表示改进后算法和基本模拟退火蚁群算法的迭代次数比较图，解的质量提高2.65%，收敛速度提高46.8%。

4)(g)表示A-n37-k6的路径图，(h)表示改进后算法和基本模拟退火蚁群算法的迭代次数比较图，解的质量提高13.63%，收敛速度提高43.6%。

5)(i)表示A-n38-k5的路径图，(j)表示改进后算法和基本模拟退火蚁群算法的迭代次数比较图，解的质量提高8.75%，收敛速度提高47.3%。

由此可知，改进后的算法在收敛速度与解的精度上都有提升。

7 结论

本文针对蚁群算法在车辆路径规划存在的问题提出自适应模拟退火蚁群算法。在蚁群算法的状态转移规则引入道路阻抗系数，对全局信息素更新策略的信息素挥发系数进行调整，前期避免陷入局部最优，后期加快算法收敛速度。最后通过对不同规模城市的车辆路径问题进行测试，结果表明，改进后的算法可以提高解的质量和收敛速度。下一步将针对多配送中心和软时间窗的物流路径问题进行研究，用以提高物流车辆路径规划的实用性。