CFP last date
20 December 2024
Reseach Article

An Enhanced Ant Colony System for Solving Vehicle Routing Problem with Time Window

by Sandhya, Vijay Katiyar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 73 - Number 12
Year of Publication: 2013
Authors: Sandhya, Vijay Katiyar
10.5120/12794-0080

Sandhya, Vijay Katiyar . An Enhanced Ant Colony System for Solving Vehicle Routing Problem with Time Window. International Journal of Computer Applications. 73, 12 ( July 2013), 27-31. DOI=10.5120/12794-0080

@article{ 10.5120/12794-0080,
author = { Sandhya, Vijay Katiyar },
title = { An Enhanced Ant Colony System for Solving Vehicle Routing Problem with Time Window },
journal = { International Journal of Computer Applications },
issue_date = { July 2013 },
volume = { 73 },
number = { 12 },
month = { July },
year = { 2013 },
issn = { 0975-8887 },
pages = { 27-31 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume73/number12/12794-0080/ },
doi = { 10.5120/12794-0080 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:39:54.573745+05:30
%A Sandhya
%A Vijay Katiyar
%T An Enhanced Ant Colony System for Solving Vehicle Routing Problem with Time Window
%J International Journal of Computer Applications
%@ 0975-8887
%V 73
%N 12
%P 27-31
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Vehicle Routing Problem with Time Window (VRPTW), an extension of VRP, is a complex combinatorial problem having many real life applications. It can be described as the problem of minimizing the total route cost while satisfying the capacity and time window constraint. Ant Colony System (ACS) is a meta heuristic that is often applied to solve VRPTW. In this paper an attempt has been made to enhance the already existing ant colony system to solve the problem efficiently. Experimentation with the Solomon data sheet is performed and compared with best known results available in literature.

References
  1. Laporte, Gilbert. "Fifty years of vehicle routing. " Transportation Science 43. 4 (2009): 408-416.
  2. Dantzig, George B. , and John H. Ramser. "The truck dispatching problem. " Management science 6. 1 (1959): 80-91.
  3. Gambardella, Luca Maria, Éric Taillard, and Giovanni Agazzi. "Macs-vrptw: A multiple colony system for vehicle routing problems with time windows. " New ideas in optimization. 1999.
  4. Dorigo, Marco, Vittorio Maniezzo, and Alberto Colorni. "Ant system: optimization by a colony of cooperating agents. " Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 26. 1 (1996): 29-41.
  5. Qi, Chengming, and Yunchuan Sun. "An improved ant colony algorithm for VRPTW. " Computer Science and Software Engineering, 2008 International Conference on. Vol. 1. IEEE, 2008.
  6. Ma, Xin. "Vehicle Routing Problem with Time Windows Based on Improved Ant Colony Algorithm. " Information Technology and Computer Science (ITCS), 2010 Second International Conference on. IEEE, 2010.
  7. Doerner, Karl F. , and Verena Schmid. "Survey: metaheuristics for rich vehicle routing problems. " Hybrid Metaheuristics. Springer Berlin Heidelberg, 2010. 206-221.
  8. Gambardella, Luca Maria, Éric Taillard, and Giovanni Agazzi. "Macs-vrptw: A multiple colony system for vehicle routing problems with time windows. " New ideas in optimization. 1999.
  9. Zhu, Kenny Qili. "A new genetic algorithm for VRPTW. " Proceedings of the International Conference on Artificial Intelligence. 2000.
  10. Jourdan, Laetitia, Matthieu Basseur, and E-G. Talbi. "Hybridizing exact methods and metaheuristics: A taxonomy. " European Journal of Operational Research 199. 3 (2009): 620-629.
  11. Dorigo, Marco, and Christian Blum. "Ant colony optimization theory: A survey. " Theoretical computer science 344. 2 (2005): 243-278.
  12. Soo, Raymond Kuo Yang, and Yong Haur Tay. "A survey on the progress of research on vehicle routing problem with time window constraints. " Symposium on Progress in Information and Communication Technology (SPICT).
  13. Bullnheimer, Bernd, Richard F. Hartl, and Christine Strauss. "A new rank based version of the Ant System. A computational study. " (1997).
  14. Bullnheimer, Bernd, Richard F. Hartl, and Christine Strauss. "An improved ant System algorithm for the vehicle Routing Problem. " Annals of Operations Research 89 (1999): 319-328.
  15. Balseiro, S. R. , Irene Loiseau, and Juan Ramonet. "An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows. " Computers & Operations Research 38. 6 (2011): 954-966.
  16. Hu, Xiangpei, et al. "An improved ant colony system and its application. " Computational intelligence and security. Springer Berlin Heidelberg, 2007. 36-45.
  17. Hu, Xiangpei, et al. "An improved ant colony system and its application. " Computational intelligence and security. Springer Berlin Heide-berg, 2007. 36-45.
  18. Sandhya et al. "Use of Ant Colony System Heuristic for solving Vehicle routing problem with time window constraint", Scopros 2012 2nd international Conference on Soft Computing for Problem solving, proceedings in AISC series of Springer.
  19. http://www. sintef. no/Projectweb/TOP/VRPTW/Solomon-benchmark/100-customers/
  20. Chen, Chia-Ho, and Ching-Jung Ting. "A hybrid ant colony system for vehicle routing problem with time windows. " Journal of the Eastern Asia Society for Transportation Studies 6. 10 (2005): 2.
Index Terms

Computer Science
Information Sciences

Keywords

Ant Colony Optimization Meta heuristics Time Windows Vehicle Routing Problem.