基于改进蚁群算法的车辆路径仿真研究

1、基于改进蚁群算法的车辆路径仿真研究唐连生，程文明，张则强，钟斌，梁剑（西南交通大学机械工程研究所，成都 610031）摘要：针对基本蚁群算法收敛速度慢、易陷于局部最优等缺陷，提出了一种改进蚁群算法。通过车辆的满载率调整搜索路径上的启发信息强度变化，对有效路径采取信息素的局部更新和全局更新策略，并对子可行解进行3-opt优化，在实现局部最优的基础上保证可行解的全局最优。通过对22城市车辆路径实例的仿真，仿真结果表明，改进型算法性能更优，同基本蚁群相比该算法的收敛速度提高近50%，效果显著，该算法能在更短时间内求得大规模车辆路径问题满意最优解。关键字：物流，VRP，蚁群算法，车辆路径中国分类号：T

2、P18 文献标识码：AVEHICLE ROUTING SIMULATION RESEARCH BASED ON AN IMPROVED ANT COLONY ALGORITHMTang Liansheng, Cheng Wenming, Zhang Zeqiang, Zhong Bin, Liang jian(Research Institute of Mechanical Engineering, Southwest Jiaotong University, Chengdu, 610031)ABSTRACT：An improved ant colony algorithm is propos

3、ed aiming at the basic ant colony algorithms convergence slow and be prone to plunge a partial basis. The inspired route information strength changes according to the search vehicles loaded rate. Both local information and global information are updated on the effective route. Achieving optimal loca

4、l basis ensures the best possible solution by means of 2-opt optimized algorithm. The example of 22 city vehicle routing is simulated by this algorithm, and it shows that the speed of convergence nearly 50% increased compared with the basic ant algorithm. The algorithm has achieved significant resul

5、ts, and less time by the algorithm to solve large-scale vehicle routing problems.KEYWORDS：Logistics; VRP; Ant colony algorithm; Vehicle routing 1 引言车辆路径问题（Vehicle Routing Problem，简称VRP）来源于交通运输，由Dantzig1于1959年提出，它是组合优化问题中一个典型的NP-hard问题，用于研究亚特兰大炼油厂向各加油站投送汽油的运输路径优化问题，并迅速成为运筹学和组合优化领域的前沿和研究热点，吸引众多学者对其进行研

6、究。通常用图G=(V,E)用来描述该问题2，在图G=(V，E)中，V=0,1,2,n，E=(i，j)，ij，i，jV，节点1表示仓库（depot），其它节点为客户。每个客户的需求为qi，边(i，j)对应的距离或运输时间或成本为Cij，所有车辆运输能力为Q，车辆从仓库出发，完成运输任务后回到仓库，每个顾客只能接受一次服务，问题的目标函数通常是车辆数和运输成本最小化。由于该问题的复杂性，寻找到一种高效、精确的算法的可能性微乎其微，人们开始尝试利用仿生智能算法求解。 蚁群算法是一种新的群体智能启发式优化方法，适合求解车辆路径等组合优化问题。最初由意大利学者Dorigo34等人提出用于解决旅行商问题，

7、随着研究的不断深入，已经陆续渗透到电子、通讯、车间调度等工程领域。John E. Bell5将蚂蚁系统优化的亚启发式方法应用到VRP问题的求解。Silvia6探讨了在车辆容量限制条件下的VRP问题，在亚启发式算法基础上提出了CVRP 的蚁群算法，并取得较好的效果。刘志勋7等在分析VRP和TSP区别基础上，构造了求解VRP的自适应蚁群算法，提出了近似解可行化的解决策略。蚁群算法由于基本蚁群算法收敛速度慢且易陷于局部最优，很难在较短时间内对大规模VRP求得满意最优解，且该算法极易出现停滞现象，因此有必要对四川省应用基础研究项目（批准号:04JY029-058-1）唐连生 (1974.2-)，男（满

8、族），辽宁人，博士生，研究方向为数字物流与智能技术，车辆路径。算法进行改进。1 基本蚁群算法简介910基本蚁群算法受真实蚁群觅食行为策略的启发，蚂蚁在觅食过程中对所经过路段释放一种被称为信息素的物质，其他经过该路段的蚂蚁通过对残留信息素的数量判断是否重复该路段，从而找到一条巢穴到食物源之间的最短路径。该路段残留信息素越多，所有蚂蚁选择该路段的可能性也就越大。为模拟蚂蚁实际行为设：m是蚁群中蚂蚁的数量，dij是城市i到城市j之间的距离，ij是边(i，j)的能见度，ij=1/dij，反映由城市i转移到城市j的启发程度，ij是边(i，j)上的信息素轨迹强度，ijk是蚂蚁k在边(i，j)上留下的单位长

9、度轨迹信息素量，pijk是蚂蚁k从城市i转移到城市j的状态转移概率， j是尚未访问的城市，则状态转移概率pijk （1）式中，allowedk=0,1,n-1表示蚂蚁k下一步允许选择的城市。和为两个参数，分别反映了蚂蚁在运动过程中积累的信息和启发信息在蚂蚁选择路径中的相对重要性8。为每只蚂蚁设计一个禁忌表tabuk(k=1,2,m)，记录在t时刻蚂蚁k已走过城市，不允许该蚂蚁在本次循环中重复经过。本次循环结束后禁忌表被清空。蚂蚁完成一次循环，对各路径上的信息素进行更新： （2） （3）式中ijk(t，t+1)表示第k只蚂蚁在(t，t+1)时刻留在(i，j)路段上的信息量，ij(t，t+1)表示

10、本次循环中路段(i，j)的信息素增量，(1-)为信息素轨迹的衰减系数。Dorigo给出了三种不同的模型，分别为蚁周系统（ant-cycle system）、蚁量系统（ant-quantity system）、蚁密系统（ant-density system）。区别仅在于ijk(t，t+1)的表达试不同。蚁周系统与其他两种模型的差别在于ij的表达式不同，使用了全局信息而其他两者使用的局部信息。3 算法的改进3 1 状态转移概率公式的改进蚁群算法的主要依据是信息正反馈原理和启发式算法的有机结合，ij的设计是蚁群算法的关键。当群体规 模较大时，短时间内难以求得最优解，如果随机产生的某一路径信息量变化过

11、快，很容易出现搜索停滞现象，为控 图1 改进蚁群算法流程图制信息量的变化速度，采用如下方法选择下一个被访问的城市： 4）式中，0为车辆的满载率，,其中为第k只蚂蚁所在禁忌表的城市需求量之和，QV是车辆的允许载荷。可见，随车辆遍历城市数量的增加而增加，它可以提高路径选择的多样性，从而避免陷入局部最优。q0(0,1)为常数，q为0到1之间的随机数。当qq0时，J仍按式（1）进行计算。3 2 信息素更新策略的改进信息素更新策略是蚁群算法的关键步骤之一，信息更新过快将导致算法陷入局部最优甚至停滞，信息更新过慢则收敛速度缓慢，无法搜索到最优路线。3 2 1全局信息更新 （5） （6）式中当前全局最优解的

12、路线长度，Q常量，信息素的挥发系数。3 2 2局部信息更新蚂蚁找到一个子可行解后，将子可行解路段(i，j)上的信息素进行更新。 （7）式中常数，为本次循环最短路线长度。 算法流程如图1所示。 4 实例分析本文以eil22问题为研究对象，已知有客户，各客户坐标位置点及需求量已知，各车辆 图2 eil22车辆行走路线图 图3 改进蚁群算法的收敛进程载重Q6000。初始参数设置为m20，迭代次数n_gen50，0.9，4，q00.6。采用Matlib7.0编程运算，表1 本文算法同基本蚁群算法在相同参数下的实验结果比较算法类型 最短线路长 进化次数基本蚁群算法 1 4 387.6 372 1 3 3

13、87.6 396 1 2 387.6 408改进蚁群算法 1 4 387.6 184 1 3 387.6 189 1 2 387.6 210得到最终的线路为： 第一条线路：1151720221第二条线路：118211916131第三条线路：1112368101第四条线路：1794512141运输总距离387.6。结果如图2所示。由表1可以看出，在基本参数相同的条件下，使用基本蚁群算法求解结果与改进蚁群算法相同，但改进后的蚁群算法的进化次数大大降低，收敛速度有显著提高。5 结论由仿真结果可以看出，改进后的蚁群算法解的收敛速度提高近50%，通过调整信息素更新策略和启发信息强度，弥补了基本蚁群算法由

14、于信息素更新过快易陷入局部最优的缺点。该算法与3-opt算法相结合，在求解的精度方面也有了很大提高，同时为求解大规模VRP问题提供了一种可行的方法。对该算法进一步扩展后，可用于求解有时间窗的VRP问题，如何利用该算法求解突发事件下到达时间不确定的模糊VRP问题将有待进一步研究。 参考文献 1Bernd Bullnheimer, Richard F. Hartl and Christine Strauss. An improved ant system algorithm for the vehicle routing problemJ/OL. .2 Alberto Colorni, Marco

15、 Dorigo, Vittorio Maniezzo. Distributed Optimization by Ant ColoniesJ. European conference on artificial life, Paris, France, Elsevier Publishing, 134-142. 3Marco Dorigo and Gianni Di Caro. Ant Algorithms for Discrete OptimizationJ. Artificial Life, 1999, 5 (3): 137- 172.4Marco Dorigo. Ant colonies

16、for the traveling salesman problemJ. Biosystems,1997,43:73-81.5John E. Bell, Patrick R. McMullen. Ant colony optimization techniques for the vehicle routing problemJ. Advanced Engineering Informatics Volume: 18, Issue: 1, January, 2004, pp. 41-486Silvia Mazzeo, Irene Loiseau. An ant colony algorithm for the capacitated vehicle routingJ. Electronic Notes in Discrete Mathematics Volume: 18, Complete, December 1, 2004, pp. 181-1867 刘志勋, 申金升, 柴跃廷. 基于自适应蚁群算法的车辆路径问题研究J. 控制与决策, 2005, 20(5): 562-566. 8 Dennis Huisman, Albert P. M. Wage