一种求解车辆路径问题的混合多蚁群算法

提出一种新的蚁群算法（Multiple Ant Colonies Algorithm based on Sweep Algorithm, SbMACA）用以求解车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）。该方法同以往蚁群算法的不同之处主要体现在两个方面：第一,首次将扫描算法应用于蚁群算法,通过对蚂蚁所构造的初始解中的不同子回路之间的点进行交换优化,该算法可以有效地改进初始解的质量;第二,提出并采用了一种新的多蚁群技术,各个蚁群分别进行各自的搜索,在各个蚁群均停滞后,对蚁群之间的信息素进行交换与更新,以利于蚁群跳离局部最优值。实验结果表明,SbMACA算法具有很强的搜索能力,求取各CVRP的Benchmark问题所得解的质量同最好解相比较而言,平均仅有 0.28%的差距,是求解车辆路径问题的一种十分有效的方法。

Hybrid Multiple Ant Colonies Algorithm for Capacitated Vehicle Routing Problem

A new multiple ant colonies algorithm based on sweep algorithm (SbMACA) was developed for solving the Capacitated Vehicle Routing Problem (CVRP). The SbMACA is different from other ACAs developed before mainly in two aspects. Firstly, once the ants have constructed their solutions, each ant's solution might be improved by applying Sweep Algorithm which makes improvement to the solutions by exchanging the vertices between subtours. Secondly, a new Multiple Ant Colonies technique is proposed, in which multiple ant colonies are executed separately and simultaneously, and after all colonies are in the state of stagnation, communication among them is carried out in order to do favor to leave the local peaks. Experiment shows that the SbMACA is able to find solutions for CVRP within 0.28% of known optimal solutions and is competitive when compared with the best Tabu Search meta-heuristics.