General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Prikl. Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

Prikl. Diskr. Mat., 2013, Number 2(20), Pages 78–90 (Mi pdm410)  

This article is cited in 5 scientific papers (total in 5 papers)

Computational Methods in Discrete Mathematics

Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method

Yu. L. Kostyuk

Tomsk State University, Tomsk, Russia

Abstract: The modification of Little's algorithm for solving the well-known travelling salesman problem by branch-and-bound method is proposed. At each intermediate stage of the algorithm execution, a more exact lower bound is evaluated for all variants of the route which may be built on the basis of the current partial solution. Thanks to this, the rejection of unperspective variants becomes, as a rule, much more effective, especially when applied to the random asymmetrical distance matrix. The implementations of this modified algorithm are described with the depth-first and breadth-first search, and also with the depth-first search when an approximate route with the inaccuracy prescribed arbitrarily is searched. In a computing experiment, for each algorithm implementation, the values of constants $a$ and $c$ have been evaluated for the complexity function $U(n)=a\cdot c^n$ that is the number of distance matrixes (decision tree nodes) processing by the algorithm. In any case the time of each node processing increases by 1,5–2 times while the time of processing the whole decision tree by the algorithm is significantly decreased.

Keywords: travelling salesman problem, branch-and-bound method, computing experiment.

Full text: PDF file (882 kB)
References: PDF file   HTML file
UDC: 519.7

Citation: Yu. L. Kostyuk, “Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method”, Prikl. Diskr. Mat., 2013, no. 2(20), 78–90

Citation in format AMSBIB
\by Yu.~L.~Kostyuk
\paper Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method
\jour Prikl. Diskr. Mat.
\yr 2013
\issue 2(20)
\pages 78--90

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Yu. L. Kostyuk, “Zadacha kommivoyazhera: uluchshennaya nizhnyaya granitsa v metode vetvei i granits”, PDM, 2013, no. 4(22), 73–81  mathnet
    2. V. V. Vasilchikov, “Ob optimizatsii i rasparallelivanii algoritma Littla dlya resheniya zadachi kommivoyazhera”, Model. i analiz inform. sistem, 23:4 (2016), 401–411  mathnet  crossref  mathscinet  elib
    3. V. V. Vasilchikov, “On optimization and parallelization of the little algorithm for solving the travelling salesman problem”, Autom. Control Comp. Sci., 51:7 (2017), 551–557  crossref  isi  scopus
    4. V. V. Burkhovetskiy, B. Ya. Steinberg, “Parallelizing an exact algorithm for the traveling salesman problem”, 6th International Young Scientist Conference on Computational Science (YSC 2017), Procedia Computer Science, 119, eds. A. Klimova, A. Bilyatdinova, J. Kortelainen, A. Boukhanovsky, Elsevier Science BV, 2017, 97–102  crossref  isi  scopus
    5. Yu. L. Kostyuk, “Zadacha kommivoyazhera: priblizhennyi algoritm po metodu vetvei i granits s garantirovannoi tochnostyu”, PDM, 2019, no. 45, 104–112  mathnet  crossref
  • Прикладная дискретная математика
    Number of views:
    This page:2541
    Full text:680

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