The 4-OPT neighborhood for the TSP contains Θ(n4) moves so that finding the best move effectively requires some ingenuity. Recently, de Berg et al. have given a Θ(n3) dynamic program, but the cubic complexity is still too large for using 4-OPT in practice. We describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm. This is much faster than the DP procedure, achieving speedups of two to three orders of magnitude on all instances we tested.
Algorithmic Strategies for a Fast Exploration of the TSP 4-OPT Neighborhood
Lancia, Giuseppe
;
2019-01-01
Abstract
The 4-OPT neighborhood for the TSP contains Θ(n4) moves so that finding the best move effectively requires some ingenuity. Recently, de Berg et al. have given a Θ(n3) dynamic program, but the cubic complexity is still too large for using 4-OPT in practice. We describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm. This is much faster than the DP procedure, achieving speedups of two to three orders of magnitude on all instances we tested.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
ods2019.pdf
non disponibili
Descrizione: articolo
Tipologia:
Documento in Pre-print
Licenza:
Non pubblico
Dimensione
310.54 kB
Formato
Adobe PDF
|
310.54 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
