Paper Info
Title
A novel discretization scheme for the close enough traveling salesman problem.
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. HighlightsWe introduce a novel discretization scheme for the close enough TSP problem.By reducing the discretization error, the new scheme allows to compute tighter upper and lower bounds for the problem.We apply an enhanced convex hull strategy to save the number of discretization points to be used.The discretization strategy allows us to assign an adaptively variable number of discretization points to each neighborhood.Numerical comparisons with some algorithms proposed in the literature are presented.
Year
DOI
Venue
2017
10.1016/j.cor.2016.09.003
Computers & OR
Keywords
Field
DocType
Close-enough,Traveling salesman problem,Discretization scheme
Bottleneck traveling salesman problem,Discretization,Mathematical optimization,Upper and lower bounds,Convex hull,Travelling salesman problem,2-opt,Graph reduction,Mathematics,Discretization of continuous features
Journal
Volume
Issue
ISSN
78
C
0305-0548
Citations 
PageRank 
References 
8
0.57
5
Authors
4
Name
Order
Citations
PageRank
Francesco Carrabs119915.55
Carmine Cerrone2407.45
R. Cerulli325223.85
Manlio Gaudioso420723.95