求解CVRP问题的一种改进启发式蚁群算法

An Improved Heuristic Ant Colony Algorithm for Capacitated Vehicle Routing Problems

针对蚁群算法求解CVRP问题时收敛速度慢、求解质量不高的缺点,提出了一种改进启发式蚁群算法。该算法借鉴蚁群系统和基于排列的蚂蚁系统的优点设计信息素更新策略,既加强了对每次迭代最好解的利用,又避免了陷入局部最优;按一定比例使用基本方法和基于PFIH方法构造路径,扩大了算法的搜索空间;采用一种混合局部搜索算子,增强了算法局部寻优能力。实验结果表明,改进启发式蚁群算法可以大幅度减少车辆运行成本,具有较快的收敛速度。

In view of the slow convergence and the low quality of ant colony algorithm for eapaeitated vehicle routing prob- lems （CVRP）, an improved ant colony algorithm is proposed. Inspired by the ant colony system and the rank-based ant system, the algorithm employs the pheromone update strategy, not only strengthening the usage of the best solutions of each iteration, but also avoiding falling into a local optimum. With the use of the basic method by a certain percentage and construction of a path with push- forward insertion heuristic （PFIH） method, the search space is expanded. Using a hybrid local search operator, it enhances the ca- pacity of local search. The experimental results show that the algorithm can greatly reduce the vehicle operating costs and has fast convergence speed, which proves that the algorithm is effective.