2025, випуск 4, с. 5-11
Одержано 01.08.2025; Виправлено 08.11.2025; Прийнято 18.11.2025
Надруковано 08.12.2025; Вперше Online 15.12.2025
https://doi.org/10.34229/2707-451X.25.4.1
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Про розв'язання задачі комівояжера модифікацією угорського методу
Д.Г. Терзі 
Державний університет Молдови, Кишинів
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Задача комівояжера – важлива модель для проведення досліджень у різних галузях науки, економіки та техніки. Побудова ефективних алгоритмів для пошуку оптимальних розв’язків – актуальне завдання. Задача комівояжера це задача транспортного типу і природнім підходом до її розв’язування можуть бути алгоритми, що грунтуються на методах розв’язування транспортних задач, зокрема, варіанти угорського методу.
Мета. Розробка модифікації угорського методу для розв’язування задачі комівояжера. Розширення можливостей точних методів розв'язування задач транспортного типу.
Результати. Показана можливість розв’язування задачі комівояжера модифікацією угорського методу для задачі призначення. Введено поняття набору циклічно незалежних елементів та циклічно незалежного нуля даної матриці. У цих нових термінах викладено ідею та одну з її реалізацій. Було проведено обчислювальні експерименти. Результати відображаються трьома показниками: середньою кількістю ітерацій та процесорним часом для набору задач заданої розмірності.
Висновки. Потреба розробки ефективних точних методів розв’язування задачі комівояжера призводить до появи нових ідей, підходів. У цьому сенсі корисним є застосування природнього підходу (заснованого на застосуванні методів розв'язування задач транспортного типу), оскільки задача комівояжера є задачею транспортного типу. Показано, що грунтуючись на модифікації угорського методу можна будувати ефективні методи отримання точного чи наближеного розв’язку залежно від конкретної ситуації.
Ключові слова: задача комівояжера, циклічно незалежні елементи, модифікація угорського методу.
Цитувати так: 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
Список літератури
1. Reingold E.M., Nievergelt J., Deo N. Combinatorial algorithms. Theory and Practice. Prentice-Hall, New Jersey 07632, 1977.
2. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наук. думка, 1980. 276 с.
3. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук. думка, 1981. 288 с.
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. Applegate D., Bixby R., Chavatal V., Cook W. The Travelling Salesman Problem: A Computational Study. 2011. P. 1–15.
8. 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
9. 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
10. 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
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)
Попередня | ПОВНИЙ ТЕКСТ | Наступна