A novel discretization scheme for the close enough traveling salesman problem. (February 2017)

• Record Type: Journal Article
• Authors: Carrabs, Francesco; Cerrone, Carmine; Cerulli, Raffaele; Gaudioso, Manlio
• Is Part Of: Computers & operations research. Volume 78(2017)
• Page Start: 163
• Page End: 171
• Publication Date: 2017-02
• Subjects: Close-enough -- Traveling salesman problem -- Discretization scheme; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.09.003
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Abstract : Highlights: We 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.