  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-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 uniform random numbers in [0, 1] or
Euclidean distances between random points in the plane. We prove that, for any
probability p: (i) there is a heuristic in the family which can find the best
move with probability at least p in average-time O(n^3/2) for uniform instances
and O(n) for Euclidean instances; (ii) the exact algorithm take lesser time
then the above heuristic on all instances on which the heuristic finds the best
move. During local search, while the tour becomes less and less random, the
speed of our algorithm worsens until it becomes quadratic. We then discuss how
to fine tune a successful hybrid approach, made of our algorithm in the
beginning followed by the usual quadratic enumeration.
