Back to search

Lancaster University

Exploring various set covering problem techniques to tackle the optimal camera placement problem

Abstract

dc:description.abstract

Optimal Camera Placement (OCP) problem is a combinatorial optimization problem, where the aim is to find an optimal placement of cameras, given that a target area is completely covered. A single-objective OCP is commonly formulated in two possible ways. The first one is to maximize the area coverage, such that minimal camera cost is maintained. The second one is to minimize camera cost, such that complete area coverage is achieved. The idea of the second formulation of OCP can be similar to a popular NP-hard combinatorial optimization problem, namely, the Set Covering Problem (SCP). Thus, OCP can be formulated as SCP. However, a special variant of SCP is used in this paper. This variant is called the unicost SCP (USCP), where the cost is assumed to be unified and, therefore, not a factor. The reason behind using USCP is that our problem instances do not consider cost as a factor, which makes USCP well-suited for this study. Thus, the objective of our OCP problem is to minimize the number of cameras rather than the cost. Despite the connection between OCP and SCP, not many studies have used techniques from the former's literature and applied them to address the latter. This study exploits this connection by implementing various SCP techniques to address 69 OCP instances retrieved from the GECCO 2021 competition on "the optimal camera placement problem and the unicost set covering problem'". First, our OCP problems are solved using classic exact methods. The initial results seem to be promising, but can be improved. Next, SCP problem reduction techniques are introduced and implemented to address the complexity of our problem. A comparison between the results before and after reduction is given. After that, the OCP is formulated as a bi-objective problem, where the two objectives are to, simultaneously, minimize the number of cameras and maximize the area coverage. An effective multi-objective technique is used to obtain the efficient solutions of this problem.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
Lancaster University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Almousa, Malek
  • Ehrgott, Matthias
  • Kheiri, Ahmed

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
Lancaster University
Base URL
eprints.lancs.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Almousa, Malek; Ehrgott, Matthias; Kheiri, Ahmed. Exploring various set covering problem techniques to tackle the optimal camera placement problem. doctoral thesis, Lancaster University, 2025.