Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 88-95 |
| Number of pages | 8 |
| Journal | Applied Intelligence |
| Volume | 32 |
| Issue number | 1 |
| DOIs | |
| State | Published - 02 2010 |
| Externally published | Yes |
Keywords
- Ant colony optimization
- Capacitated vehicle routing problem
- Hybrid algorithm
- Simulated annealing