We describe an exact algorithm for finding the best 2-OPT move that, experi-
mentally, was observed to be much faster than the standard quadratic approach for a large
part of a best-improvement local search convergence starting at a random tour. To analyze
its average-case complexity, we introduce a family of heuristic procedures and discuss
their complexity when applied to a random tour in graphs whose edge costs are either uni-
form random numbers in [0, 1] or Euclidean distances between random points in the plane.
We prove that, for any probability p, there is a heuristic in the family that can find the best
2-OPT move with probability at least p in average-time O(n log n) for uniform instances
and O(n) for Euclidean instances. The exact algorithm is then proved to be even faster in
the sense that in those instances in which a heuristic finds the best move, the exact algorithm
finds it in a smaller time. We give empirical evidence that a slight variant of our algorithm
finds the best move in O(n) time on both types of instances, achieving the best possible per-
formance for this particular problem. Computational experiments are reported to show the
effectiveness of our algorithms, both in best-improvement and in first-improvement 2-OPT
local search.
