Abstract:
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.
Fulltext:
PDF file (882 kB)