Volume 55, Number 3, May-June 2021
|Page(s)||1441 - 1457|
|Published online||08 June 2021|
Reactive GRASP for the Prize-collecting Covering Tour Problem
Universidade Federal do Maranhão, Av. dos Portugueses, 1966 – Vila Bacanga, Sao Luís, MA 65080-805, Brazil
2 Universidade Federal Fluminense, Instituto de Computação, Rua Passo da Pátria 156 – São Domingos, Niterói, RJ 24210-240, Brazil
3 Institute of Education, Science and Technology of Piauí, R. Alvaro Mendes, 94 – Centro (Sul), Teresina, PI 64000-040, Brazil
4 Federal Institute of Education, Science and Technology of Rio de Janeiro, Rua José Breves, 550, Centro, Pinheiral, RJ 27197-000, Brazil
* Corresponding author: firstname.lastname@example.org
Accepted: 6 April 2021
This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) for the Prize-Collecting Covering Tour Problem (PCCTP), which is the problem of finding a route for traveling teams that provide services to communities geographically distant from large urban locations. We devised a novel hybrid heuristic by combining a reactive extension of the GRASP with Random Variable Neighborhood Search (VND) meta-heuristic for the purpose of solving the PCCTP. Computational experiments were conducted on a PCCTP benchmark from the literature, and the results demonstrate our approach provides a significant improvement in solving PCCTP and comparable with the state-of-the-art, mainly regarding the computational processing time.
Mathematics Subject Classification: 90C10 / 90C11 / 90C08 / 90C05
Key words: Prize-collecting covering tour problem / hybrid heuristic / GRASP / VND
© EDP Sciences, ROADEF, SMAI 2021
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.