Title: A hybrid heuristic based on GRASP and RVND metaheuristics for the prise-collecting covering tour problem

Authors: Glaubos Clímaco; Isabel Rosseti; Rogério Da Silva; Marcos Guerine

Addresses: Computer Science Department, Federal University of Maranhão, São Luís, Brazil ' Institute of Computing, Fluminense Federal University, Niterói, Brazil ' Federal Institute of Education, Science and Technology of Piauí, Teresina, Brazil ' Federal Institute of Education, Science and Technology of Rio de Janeiro, Pinheiral, Brazil

Abstract: The provision of social, medical, or legal assistance to communities geographically distant from large urban locations has been a concern of the various public, philanthropic or private entities. This concern led to the emergence of the prise-collecting covering tour problem (PCCTP), which seeks to find a tour for travelling teams that provide services to these communities. This work proposes a novel hybrid heuristic based on greedy randomised adaptive search procedure (GRASP) and random variable neighbourhood search (RVND) meta-heuristics 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.

Keywords: prise-collecting covering tour problem; PCCTP; greedy randomised adaptive search procedure; GRASP; random variable neighbourhood search; RVND; hybrid heuristic.

DOI: 10.1504/IJLSM.2022.122977

International Journal of Logistics Systems and Management, 2022 Vol.41 No.3, pp.349 - 370

Received: 04 Jun 2020
Accepted: 09 Jan 2021

Published online: 19 May 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article