|
|||||
|
|
A novel discretization scheme for the close enough traveling salesman problem |
|
| Affiliation: | 1. Department of Biosciences and Territory, University of Molise, Italy;2. Department of Mathematics, University of Salerno, Italy;3. Robert H. Smith School of Business, University of Maryland, USA;1. College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou, 350002 China;2. Department of Computer Engineering and Computer Science, University of Louisville, KY, 40217 USA;1. School of Mathematics, Statistics and Computer Science, University of Kwazulu-Natal, Westville Campus, Private Bag X54001, Durban 4000, South Africa;2. Faculties of Mathematics and Computer Science, West University of Timisoara, Timisoara, Romania |
| 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. |
| Keywords: | Close-enough Traveling salesman problem Discretization scheme |
| 本文献已被 ScienceDirect 等数据库收录！ | |