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

We describe an effective algorithm for exploring the $$4$$ 4 -OPT neighborhood for the Traveling Salesman Problem. $$4$$ 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)$$ Θ ( n 4 ) algorithm by complete enumeration, but a $$\Theta (n^3)$$ Θ ( n 3 ) dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ Θ ( n 2 ) algorithm also exists for a particular subset of symmetric $$4$$ 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})$$ 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$$ 4 -OPT move, and discuss the strength of the $$4$$ 4 -OPT neighborhood compared to 2- and $$3$$ 3 -OPT.