Solution of Travelling Salesman Problem Using Ant Colony Algorithm

Abstract:

Recently some studies have been revealed by inspiring from animals which live as colonies in the nature. Ant Colony System is one of these studies. This system is a meta-heuristic method which has been developed based upon food searching characteristics of the ant colonies. Ant Colony System is applied in a lot of discrete optimization problems such as travelling salesman problem. In this study solving the travelling salesman problem using ant colony system is aimed.

• Periodical: Applied Mechanics and Materials (Volumes 548-549)
• Pages: 1206-1212
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.548-549.1206
• Online since: April 2014
• Authors: Sevda Dayıoğlu Gülcü, Şaban Gülcü, Humar Kahramanli
• Keywords: Ant Colony System, Meta-Heuristic, Optimization, Travelling Salesman Problem

References

[1] E. Bonabeau, M. Dorigo and G. Theraulaz: Inspiration for optimization from social insect behavior, Nature 2000, vol. 406, p.39–42.

DOI: 10.1038/35017500

[2] Z. Wang, H. Duan and X. Zhang: An Improved Greedy Genetic Algorithm for Solving Travelling Salesman Problem, Natural Computation, ICNC '09. Fifth International Conference on, vol. 5, pp.374-378, 14-16 Aug. (2009).

DOI: 10.1109/icnc.2009.504

[3] G. Wei and Xiaoyao Xie: Research of using genetic algorithm of improvement to compute the most short path, Anti-counterfeiting, Security, and Identification in Communication, 2009. ASID 2009. 3rd International Conference on, pp.516-519, 20-22 Aug. (2009).

DOI: 10.1109/icasid.2009.5276990

[4] F. Kondo and T. Watanabe: A study on distributed parameter free genetic algorithm for TSP problem, Systems, Man, and Cybernetics (SMC), 2011 IEEE International Conference on, pp.675-680, 9-12 Oct. (2011).

DOI: 10.1109/icsmc.2011.6083718

[5] L. Yai-Fung, H. Pei-Yee, R. Ramli and R. Khalid: An improved tabu search for solving symmetric traveling salesman problems, Humanities, Science and Engineering (CHUSER), 2011 IEEE Colloquium on, pp.851-854, (2011).

DOI: 10.1109/chuser.2011.6163857

[6] H. Keko, M. Skok, and D. Skrlec: Artificial immune systems in solving routing problems, EUROCON 2003. Computer as a Tool. The IEEE Region 8, vol. 1, pp.62-66, (2003).

DOI: 10.1109/eurcon.2003.1247979

[7] W. Sun; X. Xu, H. Dai, and T. Zheng, H.: An immune optimization algorithm for TSP problem, SICE 2004 Annual Conference, vol. 1, pp.710-715, 4-6 Aug. (2004).

[8] M. Dorigo and Thomas Stützle: Ant Colony Optimization, MIT Press, (2004).

[9] S. Goss, S. Aron, J. L. Deneubourg and J. M. Pasteels: Self-organized Shortcuts in the Argentine Ant, Naturwissenschaften, vol. 76, pp.579-581, (1989).

DOI: 10.1007/bf00462870

[10] M. Dorigo, G. Caro and L. Gambardella: Ant Algorithms for Discrete Optimization, Artifical Life, vol. 5, no. 3, pp.137-172, (1999).

DOI: 10.1162/106454699568728

[11] M. Dorigo and L. Gambardella: Ant colonies for the traveling salesman problem, Biosystems, vol. 43, p.73–81, July (1997).

DOI: 10.1016/s0303-2647(97)01708-5

[12] M. Dorigo and C. Blum: Ant colony optimization theory: a survey, Journal Theoretical Computer Science, vol. 344, pp.243-278, (2005).

DOI: 10.1016/j.tcs.2005.05.020

[13] M. Dorigo and L. Gambardella: Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions On Evolutionary Computation, vol 1, pp.53-66, (1997).

DOI: 10.1109/4235.585892

[14] M. Dorigo, V. Maniezzo and A. Colorni: The Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, vol. 26, no. 1, pp.1-13, (1996).

DOI: 10.1109/3477.484436

[15] S. Haykin, B. Kosko, Intelligent Signal Processing, Wiley-IEEE Press, (2001).