An Algorithm for Finding an Exact Solution to the Problem of Multiple Travelling Salesmen
Main Article Content
Abstract
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.
Article Details
References
2. 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/BF01584228
3. Burhoveckij 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-16
4. Burhoveckij 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.v25r436
5. 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.
6. 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/BFb0057890
7. Kuhn 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.3800020109
8. Christofides 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-z
9. Kurejchik V.V., Logunova Y.A. Zadacha kommivoyazhyora. Obzor i metody eyo resheniya. Palmarium Academic Publishing, 2020.
10. 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.004
11. Ali 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-9
12. Laporte 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.188
13. Ahmeda 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.9
14. Little 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.972
15. Bö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
This work is licensed under a Creative Commons Attribution 4.0 International License.
Presenting an article for publication in the Russian Digital Libraries Journal (RDLJ), the authors automatically give consent to grant a limited license to use the materials of the Kazan (Volga) Federal University (KFU) (of course, only if the article is accepted for publication). This means that KFU has the right to publish an article in the next issue of the journal (on the website or in printed form), as well as to reprint this article in the archives of RDLJ CDs or to include in a particular information system or database, produced by KFU.
All copyrighted materials are placed in RDLJ with the consent of the authors. In the event that any of the authors have objected to its publication of materials on this site, the material can be removed, subject to notification to the Editor in writing.
Documents published in RDLJ are protected by copyright and all rights are reserved by the authors. Authors independently monitor compliance with their rights to reproduce or translate their papers published in the journal. If the material is published in RDLJ, reprinted with permission by another publisher or translated into another language, a reference to the original publication.
By submitting an article for publication in RDLJ, authors should take into account that the publication on the Internet, on the one hand, provide unique opportunities for access to their content, but on the other hand, are a new form of information exchange in the global information society where authors and publishers is not always provided with protection against unauthorized copying or other use of materials protected by copyright.
RDLJ is copyrighted. When using materials from the log must indicate the URL: index.phtml page = elbib / rus / journal?. Any change, addition or editing of the author's text are not allowed. Copying individual fragments of articles from the journal is allowed for distribute, remix, adapt, and build upon article, even commercially, as long as they credit that article for the original creation.
Request for the right to reproduce or use any of the materials published in RDLJ should be addressed to the Editor-in-Chief A.M. Elizarov at the following address: amelizarov@gmail.com.
The publishers of RDLJ is not responsible for the view, set out in the published opinion articles.
We suggest the authors of articles downloaded from this page, sign it and send it to the journal publisher's address by e-mail scan copyright agreements on the transfer of non-exclusive rights to use the work.