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

A Chaotic Simulated Annealing Glowworm Swarm Algorithm for Solving VRP Problem

目的使萤火虫优化算法(GSO)能够适用于车辆路径问题(VRP)的求解,同时提高该算法的求解性能。方法通过对GSO算法的改进,提出求解VRP问题的混沌模拟退火萤火虫优化算法(CSAGSO)。首先,设计改进的GSO算法(IGSO)使IGSO算法能够适应VRP问题的求解;其次,在IGSO算法中引入模拟退火机制,提出模拟退火萤火虫优化算法(SAGSO),使IGSO算法可有效避免陷入局部极小并最终趋于全局最优。然后,在SAGSO算法中引入混沌机制,提出CSAGSO算法,对SAGSO算法的荧光素浓度值进行混沌初始化和混沌扰动;最后,对标准算例集进行仿真测试。结果与遗传算法、蚁群算法和粒子群算法相比,CSAGSO算法的全局寻优能力、收敛速度及稳定性均改善了50%以上。结论对GSO算法的改进是合理的,且CSAGSO算法的全局优化能力、收敛速度和稳定性均优于遗传算法、蚁群算法和粒子群算法。

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 algorithm, and the CSAGSO algorithm was proposed, which carried out the chaos initialization and chaos perturbation of the fluorescein concentration value of the SAGSO al- gorithm. Finally, simulation tests were carried out on a standard example set. Compared with genetic algorithm, ant colo- ny algorithm and particle swarm optimization algorithm, the global optimization ability, convergence rate and stability of CSAGSO algorithm were improved by more than 50%. The improvement of GSO algorithm is reasonable, and the global optimization ability, convergence rate and stability of CSAGSO algorithm are better than those of the genetic algorithm, ant colony algorithm and particle swarm optimization algorithm.