Algorithmic Strategies for a Fast Exploration of the TSP 4-OPT Neighborhood

The 4-OPT neighborhood for the TSP contains Θ(n4) moves so that finding the best move effectively requires some ingenuity. Recently, de Berg et al. have given a Θ(n3) dynamic program, but the cubic complexity is still too large for using 4-OPT in practice. We describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm. This is much faster than the DP procedure, achieving speedups of two to three orders of magnitude on all instances we tested