RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat., 2019, Number 45, Pages 104–112 (Mi pdm677)

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.

 Funding Agency Grant Number Ministry of Education and Science of the Russian Federation 2.4218.2017/4.6

DOI: https://doi.org/10.17223/20710410/45/12

Full text: PDF file (613 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.7

Citation: 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
\Bibitem{Kos19} \by Yu.~L.~Kostyuk \paper The traveling salesman problem: approximate algorithm by branch-and-bound method with~guaranteed precision \jour Prikl. Diskr. Mat. \yr 2019 \issue 45 \pages 104--112 \mathnet{http://mi.mathnet.ru/pdm677} \crossref{https://doi.org/10.17223/20710410/45/12}