We describe an effective algorithm for exploring the 4 -OPT neighborhood for the Traveling Salesman Problem. 4 -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a Θ (n4) algorithm by complete enumeration, but a Θ (n3) dynamic programming algorithm exists in the literature. Furthermore a Θ (n2) algorithm also exists for a particular subset of symmetric 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(n2.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 -OPT move, and discuss the strength of the 4 -OPT neighborhood compared to 2- and 3 -OPT.

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

Lancia G.;
2023-01-01

Abstract

We describe an effective algorithm for exploring the 4 -OPT neighborhood for the Traveling Salesman Problem. 4 -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a Θ (n4) algorithm by complete enumeration, but a Θ (n3) dynamic programming algorithm exists in the literature. Furthermore a Θ (n2) algorithm also exists for a particular subset of symmetric 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(n2.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 -OPT move, and discuss the strength of the 4 -OPT neighborhood compared to 2- and 3 -OPT.
File in questo prodotto:
File Dimensione Formato  
s10732-023-09523-w (1).pdf

accesso aperto

Licenza: Creative commons
Dimensione 566.66 kB
Formato Adobe PDF
566.66 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1270764
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact