A new heuristic for the continuous fixed-radius disc cover problem

The continuous fixed-radius disc cover (CFDC) problem is a location model to cover the given demand points by finding the minimum number of fixed-radius discs in the plane. It is an NP-hard problem, and only a few approximate algorithms have been proposed over the past three decades. In the article, a new heuristic called dynamic reduction (DR) is introduced. The heuristic works by initiating an upper bound on the number of discs, and then reducing the number by removing redundant discs during updates to the disc centres. Experimental results, using different radius settings on some datasets of a travelling salesman problem library (TSP-Lib), show that the proposed heuristic greatly outperforms the recent approximation algorithm in accuracy. Notably, an enhancement of the heuristic is also provided.