The Angular Set Covering Problem

doi:10.1109/ACCESS.2024.3416871

2024-01-01

Fredy Barriga-Gallegos *

Armin Lüer‐Villagra

Gabriel Gutiérrez-Jarpa

DOI：10.1109/ACCESS.2024.3416871

原文链接

原文求助

摘要

En 中文

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 & iacute;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.

Keyword:

Servers

Costs

Cameras

Optimization methods

Computational modeling

Security

Linear programming

Combinatorial mathematics

Angular covering

column generation

combinatorial optimization