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

Giuseppe Lancia () and Paolo Vidoni ()
Additional contact information
Giuseppe Lancia: Dipartimento di Matematica, Informatica e Fisica, University of Udine, 33100 Udine, Italy
Paolo Vidoni: Dipartimento di Scienze Economiche e Statistiche, University of Udine, 33100 Udine, Italy

INFORMS Journal on Computing, 2025, vol. 37, issue 5, 1202-1222

Abstract: 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.

Keywords: traveling salesman; combinatorial optimization; 2-OPT neighborhood; heuristics; applied probability (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0169 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:5:p:1202-1222

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().