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, experimentally, 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 uniform 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 performance 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.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0169) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0169). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.