Service coverage optimization for facility location: considering line-of-sight coverage in continuous demand space
Xiaoya Ma, Xiaoyu Zhang, Xiang Zhao
Abstract
The reliable service coverage of many facilities or sensors used in smart city infrastructure is highly susceptible to obstructions in urban environments. Optimizing the line-of-sight (LOS) service coverage is essential to locating these facilities for smarter city services. Despite progression in the maximal coverage location problem (MCLP) model for locating facilities, maximizing the LOS service coverage in continuous demand space for facility location problems remains challenging. This study defined the LOS-constrained MCLPs (LOS-MCLPs) and proposed a service coverage optimization model to solve these LOS-MCLPs. We employed a computational geometry algorithm named the visibility polygon (VP) algorithm to simulate the LOS coverage in two-dimensional (2D) continuous demand space. We then coupled this algorithm with a robust heuristic algorithm to search for the optimal solutions to maximize effective LOS service coverage. An experiment applied the developed model to a Wi-Fi hotspot planning problem. The experimental results demonstrated that the proposed model can obtain optimal solutions for LOS-MCLPs according to the distribution of obstacles. Comparative results show that ignoring the LOS effect in the optimization of LOS-MCLPs might lead to large areas of service dead zones.