Exponential neighbourhood local search for the traveling salesman problem

We analyse an approach to the TSP, introduced by Punnen (Research Report, University of New Brunswick, St. John, Canada, 1996), which is a generalization of approaches by Sarvanov and Doroshko (In: Software: Algorithms and Programs, Math. Inst. Belorusian Acad. Sci., Minsk, No. 31, 1981: 11-13) and Gutin (In: Proceedings of the USSR Conference System Res., Moscow: 1984: 184-185). We show that Punnen's approach allows one to find the best among Theta(exp(root n/2) (n/2)!/n(1/4)) tours in the TSP with it cities (n is even) in O(n(3)) time. We describe an O(n(1+beta))-time algorithm (for any beta is an element of (0, 2]) that constructs the best among 2(Theta(n log n)) tours. This algorithm provides low-complexity solutions to a problem by Burkard et al. (In: Proc. IPCO V, Lecture Notes in Computer Science, Vol. 1084, Bel-lin: Springer, 1996: 490-504) and may be quite useful for large-scale instances of the TSP. We also show that for every positive integer r there exists an O(r(5)n)-time algorithm that finds the best among Omega(r(n)) tours. This improves a result of Balas and Simonetti Management Sci. Res. Report MSRR-617, Canegve Mellon University, Pittsburgh, (1996) who showed that the best among Omega(r(n)) tours can be obtained in time O(r(2)2(r)n). (C) 1999 Elsevier Science Ltd. All rights reserved.