Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time

Giuseppe Lancia, Paolo Vidoni

We describe an exact algorithm for finding the best 2-OPT move which, experimentally, was observed to be much faster than the standard quadratic approach. To analyze its average-ca…