A Hybrid Meta-heuristic for the Fixed-Radius Continuous Disc Coverage Problem

The Fixed Radius Continuous Disk Coverage Problem (PCCD) is an NP-hard problem in the area of facility location. It consists of positioning as few fixed-radius disks as possible to cover a set of points in the Euclidean plane. This work proposes
a matheuristic, called Construct, Merge, Solve & Adapt (CMSA), to solve the PCCD. The hybrid approach combines constructive heuristics, mathematical programming, and adaptive mechanisms to improve the quality of solutions. Computational experiments with TSP Challenge instances compare the performance of the CMSA to the Enhanced DR heuristic. The results showed the robustness and effectiveness of the proposed matheuristic—achieving superior or equivalent solutions in more than 86% of cases.