Coverage area maximization with parallel simulated annealing

This study provides a system that determines where to locate k disks-like services of radius r so that they globally cover as much as possible a region of demand. It is an NP-hard problem with notorious applications in the facility location field when locating multiple warning sirens, cellular towers, radio stations, or pollution sensors covering as much area as possible of a city or geographical region. The region of demand is assumed to be delimited by a general polygonal domain, and the resolution strategy relies on a parallel simulated annealing optimization technique based on a suitable perturbation strategy and a probabilistic estimation of the area of the polygonal region covered by the k disks in O(k(2)) time. The system provides a good enough location for the disks starting from an arbitrary initial solution with very reasonable running times. The proposal is experimentally tested by visualizing the solutions, analyzing and contrasting their quality, and studying the computational efficiency of the entire strategy.

Automated summary

This study presents a system for determining the optimal locations for k disk-like services to maximize the coverage of a demand region. The study focuses on the facility location field and addresses the challenge of locating multiple services efficiently. The proposed system utilizes a parallel simulated annealing optimization technique to provide good enough solutions within reasonable running times.