EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Branch-and-cut algorithms for the covering salesman problem

Lucas Porto Maziero, Fábio Luiz Usberti, Celso Cavellucci

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →