2025, issue 4, p. 5-11
Received 01.08.2025; Revised 08.11.2025; Accepted 18.11.2025
Published 08.12.2025; First Online 15.12.2025
https://doi.org/10.34229/2707-451X.25.4.1
On the Solution of the Traveling Salesman Problem by a Modification of the Hungarian Method
Dmitri Terzi 
Moldova State University, Chisinau, Moldova
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The traveling salesman problem is becoming an important object of research in various fields of science, economics and technology. Construction of efficient algorithms with an optimality criterion for the obtained solution is a relevant task. The traveling salesman problem is a transport-type problem and a natural approach to its solution can be methods for solving transport problems, in particular, variants of the Hungarian method.
Purpose. Development of a modification of the Hungarian method for solving the traveling salesman problem. Expanding the capabilities of exact methods for solving transport-type problems.
Results. The possibility of solving the traveling salesman problem by modifying the Hungarian method for solving the assignment problem is shown. The concepts of a set of cyclically independent elements and a cyclically independent zero of a given matrix are introduced. The idea of the modification and one of its implementations are presented in these new terms. Computational experiments were conducted. The results are reflected by three indicators: the average number of iterations and the processor time for a set of problems of a given dimension.
Conclusions. The need to develop effective exact methods for solving the traveling salesman problem leads to the emergence of new ideas and approaches. In this sense, it is useful to use a natural approach based on the application of methods for solving transport-type problems, since the traveling salesman problem is a transport-type problem. It is shown that based on the modification of the Hungarian method, it is possible to build an effective method for obtaining an exact or approximate one depending on the specific situation.
Keywords: traveling salesman problem, cyclically independent elements, modified Hungarian method.
Cite as: Terzi D. On the Solution of the Traveling Salesman Problem by a Modification of the Hungarian Method. Cybernetics and Computer Technologies. 2025. 4. P. 5–11. https://doi.org/10.34229/2707-451X.25.4.1
References
1. Reingold E.M., Nievergelt J., Deo N. Combinatorial algorithms. Theory and Practice. Prentice-Hall, New Jersey 07632, 1977.
2. Sergienko I.V., Lebedeva T.T., Roshchin V.A. Approximate methods for solving discrete optimization problems. Kyiv: Nauk. Dumka, 1980. 276 p. (in Russian)
3. Sergienko I.V., Kaspshitskaya M.F. Models and methods for solving combinatorial optimization problems on a computer. Kyiv: Nauk. Dumka, 1981. 288 p. (in Russian)
4. Rardin R.L. Optimization in Operations Research. Purdue University, 2017.
5. Laporte G. The traveling salesman problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. Vol. 59, No. 2. P. 231–247. https://doi.org/10.1016/0377-2217(92)90138-Y
6. Eneko O., Yang X.-S., Ser J.D. Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics. Nature-Inspired Computation and Swarm Intelligence. 2020. P. 135–164. https://doi.org/10.1016/B978-0-12-819714-1.00020-8
7. Uddin F., Riaz N., Manan A., Mahmood I., Song O.Y., Malik A.J., Abbasi A.A. An improvement to the 2-opt heuristic algorithm for approximation of optimal tsp tour. Applied Sciences. 2023. 13 (12), 7339. https://doi.org/10.3390/app13127339
8. Applegate D., Bixby R., Chavatal V., Cook W. The Travelling Salesman Problem: A Computational Study. 2011. P. 1–15.
9. Halim A.H., Ismail I. Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem. Archives of Computational Methods in Engineering. 2019. 26. P. 367–380. https://doi.org/10.1007/s11831-017-9247-y
10. Sahana S.K. Hybrid optimizer for the travelling salesman problem. Evolutionary Intelligence. Vol. 12, No. 2. P. 179–188. https://doi.org/10.1007/s12065-019-00208-7
11. Toaza B., Esztergár-Kiss D. A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems. Applied Soft Computing. 2023. 110908. https://doi.org/10.1016/j.asoc.2023.110908
12. Gunay-Sezer N.S., Cakmak E., Bulkan S. A hybrid metaheuristic solution method to traveling salesman problem with drone. Systems. 2023. 11 (5). 259. https://doi.org/10.3390/systems11050259
13. Ghadle K.P., Muley Y.M. Travelling salesman problem with MATLAB programming. Int. J. Adv. Appl. Math. Mech. 2015. 2 (3). P. 2347–2529. https://doi.org/10.3390/systems11050259
14. Pankaj D., Rishika Ch., Dhananjay R.M. Travelling Salesman Problem: A Python Implementation. International Journal of Mathematics And its Applications. 2025. 13 (1). P. 57–84.
15. Kun H.W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly. 1955. 2. P. 83–97. https://doi.org/10.1002/nav.3800020109
16. Flood M.M. The traveling-salesman problem. Operations Research. 1956. 4. P. 61–75. https://doi.org/10.1287/opre.4.1.61
17. Munkres J.M. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics. 1957. Vol. 5, No. 1. P. 32–38. https://doi.org/10.1137/0105003
18. Burkard R., Dell'Amico M., Martello S. Assignment problems. Philadelphia (PA): SIAM; 2009. https://doi.org/10.1137/1.9780898717754
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)