Branch-and-cut algorithms for the covering salesman problem
RAIRO - Operations Research · 2023-05 · 57 (3) · 1149-1166
DOI: 10.1051/ro/2023055 ↗Kurz gefasst
Fachartikel in der Zeitschrift RAIRO - Operations Research, online erschienen am 18.05.2023. Verfasst von Lucas Porto Maziero und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Maziero, L. P., Usberti, F. L., & Cavellucci, C. (2023). Branch-and-cut algorithms for the covering salesman problem. RAIRO - Operations Research, 57(3), 1149-1166. https://doi.org/10.1051/ro/2023055
Vancouver
Maziero LP, Usberti FL, Cavellucci C. Branch-and-cut algorithms for the covering salesman problem. RAIRO - Operations Research. 2023;57(3):1149-1166. doi:10.1051/ro/2023055
BibTeX
@article{Maziero2023,
author = {Maziero, Lucas Porto and Usberti, Fábio Luiz and Cavellucci, Celso},
title = {Branch-and-cut algorithms for the covering salesman problem},
journal = {RAIRO - Operations Research},
year = {2023},
volume = {57},
number = {3},
pages = {1149--1166},
doi = {10.1051/ro/2023055}
}
EUVIMED