New approaches for the prize-collecting covering tour problem

Glaubos Clímaco, Luidi Simonetti, Isabel Rosseti and Pedro Henrique González

International Journal of Industrial and Systems Engineering, 2023, vol. 45, issue 1, 101-134

Abstract: In this paper, we consider the prize-collecting covering tour problem (PCCTP), which intends to find a minimum cost tour for travelling teams that grant assistance to people located far from urban centres. We develop a branch-and-cut algorithm, some valid inequalities, and a new set of reduction rules as exact approaches. We also present a hybrid heuristic that combines a state-of-the-art heuristic for the PCCTP with integer programming techniques. Computational experiments showed that the exact approaches found several new optimal solutions while reducing CPU time, and the hybrid heuristic was able to match or improve the solution quality for many instances, along with a significant reduction of running time.

Keywords: prize-collecting covering tour problem; PCCTP; greedy randomised adaptive search procedure; GRASP; random variable neighbourhood descent; RVND; hybrid heuristic; reduction rules. (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=133526 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijisen:v:45:y:2023:i:1:p:101-134

Access Statistics for this article

More articles in International Journal of Industrial and Systems Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().