A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem
| Autor: | Roberto Quirino do Nascimento, Artur Alves Pessoa, Anand Subramanian, Walton Pereira Coutinho |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Traveling purchaser problem
050210 logistics & transportation 021103 operations research Branch and bound 05 social sciences Nearest neighbour algorithm 0211 other engineering and technologies General Engineering 02 engineering and technology 2-opt Travelling salesman problem Combinatorics 0502 economics and business Christofides algorithm Greedy algorithm Bottleneck traveling salesman problem MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | INFORMS Journal on Computing. 28:752-765 |
| ISSN: | 1526-5528 1091-9856 |
| DOI: | 10.1287/ijoc.2016.0711 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|