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

唐连生，程文明，张则强，钟斌，梁剑 （西南交通大学机械工程研究所，成都  610031）       摘要：针对基本蚁群算法收敛速度慢、易陷于局部最优等缺陷，提出了一种改进蚁群算法。通过车辆的满载率调整搜索路径上的启发信息强度变化，对有效路径采取信息素的局部更新和全局更新策略，并对子可行解进行3-opt优化，在实现局部最优的基础上保证可行解的全局最优。通过对22城市车辆路径实例的仿真，仿真结果表明，改进型算法性能更优，同基本蚁群相比该算法的收敛速度提高近50%，效果显著，该算法能在更短时间内求得大规模车辆路径问题满意最优解。 关键字：物流，VRP，蚁群算法，车辆路径 中国分类号：TP18       文献标识码：A   VEHICLE ROUTING SIMULATION RESEARCH BASED ON AN IMPROVED ANT COLONY ALGORITHM Tang 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 proposed 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 local 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 results, 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）来源于交通运输，由Dantzig^[1]于1959年提出，它是组合优化问题中一个典型的NP-hard问题，用于研究亚特兰大炼油厂向各加油站投送汽油的运输路径优化问题，并迅速成为运筹学和组合优化领域的前沿和研究热点，吸引众多学者对其进行研究。通常用图G=(V,E)用来描述该问题^[2]，在图G=(V，E)中，V={0,1,2,…,n}，E={(i，j)，i≠j，i，j∈V}，节点1表示仓库（depot），其它节点为客户。每个客户的需求为q_i，边(i，j)对应的距离或运输时间或成本为C_ij，所有车辆运输能力为Q，车辆从仓库出发，完成运输任务后回到仓库，每个顾客只能接受一次服务，问题的目标函数通常是车辆数和运输成本最小化。由于该问题的复杂性，寻找到一种高效、精确的算法的可能性微乎其微，人们开始尝试利用仿生智能算法求解。 蚁群算法是一种新的群体智能启发式优化方法，适合求解车辆路径等组合优化问题。最初由意大利学者Dorigo^[3][4]等人提出用于解决旅行商问题，随着研究的不断深入，已经陆续渗透到电子、通讯、车间调度等工程领域。John E. Bell^[5]将蚂蚁系统优化的亚启发式方法应用到VRP问题的求解。Silvia^[6]探讨了在车辆容量限制条件下的VRP问题，在亚启发式算法基础上提出了CVRP 的蚁群算法，并取得较好的效果。刘志勋^[7]等在分析VRP和TSP区别基础上，构造了求解VRP的自适应蚁群算法，提出了近似解可行化的解决策略。蚁群算法由于基本蚁群算法收敛速度慢且易陷于局部最优，很难在较短时间内对大规模VRP求得满意最优解，且该算法极易出现停滞现象，因此有必要对 算法进行改进。               全文下载基于改进蚁群算法的车辆路径问题研究.doc