Exponential neighbourhood local search for the traveling salesman problem

We analyse an approach to the TSP, introduced by Punnen, which is a generalization of approaches by Sarvanov and Doroshko, and Gutin. We show that Punnen's approach allows one to find the best among Θ(exp(√(n/2)) (n/2)!/n^1/4) tours in the TSP with n cities (n is even) in O(n³) time. We describe an O(n^{1 + β})-time algorithm (for any β ∈(0, 2]) that constructs the best among 2^{Θ(n log n)} tours. This algorithm provides low-complexity solutions to a problem by Burkard et al. and may be quite useful for large-sale instances of the TSP. We also show that for every positive integer r there exists an O(r⁵n)-time algorithm that finds the best among Ω(rⁿ) tours. This improves a result of Balas and Simonetti who showed that the best among Ω(rⁿ) tours can be obtained in time O(r²2^rn).