This paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound for the optimal solution. Moreover, we apply a graph reduction algorithm that significantly reduces the problem size and speeds up computation of the bounds. We evaluate the effectiveness and the performance of our approach on several benchmark instances. The computational results show that our algorithm is faster than the other algorithms available in the literature and that the bounds it provides are almost always more accurate.
A novel discretization scheme for the close enough traveling salesman problem
CARRABS, FRANCESCO
;CERRONE, CARMINE;CERULLI, Raffaele;
2017-01-01
Abstract
This paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound for the optimal solution. Moreover, we apply a graph reduction algorithm that significantly reduces the problem size and speeds up computation of the bounds. We evaluate the effectiveness and the performance of our approach on several benchmark instances. The computational results show that our algorithm is faster than the other algorithms available in the literature and that the bounds it provides are almost always more accurate.File | Dimensione | Formato | |
---|---|---|---|
2016_CETSP_COR_DOI_pp.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Creative commons
Dimensione
2.45 MB
Formato
Adobe PDF
|
2.45 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.