The Angular Set Covering Problem

We present an innovative extension of the Set Covering Problem, transitioning from a traditional radial covering to an angular covering structure. The decisions are based on locating the facilities and identifying the directional servers installed in each, covering a set of points in a geographic area. The strategic placement of surveillance cameras inspired this novel approach. We aim to minimize the cost of covering demand points by strategically installing directional servers on facilities. We propose an integer linear model and an initial approach based on column generation decomposition. We conducted extensive computational experiments on different test instances, including a practical case study involving positioning security cameras for surveillance in Valparaíso, Chile. The results highlight the effectiveness of column generation in achieving optimal solutions or significantly improving solution quality compared with solving the model directly with standard optimization solvers, especially for larger instances. In particular, the column generation algorithm achieves up to a 67% improvement in solution quality compared to the optimization model for real-world size instances, demonstrating its practical applicability and potential for enhancing surveillance infrastructure design.