POLYNOMIALLY SOLVABLE CASES OF THE TRAVELING SALESMAN PROBLEM AND A NEW EXPONENTIAL NEIGHBORHOOD

Let A = (a(ij)) be the distance matrix of an arbitrary (asymmetric) traveling salesman problem and let tau = tau(1) tau(2)...tau(m) be the optimal solution of the corresponding assignment problem with the subtours tau(1), tau(2),...,tau(m). By choosing (m - 1) transpositions (k, l) with k is an element of tau(i-1), l is an element of tau(i) (i = 2,...,m) and patching the subtours by using these transpositions in any order, we get a set of cyclic permutations. It will be shown that within this set of cyclic permutations a tour with minimum distance can be found by O(n(2)\tau\*) operations, where \tau\* is the maximum number of nodes in a subtour of tau. Moreover, applying this result to the case when A = (a(ij)) is a permuted distribution matrix (Monge-matrix) and the patching graph G(tau) is a multipath, a result of Gaikov can be improved: By combining the above theory with a result of Park a linear algorithm for finding an optimal TSP solution can be derived, provided tau is already known.