Exact algorithms and heuristics for capacitated covering salesman problems

• DOI: 10.48550/arxiv.2403.06995
• Publication Date: 2024-03-03
• Authors: Lucas Porto Maziero; Fábio Luiz Usberti; Celso Cavellucci
• Keywords: Heuristics

This paper introduces the Capacitated Covering Salesman Problem (CCSP), approaching notion of service by coverage in capacitated vehicle routing problems. In CCSP, locations where vehicles can transit are provided, some which have customers with demands. The objective is to through a fleet based depot, minimizing total distance traversed vehicles. CCSP unique sense that customers, be serviced, do not need visited vehicle. Instead, they serviced if within area assumption motivated applications unreachable (e.g., forbidden access vehicles) or visiting every customer impractical. this work, optimization methodologies proposed for on ILP (Integer Linear Programming) and BRKGA (Biased Random-Key Genetic Algorithm) metaheuristic. Computational experiments conducted benchmark instances evaluate performance respect primal bounds. Furthermore, our formulation extended order create novel MILP (Mixed Integer Multi-Depot Tour Vehicle Routing (MDCTVRP). show outperformed previous state-of-the-art exact approach optimality gaps. particular, optimal solutions were obtained several previously unsolved instances.