A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem
Published Online:5 Oct 2016https://doi.org/10.1287/ijoc.2016.0711
Abstract
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.
