Abstract
In this paper, we present a prototype application designed to solve the Traveling Salesman Problem (TSP). This application allows for obtaining high-quality solutions within reasonable time frames using bio-inspired algorithms, specifically variants of Ant Systems such as Ant Colony System, Max-Min Ant System and Best-Worst Ant System. We will review the operation of each of these algorithms and apply them interactively to solve TSP instances. These algorithms will be compared with the deterministic Lin-Kernighan algorithm to demonstrate their effectiveness.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Colorni, A., Dorigo, M., Maniezzo, V.: Distributed optimization by ant colonies. In: Proceedings of ECAL91-European Conference on Artificial Life, pp. 134–142. Elsevier, New York (1991)
Colorni, A., Dorigo, M., Maniezzo, V.: An investigation of some properties of an ant algorithm. In: Proceedings of Parallel Problem Solving from Nature Conference (PPSN 92), pp. 509–520. Elsevier, New York (1992)
Dorigo, M.: Optimization, learning and natural algorithms. Ph.D. dissertation, DEI, Politecnico di Milano, Italy (1992). (in Italian)
Dorigo, M.: The any system optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern.-Part B 26(1), 1–13 (1996)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The traveling salesman problem: a comprehensive survey. Oper. Res. 34(2), 319–368 (1985)
Lin, H., Gao, L., Wang, X.: Solving the traveling salesman problem using multi-agent simulated annealing algorithm. Appl. Soft Comput. 11(7), 6113–6120 (2011)
Karaboga, D., Basturk, B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J. Global Optim. 39(3), 459–471 (2006)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Hoboken (1985)
Bitner, J.R., Reingold, E.M.: Backtrack programming techniques. Commun. ACM 18(11), 651–656 (1975)
Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957)
Liu, C.-C., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 498–516 (1973)
Gambardella, L.M., Dorigo, M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)
Stützle, T., Hoos, H.H.: MAX-MIN Ant System. Futur. Gener. Comput. Syst. 16(8), 889–914 (2000)
Cordón, O., Fernández de Viana, I., Herrera, F., Moreno, L.l.: A new ACO model integrating evolutionary computation concepts: the best-worst ant system. In: Actas de A ’2000, pp. 22–29 (2000)
Laporte, G.: The traveling salesman problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Valdivia Alcalá, D.I., García Vico, Á.M., Carmona del Jesús, C.J. (2024). Optimization of Transport Routes Through a Social Interaction Algorithm-Based Application. In: Quintián, H., et al. International Joint Conferences. ICEUTE CISIS 2024 2024. Lecture Notes in Networks and Systems, vol 957. Springer, Cham. https://doi.org/10.1007/978-3-031-75016-8_28
Download citation
DOI: https://doi.org/10.1007/978-3-031-75016-8_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-75015-1
Online ISBN: 978-3-031-75016-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)