Traveling Salesman Problem Methods of Solution Survey
DOI:
https://doi.org/10.61841/hackr718Keywords:
Travelling Salesman problem (TSP), applied mathematicsAbstract
In this paper, a full review of the Travelling Salesman Problem (TSP) is given. In general, TSP is considered an important area of research in the field of applied mathematics. The problem was started in the 19th century by the well-known mathematician Hamilton. The idea of TSP is to find the shortest Hamiltonian cycle that covers all the nodes in a graph. Later, researchers started to work on this problem using a variety of techniques to obtain an optimal solution. In fact, solutions to TSP are divided into two main types. The exact solutions that do not require a long time to be processed and the heuristic solutions that give approximate results. The main idea of this paper is to review a collection of successful methods that deal with TSP. In addition, this paper contains some examples with different database sizes and comparisons of multiple methods. Furthermore, a mathematical model of this problem with complexity analysis is given.
Downloads
References
1. Agharghor, Amine, Mohammed Essaid Riffi, and Fayçal Chebihi. "A memetic hunting search algorithm for the traveling salesman problem." 2016 4th IEEE International Colloquium on Information Science and Technology (CiSt). IEEE, 2016.
2. Ahmed, Zied O., Ahmed T. Sadiq, and Hasanen S. Abdullah. "Solving the Traveling Salesman's Problem Using Camels Herd Algorithm." 2019 2nd Scientific Conference of Computer Sciences (SCCS). IEEE, 2019.
3. Ayon, Safial Islam, et al. "Spider Monkey Optimization to Solve Traveling Salesman Problem." 2019 International Conference on Electrical, Computer, and Communication Engineering (ECCE). IEEE, 2019.
4. Bakhouya, Mohamed, and Jaafar Gaber. "An immune-inspired-based optimization algorithm: Application to the traveling salesman problem." Advanced Modeling and Optimization 9.1 (2007): 105-116.
5. Bellmore, Mandell, and George L. Nemhauser. "The traveling salesman problem: a survey." Operations Research 16.3 (1968): 538-558.
6. Bellman, Richard. "Dynamic programming treatment of the travelling salesman problem." Journal of the ACM (JACM) 9.1 (1962): 61-63.
7. Bouzidi, Safaa, and Mohammed Essaid Riffi. "Discrete swallow swarm optimization algorithm for travelling salesman problem." Proceedings of the 2017 International Conference on Smart Digital Environment. 2017.
8. Bouzidi, Abdelhamid, and Mohammed Essaid Riffi. "Discrete cat swarm optimization to resolve the traveling salesman problem." International Journal 3.9 (2013).
9. Carpaneto, Giorgio, and Paolo Toth. "Some new branching and bounding criteria for the asymmetric travelling salesman problem." Management Science 26.7 (1980): 736-743.
10. Cheng, Le, et al. "Cockroach swarm optimization algorithm for TSP." Advanced Engineering Forum. Vol.1. Trans Tech Publications Ltd., 2011.
11. Colorni, Alberto, Marco Dorigo, and Vittorio Maniezzo. "An Investigation of some Properties of an "Ant Algorith"m." Ppsn. Vol. 92. No. 1992. 1992.
12. El Majdouli, Mohamed Amine, and Abdelhakim Ameur El Imrani. "Lightning Inspired Search Algorithm:
Introduction & application to the traveling salesman problem." 2015 10th International Conference on
Intelligent Systems: Theories and Applications (SITA). IEEE, 2015.
13. Felipe, Denis, Elizabeth Ferreira Gouvêa Goldbarg, and Marco César Goldbarg. "Scientific algorithms for
the car renter salesman problem." 2014 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2014.
14. Glover, Fred. "Tabu search—part I." ORSA Journal on Computing 1.3 (1989): 190-206.
15. Grefenstette, John, et al. "Genetic algorithms for the traveling salesman problem." Proceedings of the first
International Conference on Genetic Algorithms and Their Applications. Vol. 160, No. 168. Lawrence
Erlbaum, 1985.
16. Grötschel, Martin, and Manfred W. Padberg. "On the symmetric travelling salesman problem I:
inequalities." Mathematical Programming 16.1 (1979): 265-280.
17. Hammouri, Abdelaziz I., et al. "A dragonfly algorithm for solving the traveling salesman problem." 2018 8th IEEE International Conference on Control System, Computing, and Engineering (ICCSCE). IEEE, 2018.
18. Hatamlou, Abdolreza. "Solving travelling salesman problem using black hole algorithm." Soft Computing 22.24 (2018): 8167-8175.
19. Hoffman, Karla L., Manfred Padberg, and Giovanni Rinaldi. "Traveling salesman problem." Encyclopedia of Operations Research and Management Science 1 (2013): 1573-1578.
20. Jati, Gilang Kusuma. "Evolutionary discrete firefly algorithm for travelling salesman problem." International Conference on Adaptive and Intelligent Systems. Springer, Berlin, Heidelberg, 2011.
21. Karaboga, Dervis, and Beyza Gorkemli. "A combinatorial artificial bee colony algorithm for traveling salesman problem." 2011 International Symposium on Innovations in Intelligent Systems and Applications. IEEE, 2011.
22. Krolak, Patrick, Wayne Felts, and George Marble. "A man-machine approach toward solving the traveling salesman problem." Communications of the ACM 14.5 (1971): 327-334.
23. Langevin, André, François Soumis, and Jacques Desrosiers. "Classification of travelling salesman problem formulations." Operations Research Letters 9.2 (1990): 127-132.
24. Little, John DC, et al. "An algorithm for the traveling salesman problem." Operations Research 11.6 (1963): 972-989.
25. Marinakis, Yannis, Magdalene Marinaki, and Georgios Dounias. "Honey bees mating optimization algorithm for the Euclidean traveling salesman problem." Information Sciences 181.20 (2011): 4684-4698.
26. Mataija, Mirta, Mirjana Rakamarić Šegić, and Franciska Jozić. "Solving the travelling salesman problem using the branch and bound method." Zbornik Veleučilišta u Rijeci 4.1 (2016): 259-270.
27. Mavrovouniotis, Michalis, Mien Van, and Shengxiang Yang. "Pheromone modification strategy for the dynamic travelling salesman problem with weight changes." 2017 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, 2017.
28. Mo, Hongwei, and Lifang Xu. "Biogeography migration algorithm for traveling salesman problem." International Conference in Swarm Intelligence. Springer, Berlin, Heidelberg, 2010.
29. Papadimitriou, Christos H., and Kenneth Steiglitz. "Some examples of difficult traveling salesman
problems." Operations Research 26.3 (1978): 434-443.
30. Phu-ang, Ajchara. "The new technique based on the galaxy based search algorithm for solving the
symmetric travelling salesman problem." 2018 International ECTI Northern Section Conference on
Electrical, Electronics, Computer, and Telecommunications Engineering (ECTI-NCON). IEEE, 2018.
31. Purnomo, Hindriyanto Dwi, et al. "Soccer game optimization for travelling salesman problem." 2017
International Conference on Innovative and Creative Information Technology (ICITech). IEEE, 2017.
32. Reinelt, Gerhard. "TSPLIB—A traveling salesman problem library." ORSA journal on computing 3.4
(1991): 376-384.
33. Riffi, Mohammed Essaid, and Morad Bouzidi. "Discrete cuttlefish optimization algorithm to solve the
travelling salesman problem." 2015 Third World Conference on Complex Systems (WCCS). IEEE, 2015.
34. Saji, Yassine, Mohammed Essaid Riffi, and Belaïd Ahiod. "Discrete bat-inspired algorithm for travelling
salesman problem." 2014 Second World Conference on Complex Systems (WCCS). IEEE, 2014.
35. Salcedo-Sanz, S., et al. "The coral reefs optimization algorithm: a novel metaheuristic for efficiently
solving optimization problems." The Scientific World Journal 2014 (2014).
36. Selamoğlu, Birsen İ., and Abdellah Salhi. "The plant propagation algorithm for discrete optimization: The case of the travelling salesman problem." Nature-inspired computation in engineering. Springer, Cham, 2016, 43-61.
37. Sopto, Dibbendu Singha, et al. "Modified Grey Wolf Optimization to Solve Traveling Salesman Problem." 2018 International Conference on Innovation in Engineering and Technology (ICIET). IEEE, 2018.
38. Srour, Ayman, Zulaiha Ali Othman, and Abdul Razak Hamdan. "A water flow-like algorithm for the travelling salesman problem." Advances in Computer Engineering 2014 (2014).
39. Sur, Chiranjib, Sanjeev Sharma, and Anupam Shukla. "Solving travelling salesman problem using Egyptian vulture optimization algorithm—a new approach." Intelligent Information Systems Symposium. Springer, Berlin, Heidelberg, 2013.
40. Verma, Om Prakash, Rashmi Jain, and Vindhya Chhabra. "Solution of travelling salesman problem using bacterial foraging optimization algorithm." International Journal of Swarm Intelligence 1.2 (2014): 179-192.
41. Wang, Kang-Ping, et al. "Particle swarm optimization for traveling salesman problem." Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No. 03ex693). Vol. 3. IEEE, 2003.
42. Wang, Gai-Ge, et al. "A discrete monarch butterfly optimization for Chinese TSP problem." International Conference on Swarm Intelligence. Springer, Cham, 2016.
43. Yahia, Warif B., Mohammed W. Al-Neama, and Ghassan E. Arif. "A HYBRID OPTIMIZATION ALGORITHM OF ANT COLONY SEARCH AND NEIGHBOR-JOINING METHOD TO SOLVE THE TRAVELING SALESMAN PROBLEM."
44. Yaseen, Mustafa T., Ali Hasan Ali, and Ibrahim A. Shanan. "Weighted (k, n)-arcs of Type (nq, n) and Maximum Size of (h, m)-arcs in PG(2, q). Communications in Mathematics and Applications 10.3 (2019): 361-368.
45. Zhou, Yongquan, et al. "A discrete invasive weed optimization algorithm for solving the traveling salesman problem." Neurocomputing 151 (2015): 1227-1236.
Downloads
Published
Issue
Section
License
Copyright (c) 2020 AUTHOR
This work is licensed under a Creative Commons Attribution 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
- Adapt — remix, transform, and build upon the material for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
- Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
