Algorithmic strategies for a fast exploration of the TSP $$4$$ 4 -OPT neighborhood

Giuseppe Lancia () and Marcello Dalpasso ()
Additional contact information
Giuseppe Lancia: University of Udine
Marcello Dalpasso: University of Padova

Journal of Heuristics, 2024, vol. 30, issue 3, No 1, 109-144

Abstract: Abstract We describe an effective algorithm for exploring the $$4$$ 4 -OPT neighborhood for the Traveling Salesman Problem. $$4$$ 4 -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a $$\Theta (n^4)$$ Θ ( n 4 ) algorithm by complete enumeration, but a $$\Theta (n^3)$$ Θ ( n 3 ) dynamic programming algorithm exists in the literature. Furthermore a $$\Theta (n^2)$$ Θ ( n 2 ) algorithm also exists for a particular subset of symmetric $$4$$ 4 -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at $$O(n^{2.5})$$ O ( n 2.5 ) ) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best $$4$$ 4 -OPT move, and discuss the strength of the $$4$$ 4 -OPT neighborhood compared to 2- and $$3$$ 3 -OPT.

Keywords: Traveling salesman problem; 4-OPT; Local search (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-023-09523-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:30:y:2024:i:3:d:10.1007_s10732-023-09523-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-023-09523-w

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().