Title: New approaches for the prize-collecting covering tour problem

Authors: Glaubos Clímaco; Luidi Simonetti; Isabel Rosseti; Pedro Henrique González

Addresses: Departamento de Informática, Universidade Federal do Maranhão, São Luís, Brazil ' Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil ' Instituto de Computação, Universidade Federal Fluminense, Niterói, Brazil ' Departamente de Ciência da Computação, Centro Federal de Educação Tecnológica Celso Suckow da Foseca, Rio de Janeiro, Brazil

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.

DOI: 10.1504/IJISE.2023.133526

International Journal of Industrial and Systems Engineering, 2023 Vol.45 No.1, pp.101 - 134

Received: 20 Jul 2021
Accepted: 20 Nov 2021
Published online: 19 Sep 2023 *

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