This article is cited in 5 scientific papers (total in 5 papers)
Computational Methods in Discrete Mathematics
Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method
Yu. L. Kostyuk
Tomsk State University, Tomsk, Russia
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.
travelling salesman problem, branch-and-bound method, computing experiment.
PDF file (882 kB)
Yu. L. Kostyuk, “Effective implementation of algorithm for solving the travelling salesman problem by branch-and-bound method”, Prikl. Diskr. Mat., 2013, no. 2(20), 78–90
Citation in format AMSBIB
\paper Effective implementation of algorithm for solving the travelling salesman problem by 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: uluchshennaya nizhnyaya granitsa v metode vetvei i granits”, PDM, 2013, no. 4(22), 73–81
V. V. Vasilchikov, “Ob optimizatsii i rasparallelivanii algoritma Littla dlya resheniya zadachi kommivoyazhera”, Model. i analiz inform. sistem, 23:4 (2016), 401–411
V. V. Vasilchikov, “On optimization and parallelization of the little algorithm for solving the travelling salesman problem”, Autom. Control Comp. Sci., 51:7 (2017), 551–557
V. V. Burkhovetskiy, B. Ya. Steinberg, “Parallelizing an exact algorithm for the traveling salesman problem”, 6th International Young Scientist Conference on Computational Science (YSC 2017), Procedia Computer Science, 119, eds. A. Klimova, A. Bilyatdinova, J. Kortelainen, A. Boukhanovsky, Elsevier Science BV, 2017, 97–102
Yu. L. Kostyuk, “Zadacha kommivoyazhera: priblizhennyi algoritm po metodu vetvei i granits s garantirovannoi tochnostyu”, PDM, 2019, no. 45, 104–112
|Number of views:|