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
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.
travelling salesman problem, branch-and-bound method, computing experiment.
PDF file (561 kB)
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
\paper The travelling salesman problem: improved lower bound in the branch-and-bound method
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Yu. L. Kostyuk, “Zadacha kommivoyazhera: priblizhennyi algoritm po metodu vetvei i granits s garantirovannoi tochnostyu”, PDM, 2019, no. 45, 104–112
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
|Number of views:|