Parallel software tools and technologies

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

V. V. Burkhovetskiy, B. Ya. Steinberg

Institute of Mathematics, Mechanics and Computer Sciences, Southern Federal University, Rostov-on-Don

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.

Keywords: traveling salesman problem, exact algorithm, heuristic algorithm, parallel algorithm, branch-and-bound.

UDC: 004.023

Received: 26.09.2024

DOI: 10.26089/NumMet.v25r436