Prikladnaya Diskretnaya Matematika
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., 2013, Number 4(22), Pages 73–81 (Mi pdm434)  

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

Computational Methods in Discrete Mathematics

The travelling salesman problem: improved lower bound in the branch-and-bound method

Yu. L. Kostyuk

Tomsk State University, Tomsk, Russia

Abstract: In a previous article, the author describes the implementation of Little's algorithm for solving the travelling salesman problem by the branch-and-bound method and gives a new modified algorithm where an additional transformation of the distance matrix is used at each step of the solution. This improves the lower bound for the exact solution and speeds up its work, but only in the case of non-symmetric matrices. In the present article, a method is described to further improve the lower bound, especially in the case of symmetric matrices. A new algorithm based on it is constructed. With the help of a computer simulation, some estimates of the constants in the formulas for the algorithm complexity are obtained for three types of distance matrices: 1) non-symmetric matrices with random distances, 2) matrices with the Euclidean distances between random points in the square, and 3) non-symmetric matrices with random distances satisfying the triangle inequality.

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

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

Citation: Yu. L. Kostyuk, “The travelling salesman problem: improved lower bound in the branch-and-bound method”, Prikl. Diskr. Mat., 2013, no. 4(22), 73–81

Citation in format AMSBIB
\Bibitem{Kos13}
\by Yu.~L.~Kostyuk
\paper The travelling salesman problem: improved lower bound in the branch-and-bound method
\jour Prikl. Diskr. Mat.
\yr 2013
\issue 4(22)
\pages 73--81
\mathnet{http://mi.mathnet.ru/pdm434}


Linking options:
  • http://mi.mathnet.ru/eng/pdm434
  • http://mi.mathnet.ru/eng/pdm/y2013/i4/p73

    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

    This publication is cited in the following articles:
    1. Yu. L. Kostyuk, “Zadacha kommivoyazhera: priblizhennyi algoritm po metodu vetvei i granits s garantirovannoi tochnostyu”, PDM, 2019, no. 45, 104–112  mathnet  crossref
    2. Matsyi O., “Approaches to Solving Basic Problems of Closed Routes”, 15Th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (Tcset - 2020), IEEE, 2020, 69–72  crossref  isi  scopus
  • Прикладная дискретная математика
    Number of views:
    This page:232
    Full text:77
    References:23

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021