Research Article Open Access

Ant Colony Optimization for Capacitated Vehicle Routing Problem

W. F. Tan, L. S. Lee, Z. A. Majid and H. V. Seow

Abstract

Problem statement: The Capacitated Vehicle Routing Problem (CVRP) is a well-known combinatorial optimization problem which is concerned with the distribution of goods between the depot and customers. It is of economic importance to businesses as approximately 10-20% of the final cost of the goods is contributed by the transportation process. Approach: This problem was tackled using an Ant Colony Optimization (ACO) combined with heuristic approaches that act as the route improvement strategies. The proposed ACO utilized a pheromone evaporation procedure of standard ant algorithm in order to introduce an evaporation rate that depends on the solutions found by the artificial ants. Results: Computational experiments were conducted on benchmark data set and the results obtained from the proposed algorithms shown that the application of combination of two different heuristics in the ACO had the capability to improve the ants’ solutions better than ACO embedded with only one heuristic. Conclusion: ACO with swap and 3-opt heuristic has the capability to tackle the CVRP with satisfactory solution quality and run time. It is a viable alternative for solving the CVRP.

Journal of Computer Science
Volume 8 No. 6, 2012, 846-852

DOI: https://doi.org/10.3844/jcssp.2012.846.852

Submitted On: 21 February 2012 Published On: 15 March 2012

How to Cite: Tan, W. F., Lee, L. S., Majid, Z. A. & Seow, H. V. (2012). Ant Colony Optimization for Capacitated Vehicle Routing Problem. Journal of Computer Science, 8(6), 846-852. https://doi.org/10.3844/jcssp.2012.846.852

  • 4,773 Views
  • 7,035 Downloads
  • 17 Citations

Download

Keywords

  • Capacitated vehicle routing problem
  • ant colony optimizatio
  • heuristics
  • pheromone