This paper studies the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood of that node. We introduce an improved version of the adaptive internal discretization scheme, recently proposed in the literature, and a heuristic that combines this scheme with to a second-order cone programming algorithm. Our heuristic is able to compute tight bounds for the problem. The computational results, carried out on benchmark instances, confirm the improvements of the bounds computed with respect to the other algorithms proposed in the literature.

Improved Upper and Lower Bounds for the Close Enough Traveling Salesman Problem

CARRABS, FRANCESCO;CERRONE, CARMINE
;
CERULLI, Raffaele;D'AMBROSIO, CIRIACO
2017-01-01

Abstract

This paper studies the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood of that node. We introduce an improved version of the adaptive internal discretization scheme, recently proposed in the literature, and a heuristic that combines this scheme with to a second-order cone programming algorithm. Our heuristic is able to compute tight bounds for the problem. The computational results, carried out on benchmark instances, confirm the improvements of the bounds computed with respect to the other algorithms proposed in the literature.
2017
978-3-319-57185-0
978-3-319-57186-7
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11386/4685081
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 11
social impact