COMPARATIVE ANALYSIS OF THE APPLICATION OF HEURISTIC ALGORITHMS FOR SOLVING THE TSP PROBLEM
DOI:
https://doi.org/10.26906/SUNZ.2024.2.144Keywords:
genetic algorithms, NP-complex problem, TSP-problem, ant colony algorithm, MATLABAbstract
The need to solve the traveling salesman problem (TSP) often arises when solving practically significant optimization problems, such as problems in the field of economics, logistics in the widest range of applications, in chains of technical programs. Quite often, the specifics of these problems require obtaining a solution that is as close to the exact value as possible. But the TSP problem is NP-complex, that is, its exact solution can be obtained only in exponential time. Therefore, it is not efficient to solve the TSP problem by the full search algorithm in the presence of a large number of vertices of the graph. However, there are various heuristic algorithms that allow finding a rational solution to this problem with a large number of vertices in a time acceptable for the relevant subject area. In this work, the problem of the traveling salesman is defined as a mathematical programming task of finding the shortest path for the movement of a traveling salesman (traveling salesman), the goal of which is to visit all the objects involved in the task in the shortest time and with minimal costs. Appropriate adaptations of the heuristic algorithms, namely the genetic algorithm and the ant colony algorithm, were developed in the MATLAB environment. A computational experiment was performed on the same input sample, a comparative analysis of the performance of two heuristic algorithms, and the effectiveness of the use of heuristic algorithms for solving NP-complex problems was proven.Downloads
References
The Traveling Salesman Problem: A Computational Study, D.L. Applegate, R.E. Bixby, V. Chvátal & W.J. Cook (2006). [Electronic resource]. URL: https://www.math.uwaterloo.ca/tsp/book/contents.html (Date accessed 11/01/2023).
Mathematical methods of operations research: a textbook/ E. A. Lavrov, L. P. Perhun, V. V. Shendryk and others. – Sumy: Sumy State University, 2017. – 212 p.
Hassan M. H. Mustafa, Ayoub Al-Hamadi, Mohamed Abdulrahman, Shahinaz Mahmoud, Mohammed O Sarhan On Comparative Analogy between Ant Colony Systems and Neural Networks Considering Behavioral Learning Performance// Journal of Computer Sciences and Applications. 2015, vol. 3 No. 3, 79-89.
Biological bases of ant colonies - [Electronic resource]. URL: http://posibniki.com.ua/post-prikladni-sistemi-kolektivnogo-intelektu-swarm-intelli-gence (Date of application 10/15/2023).
Rukundo, O., Cao, H. Advances on image interpolation based on ant colony algorithm. SpringerPlus 5, 403 (2016) - [Electronic resource]. URL: https://springerplus.springeropen.com/articles/10.1186/s40064-016-2040-9
Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics) 6th ed., New York, 2018, 455 p.
Divya M. A Comparison of Ant Colony Optimization Algorithms Applied to Distribution Network Reconfiguration// International Journal of Engineering Research & Technology, Volume 3, Issue 01, 2016. – pp. 1-4.
Hahsler M., Hornik K. TSP – Infrastructure for the Traveling Salesperson Problem// Journal of Statistical Software, December 2007, Vol. 23, Issue 2, 2007. – pp. 1-21.
Genetic algorithms. Key concepts and implementation methods. znannya.org : website. URL: http://www.znannya.org/view_ga_general (access date: 10/3/2023).
Sathya N., Muthukumaravel A. A review of the Optimization Algorithms on the Traveling Salesman Problem. Indian Journal of Science and Technology, Vol 8(29), DOI: 10.17485/ijst/2015/v8i1/84652, November 2015.
Genetic Algorithm Tom V. Mathew Assistant Professor, Department of Civil Engineering, Indian Institute of Technology Bombay, Mumbai-400076.
Ivanova E.A. "The possibility of applying genetic algorithms in solving scheduling problems" // Colloquium-journal. 2018. No. 3-1 (14). P. 36-38.
Dorigo, M. Ant algorithms and stimergy / M. Dorigo, E. Bonabeau, G. Theraulaz // Future Generation Computer Systems. — 2000. — No. 16. — P. 851-871.
Chivilikhin D., Ulyantsev V. Inferring Automata-Based Programs from Specification With Mutation-Based Ant Colony Optimization / Proceedings of the 16th Genetic and Evolutionary Computation Conference companion. - ACM, 2014. - p. 68.
Alexandrov A., Sergushichev A., Kazakov S., Tsarev F. Genetic Algorithm for Induction of Finite Automation with Continuous and Discrete Output Actions / Proceedings of the 2011 GECCO Conference Companion on Genetic and Evolutionary Computation. NY. : ACM. 2011, p. 778.
Getting Started with MATLAB. Version 6.5. The MathWorks, Inc., 2002.
