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
² Universidade Federal Fluminense, Instituto de Computação, Rua Passo da Pátria 156 – São Domingos, Niterói, RJ 24210-240, Brazil
³ Institute of Education, Science and Technology of Piauí, R. Alvaro Mendes, 94 – Centro (Sul), Teresina, PI 64000-040, Brazil
⁴ Federal Institute of Education, Science and Technology of Rio de Janeiro, Rua José Breves, 550, Centro, Pinheiral, RJ 27197-000, Brazil

^* Corresponding author: francisco.glaubos@ufma.br

Received: 22 October 2020
Accepted: 6 April 2021

Abstract

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.