Ant colony optimization for capacitated vehicle routing problem.
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English English |
| Published: |
Science Publications
2012
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/24749/ http://psasir.upm.edu.my/id/eprint/24749/1/Ant%20colony%20optimization%20for%20capacitated%20vehicle%20routing%20problem.pdf |
| _version_ | 1848845121452244992 |
|---|---|
| author | Tan, Wen Fang Lee, Lai Soon Abdul Majid, Zanariah Seow, Hsin Vonn |
| author_facet | Tan, Wen Fang Lee, Lai Soon Abdul Majid, Zanariah Seow, Hsin Vonn |
| author_sort | Tan, Wen Fang |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T08:41:47Z |
| format | Article |
| id | upm-24749 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English English |
| last_indexed | 2025-11-15T08:41:47Z |
| publishDate | 2012 |
| publisher | Science Publications |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-247492016-01-12T01:37:04Z http://psasir.upm.edu.my/id/eprint/24749/ Ant colony optimization for capacitated vehicle routing problem. Tan, Wen Fang Lee, Lai Soon Abdul Majid, Zanariah Seow, Hsin Vonn 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. Science Publications 2012 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/24749/1/Ant%20colony%20optimization%20for%20capacitated%20vehicle%20routing%20problem.pdf 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 http://www.thescipub.com/ 10.3844/jcssp.2012.846.852 English |
| spellingShingle | Tan, Wen Fang Lee, Lai Soon Abdul Majid, Zanariah Seow, Hsin Vonn Ant colony optimization for capacitated vehicle routing problem. |
| title | Ant colony optimization for capacitated vehicle routing problem. |
| title_full | Ant colony optimization for capacitated vehicle routing problem. |
| title_fullStr | Ant colony optimization for capacitated vehicle routing problem. |
| title_full_unstemmed | Ant colony optimization for capacitated vehicle routing problem. |
| title_short | Ant colony optimization for capacitated vehicle routing problem. |
| title_sort | ant colony optimization for capacitated vehicle routing problem. |
| url | http://psasir.upm.edu.my/id/eprint/24749/ http://psasir.upm.edu.my/id/eprint/24749/ http://psasir.upm.edu.my/id/eprint/24749/ http://psasir.upm.edu.my/id/eprint/24749/1/Ant%20colony%20optimization%20for%20capacitated%20vehicle%20routing%20problem.pdf |