Coverage area maximization with parallel simulated annealing

• Published in: Expert systems with applications 2022-09, Vol.202, p.117185, Article 117185
• Main Authors: Coll, Narcís, Fort, Marta, Saus, Moisès
• Format: Article
• Language: English
• Subjects: Cellular radio; Covered area; Disks; Facilities placement; Multiple services; Optimization; Optimization techniques; Parallel GPU processing; Perturbation; Polygons; Radio stations; Service coverage; Simulated annealing; Sirens
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2022.117185

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(k2) 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. •Sits k equal disk-like facilities maximizing their covering.•Probabilistically estimates the area covered by the disks.•Optimization strategy based on parallel simulated annealing.•Achieves nearly optimal locations in very reasonable running times.•Automatically setting the SA algorithm parameters.