Algorithmic strategies for a fast exploration of the TSP 4-OPT neighborhood

We describe an effective algorithm for exploring the 4-OPT neighborhood for the Traveling Salesman Problem. 4-OPT moves change a tour into another by replacing four of its edges. The best move can be found by a Theta(n(4)) algorithm by complete enumeration, but a Theta(n(3)) dynamic programming algorithm exists in the literature. Furthermore a Theta(n(2)) algorithm also exists for a particular subset of symmetric 4-OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at O(n(2.5))) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best 4-OPT move, and discuss the strength of the 4-OPT neighborhood compared to 2- and 3-OPT.