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

Yu. L. Kostyuk

Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 104-112

Résumé

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\,\%$.

Détail

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