Upper Bound Computation for the Multiple Close-Enough Traveling Salesman Problem

This paper addresses the Multiple Close-Enough Traveling Salesman Problem, a variant of the Close-Enough Traveling Salesman Problem, where multiple vehicles are used to visit a given number of points. A vehicle visits a point if it passes through the neighborhood set of that point. The goal of the problem is to minimize the longest of the defined routes. We face the problem by using a discretization schema that reduces it to the Multiple Generalized Traveling Salesman Problem for which we propose a Mixed Integer Linear Programming formulation. The use of discretization schema introduces a discretization error that makes the optimal solution value of our model an upper bound of the optimal solution value of the Multiple Close-Enough Traveling Salesman Problem. Moreover, we apply a graph reduction algorithm to remove arcs and nodes without changing the optimal solution of the problem. We provide proof of the correctness of this algorithm, and we show that it significantly reduces the s ize of the instances tested. We verified the performance of our model on the benchmark instances of Close-Enough Traveling Salesman Problem.