This article is cited in 3 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.

UDC: 519.7