Geodesic
Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method
Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 78-90 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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

[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] Reingold E., Nivergelt Yu., Deo N., Kombinatornye algoritmy. Teoriya i praktika, per. s angl., Mir, M., 1980, 478 pp. | MR | Zbl

[3] Melamed I..I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhëra. Tochnye algoritmy”, Avtomatika i telemekhanika, 1989, no. 10, 3–29 | MR | Zbl

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

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

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