This article is cited in 1 paper

Computational Methods in Discrete Mathematics

The traveling salesman problem: approximate algorithm by branch-and-bound method with guaranteed precision

Yu. L. Kostyuk

Tomsk State University, Tomsk, Russia

Abstract: To solve the traveling salesman problem with distance matrix of order $n$, we propose an approximate algorithm based on the branch-and-border method. For clipping, an increased least estimate of the current partial solution is used. This guarantees a predetermined value $\varepsilon$ of the whole solution error. A computational experiment for distance matrices of four kinds of distributions was carried out. A uniform random (asymmetric) distribution as well as matrices of Euclidean distances between random points (a symmetric distribution) were used. In the latter case, a local search was additionally applied. Estimates for the power $p$ in the polynomial computational complexity $O(n^p)$ of the algorithm for various kinds of distributions and various values of error $\varepsilon$ are obtained. For a uniform random distribution and $n\leq 1000$, the obtained estimate of the power $p$ turned out to be close to $2.8$ and of an average value of error to be $1\,\%$.

Keywords: traveling salesman problem, branch-and-border method, approximate algorithm, local search, computational experiment.

UDC: 519.7

DOI: 10.17223/20710410/45/12

Bibliographic databases:

•