Exact and approximate formulations for the close-enough TSP

This work addresses the Close-Enough Traveling Salesman Problem (CETSP), a variant of the classic traveling salesman problem in which we seek to visit neighborhoods of points in the plane (defined as disks) rather than specific points. We present two exact formulations for this problem based on second-order cone programming (SOCP), along with approximated mixed-integer linear formulations derived from polyhedral approximations of the second-order cone constraints. While SOCP models yield optimal solutions, they are quite inefficient for larger instances. Thus, we proposed several decomposition schemes based on exact SOCP models and their corresponding MILP approximations, and several cuts based on SOCP duality and classic integer L-shape methods. Moreover, we illustrate why Generalized Benders cuts cannot be applied to these problems and the consequences of doing so anyway. We test all the proposed procedures over a wide range of instances and analyze the results for different instance features (i.e., number of points and radius size). We note that exact decomposition methods based on the MILP approximation with a SOCP subproblem achieve the best overall performance, which illustrates the benefit of combining methodologies from the MILP and SOCP literature to address the problem.

Article

Download

View PDF