<div class="csl-bib-body">
<div class="csl-entry">Prischink, M. (2016). <i>Metaheuristics for the districting and routing problem for security control</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.35903</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2016.35903
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/5909
-
dc.description
Zusammenfassung in deutscher Sprache
-
dc.description.abstract
In this thesis the Districting and Routing Problem for Security Control (DRPSC) is introduced and modeled as a combinatorial optimization problem. Multiple (meta-)heuristics and exact methods based on mixed integer linear programming are considered to practically solve the problem. The results of these different approaches are then analyzed and compared. Finally, an outlook on future work for this new problem is given. The private security sector is a steadily growing business. Regular security controls on a day by day basis are an essential and important mechanism to prevent theft and vandalism in commercial buildings. Typically, security workers patrol through a set of objects where each object requires a particular number of visits on all or some days within a given planning horizon, and each of these visits has to be performed in a specific time window. An important goal of the security company is to partition all objects into a minimum number of disjoint clusters, called districts, such that for each cluster and each day of the planning horizon a feasible route for performing all the requested visits exists. Each route is limited by a maximum working time and has to satisfy the visits- time window constraints. Any two visits of an object must be separated by a minimum separation time. We call this problem the Districting and Routing Problem for Security Control. In our heuristic approach we split the problem into a districting part where objects have to be assigned to districts and a routing part where feasible routes for each combination of district and period have to be found. Although the problem can be decomposed, these parts cannot be solved independently. The districting part of the problem is solved by generating initial solutions using a districting construction heuristic and improving the initial solutions by applying an iterative destroy & recreate algorithm trying to minimize the number of districts. In the course of solving the districting problem, feasible solutions for many instances of the routing problem have to be found. Therefore, we present an efficient method for checking the feasibility of a given route. Initial solutions to the routing problem are generated with a routing construction heuristic in a greedy fashion resulting in good starting solutions for the following improvement heuristics. These solutions are then improved using a variable neighbourhood descent approach. Additionally, an exact mixed integer linear programming model for the routing part is proposed. Computational results show that the routing construction heuristics is able to generate solutions close to the lower bounds provided by the exact algorithm and the iterative destroy & recreate algorithm is able to reduce the number of districts significantly from the starting solutions, overall yielding very plausible solutions.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Metaheuristiken
de
dc.subject
kombinatorische Optimierung
de
dc.subject
Routenplanung
de
dc.subject
Security
de
dc.subject
Metaheuristics
en
dc.subject
Combinatorial Optimization
en
dc.subject
Routing
en
dc.subject
Security
en
dc.title
Metaheuristics for the districting and routing problem for security control
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2016.35903
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Michael Prischink
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Biesinger, Benjamin
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen