ellibsЭлектронные библиотекиRussian Digital Libraries Journal1562-5419Казанский (Приволжский) федеральный университет10.26907/1562-5419-2026-29-2-414-427ellibs-755Research ArticleСтатьиПоиск точного решения задачи нескольких коммивояжеровAn Algorithm for Finding an Exact Solution to the Problem of Multiple Travelling SalesmenКлименкоОлег АлександровичKlimenkoOleg Alexandrovicholeg.klimenko.math@mail.ruШтейнбергБорис ЯковлевичSteinbergBoris Yakovlevichborsteinb@mail.ruЮжный федеральный университетSouthern Federal University202607052026292414427Copyright © Клименко О.А., Штейнберг Б.Я., 20262026Клименко О.А., Штейнберг Б.Я.Klimenko O.A., Steinberg B.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ellibs.elpub.ru/jour/article/view/755

В работе рассмотрена задача нескольких коммивояжеров. Она состоит в том, чтобы на графе со взвешенными дугами найти набор из заранее заданного количества непересекающихся циклов, у которого сумма весов дуг наибольшего цикла будет минимальной. Разработан точный алгоритм решения поставленной задачи, основанный на методе ветвей и границ. В построенном алгоритме, как и в известном алгоритме Балаша – Кристофидеса решения задачи одного коммивояжера, использован венгерский алгоритм решения задачи о назначениях. Представлены результаты численных экспериментов со случайными графами большой размерности.

This article considers the problem of several traveling salesmen. The task is to find a set of a predetermined number of disjoint cycles on a graph with weighted arcs, in which the weight (the sum of the weights of the arcs) of the largest cycle is minimal. An accurate algorithm for solving the problem based on the method of branches and boundaries has been developed. The constructed algorithm, as well as the well-known Balas' and Christofides' algorithm for solving the traveling salesman problem, uses the Hungarian algorithm for solving the assignment problem. Numerical experiments with large-dimensional random graphs have been carried out.

задача коммивояжеразадача о назначенияхвенгерский алгоритмметод ветвей и границграфыдискретная оптимизациягамильтонов циклtraveling salesman problemassignment problemHungarian algorithmbranch and bound methodgraphsdiscrete optimizationHamiltonian cycleReferencesGeri M., Dzhonson D. Vychislitel'nye mashiny i trudno reshaemye zadachi. M.: Mir, 1982. 416 s.Geri M., Dzhonson D. Vychislitel'nye mashiny i trudno reshaemye zadachi. M.: Mir, 1982. 416 s.Balas E., Christofides N. A restricted lagrangean approach to the traveling salesman problem // Mathematical Programming. 1981. Vol. 21. No. 1. P. 19–46. https://doi.org/10.1007/BF01584228Balas E., Christofides N. A restricted lagrangean approach to the traveling salesman problem // Mathematical Programming. 1981. Vol. 21. No. 1. P. 19–46. https://doi.org/10.1007/BF01584228Burhoveckij V.V. Optimization and Parallelization of Simplified Balas’ and Christofides’ Algorithm for the Traveling Salesman Problem. Program Systems: Theory and Applications // Program Systems: Theory and Applications. 2020. Т. 11, Vyp. 4. S. 3–16. https://doi.org/10.25209/2079-3316-2020-11-4-3-16Burhoveckij V.V. Optimization and Parallelization of Simplified Balas’ and Christofides’ Algorithm for the Traveling Salesman Problem. Program Systems: Theory and Applications // Program Systems: Theory and Applications. 2020. Т. 11, Vyp. 4. S. 3–16. https://doi.org/10.25209/2079-3316-2020-11-4-3-16Burhoveckij V.V., Steinberg B.J. Tochnoe i priblizhennoe resheniya zadachi kommivoyazhyora bol'shogo razmera // Vychislitel'nye metody i programmirovanie. 2024. T. 25, Vyp. 4. S. 476–482. https://doi.org/10.26089/NumMet.v25r436Burhoveckij V.V., Steinberg B.J. Tochnoe i priblizhennoe resheniya zadachi kommivoyazhyora bol'shogo razmera // Vychislitel'nye metody i programmirovanie. 2024. T. 25, Vyp. 4. S. 476–482. https://doi.org/10.26089/NumMet.v25r436Steinberg B., Baglij A., Petrenko V., Burhovetckij V., Steinberg O., Metelica E. An Analyzer for Program parallelization and Optimization // 3-rd International Conference on Applications in Information Technologies ICAIT 2018, Tokyo, November 1–3, 2018. https://doi.org/10.1145/3274856.3274875.Steinberg B., Baglij A., Petrenko V., Burhovetckij V., Steinberg O., Metelica E. An Analyzer for Program parallelization and Optimization // 3-rd International Conference on Applications in Information Technologies ICAIT 2018, Tokyo, November 1–3, 2018. https://doi.org/10.1145/3274856.3274875.Feautrier P. A parallelization framework for recursive tree programs / Feautrier P // EuroPar’98 Parallel Processing: 4th International Euro-Par Conference Southampton, UK, September 1–4, 1998 Proceedings 4. Springer, 1998. P. 470–479. https://doi.org/10.1007/BFb0057890Feautrier P. A parallelization framework for recursive tree programs / Feautrier P // EuroPar’98 Parallel Processing: 4th International Euro-Par Conference Southampton, UK, September 1–4, 1998 Proceedings 4. Springer, 1998. P. 470–479. https://doi.org/10.1007/BFb0057890Kuhn H.W. The Hungarian Method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2. P. 83–97. https://doi.org/10.1002/nav.3800020109Kuhn H.W. The Hungarian Method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2. P. 83–97. https://doi.org/10.1002/nav.3800020109Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group (1976). https://doi.org/10.1007/s43069-021-00101-zChristofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group (1976). https://doi.org/10.1007/s43069-021-00101-zKurejchik V.V., Logunova Y.A. Zadacha kommivoyazhyora. Obzor i metody eyo resheniya. Palmarium Academic Publishing, 2020.Kurejchik V.V., Logunova Y.A. Zadacha kommivoyazhyora. Obzor i metody eyo resheniya. Palmarium Academic Publishing, 2020.Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. 2006. Vol. 34, Issue 3. P. 209–219. https://doi.org/10.1016/j.omega.2004.10.004Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures // Omega. 2006. Vol. 34, Issue 3. P. 209–219. https://doi.org/10.1016/j.omega.2004.10.004Ali AI, Kennington JL. The asymmetric m-traveling salesmen problem: a duality based branchand-bound algorithm // Discrete Applied Mathematics 1986. Vol. 13. P. 259–276. https://doi.org/10.1016/0166-218x(86)90087-9Ali AI, Kennington JL. The asymmetric m-traveling salesmen problem: a duality based branchand-bound algorithm // Discrete Applied Mathematics 1986. Vol. 13. P. 259–276. https://doi.org/10.1016/0166-218x(86)90087-9Laporte G, Nobert Y. A cutting planes algorithm for the m-salesmen problem // Journal of the Operational Research Society. 1980. Vol. 31. P. 1017–1023. https://doi.org/10.1057/jors.1980.188Laporte G, Nobert Y. A cutting planes algorithm for the m-salesmen problem // Journal of the Operational Research Society. 1980. Vol. 31. P. 1017–1023. https://doi.org/10.1057/jors.1980.188Ahmeda Z.H., Al-Dayel I. An Exact Algorithm for the Single Depot Multiple Travelling Salesman Problem // IJCSNS International Journal of Computer Science and Network Security. 2020. Vol. 20. No. 9. https://doi.org/10.22937/IJCSNS.2020.20.09.9Ahmeda Z.H., Al-Dayel I. An Exact Algorithm for the Single Depot Multiple Travelling Salesman Problem // IJCSNS International Journal of Computer Science and Network Security. 2020. Vol. 20. No. 9. https://doi.org/10.22937/IJCSNS.2020.20.09.9Little J., Murty K., Sweeney D., Karel C. An Algorithm for the Traveling Salesman Problem // Operations Research. 1963. Vol. 11, No. 6. P. 972–989. https://doi.org/10.1287/opre.11.6.972Little J., Murty K., Sweeney D., Karel C. An Algorithm for the Traveling Salesman Problem // Operations Research. 1963. Vol. 11, No. 6. P. 972–989. https://doi.org/10.1287/opre.11.6.972Böhm M., Friggstad Z., Mömke T., Spoerhase J. Approximating Traveling Salesman Problems Using a Bridge Lemma // Proceedings of the 2025 Annual ACMSIAM Symposium on Discrete Algorithms. https://doi.org/10.1137/1.9781611978322.34Böhm M., Friggstad Z., Mömke T., Spoerhase J. Approximating Traveling Salesman Problems Using a Bridge Lemma // Proceedings of the 2025 Annual ACMSIAM Symposium on Discrete Algorithms. https://doi.org/10.1137/1.9781611978322.34

The authors declare that there are no conflicts of interest present.