A Hybrid Heuristic for the Routing Problem with Multi-Vehicle Coverage and Prize Collection

The classical Vehicle Routing Problem (VRP) assumes direct service to customers, which is not suitable in applications involving intermediate facilities. In this context, the Covering Tour Problem (CTP) considers indirect service through facilities. In this work, we propose the Multi-Vehicle Covering Tour Problem with Prize Collecting (m-CTPPC), which integrates multiple vehicles and minimum prize collection constraints. The goal is to determine minimum-cost routes that simultaneously satisfy coverage and prize requirements. To solve the problem, we develop a hybrid heuristic that combines solution construction, diversification via ruin-and-recreate, and post optimization through a route-based mixed-integer programming formulation. Routes are stored in a pool and reused throughout the process. The approach is evaluated on 378 instances derived from the CTP-PC. Results show that route combination reduces solution cost by 1.7% on average and provides benchmarks under different time limits.