Prikl. Diskr. Mat., 2019, Number 45, Pages 104–112
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
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 %$.
traveling salesman problem, branch-and-border method, approximate algorithm, local search, computational experiment.
PDF file (613 kB)
Yu. L. Kostyuk, “The traveling salesman problem: approximate algorithm by branch-and-bound method with guaranteed precision”, Prikl. Diskr. Mat., 2019, no. 45, 104–112
Citation in format AMSBIB
\paper The traveling salesman problem: approximate algorithm by branch-and-bound method with~guaranteed precision
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|