DOI: https://doi.org/10.26089/NumMet.v25r436

Exact and approximate solutions of the traveling salesman problem of large size

Authors

  • Victor V. Burkhovetskiy
  • Boris Ya. Steinberg

Keywords:

traveling salesman problem
exact algorithm
heuristic algorithm
parallel algorithm
branch-and-bound

Abstract

This paper describes a fast heuristic algorithm based on branch-and-bound for the traveling salesman problem with a set approximation ratio, i.e. with a parameter k that guarantees that the solution obtained by the algorithm is at most 1/k times worse than the optimal solution. The algorithm is designed for shared-memory systems.

Downloads

Published

2024-12-11

Issue

Vol. 25 (2024): Issue 4.

Section

Parallel software tools and technologies

Author Biographies

Victor V. Burkhovetskiy

Southern Federal University,
Vorovich Institute for Mathematics, Mechanics and Computer Science,
• Phd Student

Boris Ya. Steinberg

Southern Federal University,
Vorovich Institute for Mathematics, Mechanics and Computer Science,
• Senior Researcher

References

  1. J. R. Miller, S. Koren, and G. Sutton, “Assembly Algorithms for Next-Generation Sequencing Data,” Genomics 95 (6), 315-327 (2010).
    doi 10.1016/j.ygeno.2010.03.001
  2. E. Balas and N. Christofides, “A Restricted Lagrangean Approach to the Traveling Salesman Problem,” Math. Program. 21 (1), 19-46 (1981).
    doi 10.1007/BF01584228
  3. Concorde TSP Solver.
    http://www.math.uwaterloo.ca/tsp/concorde.html.(Cited November 25, 2024).
  4. V. V. Burkhovetskiy, “Optimization and Parallelization of the Simplified Balas’ and Christofides’ Algorithm for the Traveling Salesman Problem,” Program Systems: Theory and Applications 11 (4), 3-16 (2020).
    doi 10.25209/2079-3316-2020-11-4-3-16
    http://psta.psiras.ru/read/psta2020_4_3-16.pdf. (Cited November 25, 2024).
  5. M. A. Posypkin and I. Kh. Sigal, “A Combined Parallel Algorithm for Solving the Knapsack Problem,” Izv. Akad. Nauk, Teor. Sist. Upravl., No. 4, 50-58 (2008) [J. Comput. Syst. Sci. Int. 47 (4), 543-551 (2008)].
    doi 10.1134/S1064230708040072
  6. P. Feautrier, “A Parallelization Framework for Recursive Tree Programs,” in Lecture Notes in Computer Science (Springer, Heidelberg, 1998), Vol. 1470, pp. 470-479.
    doi 10.1007/BFb0057890
  7. D. I. Lichmanov, I. V. Afanasyev, and Vad. V. Voevodin, “Performance Study of the Architecture-Independent VGL Framework for Efficient Implementation of Graph Algorithms,” Numerical Methods and Programming 24 (4), 485-499 (2023).
    https://doi.org/10.26089/NumMet.v24r433. (Cited November 25, 2024).
  8. N. Christofides, “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem,” Oper. Res. Forum 3, Article Number 20 (2022).
    doi 10.1007/s43069-021-00101-z
  9. K. A. Barkalov, V. V. Ryabov, and S. V. Sidorov, “Some Local and Global Search Balancing Methods in Parallel Global Optimization Algorithms,” Numerical Methods and Programming 11 (4), 382-387 (2010).
    http://mi.mathnet.ru/vmp333.(Cited November 25, 2024).
  10. V. Burkhovetskiy and B. Steinberg, “An Exact Parallel Algorithm for Traveling Salesman Problem,”
    https://dl.acm.org/doi/10.1145/3166094.3166108.(Cited November 25, 2024).
  11. V. V. Burkhovetskiy, “Implementation of the Exact Algorithm for the Traveling Salesman Problem Based on Modified Balas and Christofides Algorithm,”
    https://ops.rsu.ru/download/progs/BalasChristofides_v1_0.zip. (Cited November 29, 2024).
  12. N. Christofides, Graph Theory: An Algorithmic Approach (Academic Press, Cambridge, 1975; Mir, Moscow, 1978).
  13. V. V. Burkhovetskiy, Optimization and Parallelization of the Simplified Balas’ and Christofides’ Algorithm for the Traveling Salesman Problem (Inst. Matem. Mekh. Komp’yut. Nauk, Rostov-on-Don, 2018).
    http://2018.nscf.ru/TesisAll/4Students/237_BurkhovetskiyVV.pdf. (Cited November 25, 2024) [in Russian].

License

Copyright (c) 2024 В. В. Бурховецкий, Б. Я. Штейнберг

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.