A Novel and Efficient Formulation and Solution Approach for the Region Coverage Problem with Identical Circles

The problem of covering a two-dimensional region with identical circles of minimal radius (CRICMR) is a classic optimization problem with many relevant real-world applications. However, due to the nonconvexity and the multiply-connected nature of the region to be covered, designing an efficient formulation and solution approach for the problem is very challenging. In this study, we first propose a unified optimization model for two classic variants of the problem (i.e., the CRICMR problems with and without center placement constraints), and then present an effective heuristic algorithm for solving both variants. The proposed model is based on the clipped Voronoi diagram and converts the intractable region coverage problem into the much easier vertex covering problem with respect to the clipped Voronoi polygons. The proposed algorithm incorporates several key components: a two-phase monotonic basin-hopping method; a subregion-based local optimization method; two perturbation operators, and a radius adjustment method for the covering circles. Computational experiments on popular benchmark instances demonstrate the efficiency of our approach, which significantly outperforms state-of-the-art methods by improving the current best-known solutions for nearly all benchmark instances.

History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms.

Funding: This research was partially supported by the National Natural Science Foundation of China [Grants 72571149, 72588101, and 72471100].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1649) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1649). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.