基于解均匀度的车辆路径问题的自适应蚁群算法

蚁群算法是一种新型的模拟进化算法，具有许多优良的性质，可以很好地解决旅行商问题(Traveling Salesman Problem，TSP)，但同时也存在计算时间长、易出现停滞等缺陷。在分析车辆路径问题(Vehicle Roulting Problem，VRP)与TSP区别的基础上，将蚁群算法应用于VRP的求解，通过引入解均匀度、选择窗口以及吸引力等概念对算法的转移策略和更新策略进行改进，构造了具有自适应功能的蚁群算法。实验仿真结果表明所设计的算法具有很强的搜索能力，计算效率较高，能够有效地解决加速收敛与停滞现象之间的矛盾。

An Adaptive Ant Colony Algorithm for Vehicle Routing Problem Based on the Evenness of Solution

Ant Colony Algorithm (ACA) is a novel simulated evolutionary algorithm which shows many promising characters and has been successfully applied to the Traveling Salesman Problem (TSP), which is the prototype of the NP-hard problems. However, ACA has some typical shortages too, such as long computing time, stagnation behavior. ACA is applied to solve Vehicle Routing Problem in terms of the similarity and difference between VRP and TSP, and an Adaptive Ant Colony Algorithm (AACA) is proposed, which is improved from ACA through modifying the pheromone updating rule and the transition rule by introducing Evenness of Solution, Selection Window, Ant Attraction of Arc into it in order to decrease computing time and avoid stagnation behavior of basic ACA. Simulation results show that the AACA can settle the contradictory between convergence speed and stagnation behavior efficiently and is very suitable for solving VRP.