Average Case Subquadratic Exact and Heuristic Procedures for the Traveling Salesman 2-OPT Neighborhood

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.