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: email@example.com
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
Initial download of the metrics may take a while.