A Hybrid ACO Algorithm for Capacitated Vehicle Routing Problems

摘要

The Capacitated Vehicle Routing Problem (CVRP) is a well-known combinatorial optimization problem. The traditional ant colony optimization (ACO) method usually can only find a local optimum of the CVRP, and the simulated annealing (SA) method can help ACO get trapped out of the local optima to explore new solutions. Thus, combining the idea of ant colony optimization (ACO) and simulated annealing (SA), we propose a novel hybrid algorithm named SACO to solve the CVRP. In addition, inspired by decomposed ACO algorithms, we extend our algorithm into the decomposed version named DSACO to improve the solution quality and decrease the computational time. We test the standard benchmark problems on both of the proposed two algorithms SACO and DSACO, and make a comparison with other existing ACO-based algorithms. The computational results show the advantages of the proposed algorithms.