Geodesic
The travelling salesman problem: improved lower bound in the branch-and-bound method
Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 73-81
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{PDM_2013_4_a7,
     author = {Yu. L. Kostyuk},
     title = {The travelling salesman problem: improved lower bound in the branch-and-bound method},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {73--81},
     year = {2013},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_4_a7/}
}
TY  - JOUR
AU  - Yu. L. Kostyuk
TI  - The travelling salesman problem: improved lower bound in the branch-and-bound method
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 73
EP  - 81
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_4_a7/
LA  - ru
ID  - PDM_2013_4_a7
ER  - 
%0 Journal Article
%A Yu. L. Kostyuk
%T The travelling salesman problem: improved lower bound in the branch-and-bound method
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 73-81
%N 4
%U http://geodesic.mathdoc.fr/item/PDM_2013_4_a7/
%G ru
%F PDM_2013_4_a7
Yu. L. Kostyuk. The travelling salesman problem: improved lower bound in the branch-and-bound method. Prikladnaâ diskretnaâ matematika, no. 4 (2013), pp. 73-81. http://geodesic.mathdoc.fr/item/PDM_2013_4_a7/

[1] Little J. D. C., Murty K. G., Sweeney D. W., Karel C., “An algorithm for the Traveling Salesman Problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[2] Kostyuk Yu. L., “Effektivnaya realizatsiya algoritma resheniya zadachi kommivoyazhera metodom vetvei i granits”, Prikladnaya diskretnaya matematika, 2013, no. 2(20), 78–90

[3] Dantsig Dzh., Lineinoe programmirovanie, ego primeneniya i obobscheniya, Per. s angl., Progress, M., 1966

[4] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Per. s angl., Mir, M., 1979, 536 pp. | MR

[5] Kheld M., Karp R. M., “Primeneniya dinamicheskogo programmirovaniya k zadacham uporyadochivaniya”, Kib. sbornik, staraya seriya, 9, Mir, M., 1964, 202–218

[6] Kostyuk Yu. L., Modifitsirovannyi algoritm resheniya zadachi kommivoyazhera metodom vetvei i granits, Versiya 2. Programma i modul s opisaniem klassa: yazyk Paskal v sisteme Delphi. Elektronnyi resurs: , 2013, iyul http://www.inf.tsu.ru/Decanat/Staff.nsf/people/KostjukJuL

[7] Kostyuk Yu. L., Modifitsirovannyi algoritm resheniya zadachi kommivoyazhera metodom vetvei i granits s uluchshennoi nizhnei granitsei, Programma i modul s opisaniem klassa: yazyk Paskal v sisteme Delphi. Elektronnyi resurs: , 2013, avgust http://www.inf.tsu.ru/Decanat/Staff.nsf/people/KostjukJuL