求解VRP问题的混沌模拟退火萤火虫算法.PDF

包 装 工 程 第 38 卷 第 7 期 ·216 · PACKAGING ENGINEERING 2017 年 4 月 求解 VRP 问题的混沌模拟退火萤火虫算法 胡云清 （山西交通职业技术学院，太原 030031 ） 摘要： 目的 使萤火虫优化算法（GSO ）能够适用于车辆路径问题（VRP ）的求解，同时提高该算法的 求解性能。方法 通过对 GSO 算法的改进，提出求解 VRP 问题的混沌模拟退火萤火虫优化算法 （CSAGSO ）。首先，设计改进的GSO 算法（IGSO ）使IGSO 算法能够适应VRP 问题的求解；其次， 在 IGSO 算法中引入模拟退火机制，提出模拟退火萤火虫优化算法（SAGSO ），使IGSO 算法可有效避 免陷入局部极小并最终趋于全局最优。然后，在SAGSO 算法中引入混沌机制，提出CSAGSO 算法，对 SAGSO 算法的荧光素浓度值进行混沌初始化和混沌扰动；最后，对标准算例集进行仿真测试。结果 与 遗传算法、蚁群算法和粒子群算法相比，CSAGSO 算法的全局寻优能力、收敛速度及稳定性均改善了50% 以上。结论 对 GSO 算法的改进是合理的，且 CSAGSO 算法的全局优化能力、收敛速度和稳定性均优 于遗传算法、蚁群算法和粒子群算法。 关键词：车辆路径问题；萤火虫优化算法；模拟退火 中图分类号：TP301 文献标识码：A 文章编号： 1001-3563(2017)07-0216-06 A Chaotic Simulated Annealing Glowworm Swarm Algorithm for Solving VRP Problem HU Yun-qing (Shanxi Traffic Vocational and Technical College, Taiyuan 030031, China) ABSTRACT: The work aims to enable the glowworm swarm optimization (GSO) algorithm to be applied to the solution to the vehicle routing problem (VRP) and improve the solution performance of GSO algorithm. Based on the improvement of GSO algorithm, the chaotic simulated annealing GSO (CSAGSO) algorithm was put forward to solve the VRP. Firstly, the improved GSO (IGSO) algorithm which enabled the IGSO algorithm to adapt to the solution to VRP was designed; secondly, the simulated annealing mechanism was introduced into the IGSO algorithm, and the simulated annealing GSO (SAGSO) algorithm was proposed, which made the local optimal solution of IGSO algorithm jump out of local optimum. Then, the chaotic mechanism was introduced into the SAGSO algorit