Exact algorithms and heuristics for the Capacitated Covering Salesman Problem

Institute of Computing, University of Campinas, Av. Albert Einstein 1251, 13083-852 Campinas, SP, Brazil

^* Corresponding author: fusberti@ic.unicamp.br

Received: 1 May 2025
Accepted: 23 September 2025

Abstract

We introduce the Capacitated Covering Salesman Problem (CCSP), a novel extension of classical vehicle routing that integrates the concept of service by coverage into capacity-constrained routing. In the CCSP, a fleet of vehicles based at a single depot is tasked with satisfying customer demands at minimum travel cost, where customers can be serviced indirectly by being located within the coverage range of a visited vertex. This extension addresses practical challenges in routing scenarios where direct access to every customer is either difficult or inefficient. We develop a comprehensive solution framework that combines an exact integer linear programming (ILP) formulation with a biased random-key genetic algorithm (BRKGA). The proposed ILP model captures both capacity and coverage constraints, while the BRKGA efficiently explores the solution space, especially for larger instances. Furthermore, we enhance our approach through a hybrid strategy that integrates the best solutions from the BRKGA with an exact optimization process, thereby refining the results even further. Extensive computational experiments on a benchmark set derived from established vehicle routing instances demonstrate the effectiveness and robustness of our methods. The ILP formulation is able to find optimal solutions for smaller instances, and the BRKGA consistently delivers high-quality solutions for more complex problems, with the hybrid approach yielding additional improvements. Our work not only highlights the practicality of incorporating coverage in routing but also lays a solid foundation for future research on advanced routing models that balance direct visitation with flexible service strategies.