A move of the 3-OPT neighborhood for the Traveling Salesman Problem consists in removing any three edges of the tour and replacing them with three new ones. The standard algorithm to find the best possible move is cubic, both in its worst and average time complexity. Since TSP instances of interest can have thousands of nodes, up to now it has been impossible to use the 3-OPT local search on anything other than quite small instances. In this paper we describe an alternative algorithm whose average complexity appears to be quadratic and which allowed us to use 3-OPT on instances with several thousand nodes. The algorithm is based on a rule for quickly choosing two out of three edges in a good way, and then completing the choice in linear time. To this end, the algorithm uses max-heaps as a suitable data structure.

Speeding-up the exploration of the 3-OPT neighborhood for the TSP

Giuseppe Lancia
;
2018-01-01

Abstract

A move of the 3-OPT neighborhood for the Traveling Salesman Problem consists in removing any three edges of the tour and replacing them with three new ones. The standard algorithm to find the best possible move is cubic, both in its worst and average time complexity. Since TSP instances of interest can have thousands of nodes, up to now it has been impossible to use the 3-OPT local search on anything other than quite small instances. In this paper we describe an alternative algorithm whose average complexity appears to be quadratic and which allowed us to use 3-OPT on instances with several thousand nodes. The algorithm is based on a rule for quickly choosing two out of three edges in a good way, and then completing the choice in linear time. To this end, the algorithm uses max-heaps as a suitable data structure.
File in questo prodotto:
File Dimensione Formato  
ods18.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 257.65 kB
Formato Adobe PDF
257.65 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/1128935
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact