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

CERRONE, CARMINE;CERULLI, Raffaele;
2017

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.
9783319571850
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: http://hdl.handle.net/11695/64762
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
social impact