Homepage Program Systems: Theory and Applications Русская версия
ISSN 2079-3316 Bilingual online scientific Online scientific journal of the Ailamazyan Program System Institute of the Ailamazyan PSI of PSI of Russian Academy of Science of RAS 12+ 
Volume 17 (2026) . Issue 4 (73) . Paper No. 4 (530)

Optimization methods and control theory

Research Article
DOIDigital Object Identifier 10.25209/2079-3316-2026-17-4-137-158

Approximate and exact algorithms for the multiple traveling salesman problem

Oleg Aleksandrovich KlimenkoCorrespondent author

Southern Federal University, Rostov-on-Don, Russia
Oleg Aleksandrovich Klimenko — Correspondent author oleg.klimenko.math@mail.ru

Abstract. This paper considers the multiple traveling salesman problem (TSP) without depot, which consists of finding a set of a predetermined number of disjoint cycles covering all vertices on a graph with weighted edges, such that the sum of the edge weights of the largest cycle is minimized.

An exact algorithm for solving this problem, based on the branch-and-bound method, is obtained. The resulting algorithm, like the well-known Balázs-Christofides algorithm for solving the single traveling salesman problem, utilizes the Hungarian assignment problem algorithm.

A parallel version of the resulting algorithm is developed, along with a modification that enables finding an approximate solution with a specified accuracy.

Results of numerical experiments with high-dimensional random graphs are presented. The obtained results demonstrate the superiority of the developed algorithm over known analogs. (In Russian).

Keywords: Traveling salesman problem, assignment problem, Hungarian algorithm, branch and bound method, parallel programming, approximation algorithms

MSC-20202020 Mathematics Subject Classification 68W10; 68W40, 65Y20MSC-2020 68-XX: Computer science MSC-2020 68Wxx: Algorithms in computer science MSC-2020 68W10: Parallel algorithms in computer science MSC-2020 68W40: Analysis of algorithms MSC-2020 65-XX: Numerical analysis MSC-2020 65Yxx: Computer aspects of numerical algorithms MSC-2020 65Y20: Complexity and performance of numerical algorithms

Acknowledgments: The work was supported by the grant № FENW-2026-0031

For citation: Oleg A. Klimenko. Approximate and exact algorithms for the multiple traveling salesman problem . Program Systems: Theory and Applications, 2026, 17:4, pp. 137–158. (In Russ.). https://psta.psiras.ru/2026/4_137-158.

Full text of article (PDF): https://psta.psiras.ru/read/psta2026_4_137-158.pdf.

The article was submitted 15.07.2026; approved after reviewing 06.09.2026; accepted for publication 24.10.2026; published online 02.11.2026.

© Klimenko O. A.
2026
Editorial address: Ailamazyan Program Systems Institute of the Russian Academy of Sciences, Peter the First Street 4«a», Veskovo village, Pereslavl area, Yaroslavl region, 152021 Russia;   Website:  http://psta.psiras.ru Phone: +7(4852) 695-228;   E-mail: ;   License: CC-BY-4.0License text on the Creative Commons site
© Ailamazyan Program System Institute of Russian Academy of Science (site design) 2010–2026