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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

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}


Linking options:
  • http://mi.mathnet.ru/eng/pdm677
  • http://mi.mathnet.ru/eng/pdm/y2019/i3/p104

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:63
    Full text:13
    References:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020