Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the Θ(n3 ) enumeration of all triples is likely to exist for this problem, but algorithms with average case O(n3−ɛ ) are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by O(n2.5 )) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances.

Finding the Best 3-{OPT} Move in Subcubic Time

Giuseppe Lancia
Primo
;
2020-01-01

Abstract

Given a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the Θ(n3 ) enumeration of all triples is likely to exist for this problem, but algorithms with average case O(n3−ɛ ) are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by O(n2.5 )) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances.
File in questo prodotto:
File Dimensione Formato  
algorithms-990947.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 359.4 kB
Formato Adobe PDF
359.4 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/1193990
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact