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

  • Walton Coutinho
  • Artur Alves Pessoa
  • Anand Subramanian
  • Roberto do Nascimento
    • Categories Combinatorial Optimization, Second-Order Cone Programming Short URL: https://optimization-online.org/?p=12768

    This paper deals with the Close-Enough Traveling Salesman Problem (CETSP). In the CETSP, 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 (SOCP). 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 both instances in the two- and three-dimensional space.

    Citation

    Submitted to INFORMS Transportation Science

    Article

    Download

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