An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem

作者：Lee Chou Yuan; Lee Zne Jung^*; Lin Shih Wei; Ying Kuo Ching

来源：Applied Intelligence, 2010, 32(1): 88-95.

DOI：10.1007/s10489-008-0136-9

• Capacitated vehicle routing problem
• Hybrid algorithm
• Ant colony optimization
• Simulated annealing

In this paper, an enhanced ant colony optimization (EACO) is proposed for capacitated vehicle routing problem. The capacitated vehicle routing problem is to service customers with known demands by a homogeneous fleet of fixed capacity vehicles starting from a depot. It plays a major role in the field of logistics and belongs to NP-hard problems. Therefore, it is difficult to solve the capacitated vehicle routing problem directly when solutions increase exponentially with the number of serviced customers.
The framework of this paper is to develop an enhanced ant colony optimization for the capacitated vehicle routing problem. It takes the advantages of simulated annealing and ant colony optimization for solving the capacitated vehicle routing problem. In the proposed algorithm, simulated annealing provides a good initial solution for ant colony optimization. Furthermore, an information gain based ant colony optimization is used to ameliorate the search performance. Computational results show that the proposed algorithm is superior to original ant colony optimization and simulated annealing separately reported on fourteen small-scale instances and twenty large-scale instances.

• 出版日期2010-2
• 单位长春大学