UPM Institutional Repository

Ant colony optimization for capacitated vehicle routing problem.


Tan, Wen Fang and Lee, Lai Soon and Abdul Majid, Zanariah and Seow, Hsin Vonn (2012) Ant colony optimization for capacitated vehicle routing problem. Journal of Computer Science, 8 (6). pp. 846-852. ISSN 1549-3636


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.

Download File

PDF (Abstract)
Ant colony optimization for capacitated vehicle routing problem.pdf

Download (83kB) | Preview

Additional Metadata

Item Type: Article
Divisions: Faculty of Science
Institute for Mathematical Research
DOI Number: https://doi.org/10.3844/jcssp.2012.846.852
Publisher: Science Publications
Keywords: Ant Colony; Vehicle Routing; Capacitated vehicle routing problem; Ant colony optimization; Heuristics; Pheromone.
Depositing User: Nur Farahin Ramli
Date Deposited: 17 Sep 2013 07:07
Last Modified: 12 Jan 2016 01:37
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.3844/jcssp.2012.846.852
URI: http://psasir.upm.edu.my/id/eprint/24749
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item