An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem

Abstract

We address a variant of the Euclidean traveling salesman problem known as the close-enough traveling salesman problem (CETSP), where the traveler visits a node if it enters a compact neighborhood set of that node. We formulate a mixed-integer programming model based on a discretization scheme for the problem. Both lower and upper bounds on the optimal CETSP tour length can be derived from the solution of this model, and the quality of the bounds obtained depends on the granularity of the discretization scheme. Our approach first develops valid inequalities that enhance the bound and solvability of this formulation. We then provide two alternative formulations, one that yields an improved lower bound on the optimal CETSP tour length, and one that greatly improves the solvability of the original formulation by recasting it as a two-stage problem amenable to decomposition. Computational results demonstrate the effectiveness of the proposed methods.