A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem

This paper addresses the close‐enough traveling salesman problem. In this problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on branch‐and‐bound and second order cone programming. The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider instances both in two‐ and three‐dimensional space.