Branch-and-cut algorithms for the covering salesman problem
| Autor: | Lucas Porto Maziero, Fábio Luiz Usberti, Celso Cavellucci |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Computational Complexity (cs.CC) Computer Science::Computational Complexity Management Science and Operations Research MathematicsofComputing_DISCRETEMATHEMATICS Computer Science Applications Theoretical Computer Science |
| Zdroj: | RAIRO - Operations Research. 57:1149-1166 |
| ISSN: | 2804-7303 0399-0559 |
| Popis: | The Covering Salesman Problem (CSP) is a generalization of the Traveling Salesman Problem in which the tour is not required to visit all vertices, as long as all vertices are covered by the tour. The objective of CSP is to find a minimum length Hamiltonian cycle over a subset of vertices that covers an undirected graph. In this paper, valid inequalities from the generalized traveling salesman problem are applied to the CSP in addition to new valid inequalities that explore distinct aspects of the problem. A branch-and-cut framework assembles exact and heuristic separation routines for integer and fractional CSP solutions. Computational experiments show that the proposed framework outperformed methodologies from literature with respect to optimality gaps. Moreover, optimal solutions were proven for several previously unsolved instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|