[Back]

M. Prischink:
"Metaheuristics for the Districting and Routing Problem for Security Control";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2016; final examination: 2016-05-09.

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. Altough the problem can
be decombosed, 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 toreduce the number of districts significantly from the starting solutions, overall yielding
very plausible solutions.

In dieser Arbeit wird das Districting and Routing Problem for Security Control eingeführt
und als kombinatorisches Optimierungsproblem modelliert. Mehrere (Meta-)Heuristiken
und exakte Methoden basierend auf gemischt-ganzzahliger linearer Programmierung
werden zur Lösung des Problems verwendet. Die Ergebnisse der verschiedenen Ansätze
werden anschließend analysiert und verglichen. Zum Abschluss wird ein Ausblick auf
weitere Forschungsmöglichkeiten zu diesem neuen Problem gegeben.
Der private Sicherheitssektor ist ein stetig wachsendes Geschäft. Regelmäßige tägliche
Sicherheitskontrollen sind ein essentieller und wichtiger Mechanismus um Diebstahl und
Vandalismus in Firmengebäuden vorzubeugen. Typischerweise patrouillieren Mitarbeiter
eines Sicherheitsdienstes durch eine Menge von Gebäuden, wobei jedes dieser Gebäude
eine bestimmte Anzahl von Besuchen an allen oder nur an ausgewählten Tagen eines
gegebenen Planungshorizonts benötigt und jeder Besuch in einem bestimmten Zeitfenster
stattfinden muss. Ein wichtiges Ziel der Sicherheitsfirma ist daher, alle Gebäude in eine
minimale Anzahl disjunkter Distrikte, d.h. Cluster, zu unterteilen, sodass für jeden
Cluster und jeden Tag des Plannungszeitraums eine zulässige Route existiert, durch die
alle notwendigen Objektbesuche abgedeckt werden. Jede Route ist begrenzt durch die
tägliche Maximalarbeitszeit eines Mitarbeiters und muss die Zeitfenster aller Besuche
einhalten. Je zwei Besuche des selben Gebäudes müssen einen vorgegebenen zeitlichen
Mindestabstand einhalten. Wir nennen dieses Problem das Districting and Routing
Problem for Security Control. In unserem heuristischen Ansatz teilen wir das Problem
in einen Districting-Teil in dem jedes Gebäude einem Distrikt zugeteilt werden muss
und einen Routing-Teil in dem zulässige Routen für jede Kombination von Distrikt und
Planungsperiode gefunden werden müssen. Das Problem kann zwar in zwei Subprobleme
zerlegt werden, diese können jedoch nicht unabhängig voneinander gelöst werden.
Der Districting-Teil des Problems wird gelöst, indem initiale Lösungen mittels einer Districting
Construction Heuristic erzeugt werden und diese Lösungen durch einen Iterative
Destroy & Recreate Algorithmus verbessert werden, indem versucht wird, die Anzahl der
benötigten Distrikte zu minimieren. Um das Districting-Problem zu lösen, müssen viele
Instanzen des Routing-Problems gelöst werden. Deshalb präsentieren wir ein Verfahren,
mit dessen Hilfe die Gültigkeit einer gegebenen Route effizient überprüft werden kann.
Initiale Lösungen für das Routing-Problem werden mittels einer adaptierten Greedy
Construction Heuristic generiert, um gute Startlösungen für die darauffolgenden Verbesserungsheuristiken zu erzeugen. Diese Lösungen werden anschließend mittels eines Variable
Neighborhood Descent Ansatzes verbessert. Zusätzlich wird ein gemischt-ganzzahliges
lineares Programm für den Routing-Teil vorgestellt. Die Ergebnisse unserer Tests zeigen,
dass die Konstruktionsheuristiken Lösungen für das Routing-Problem erzeugen, die nahe
an den unteren Schranken des exakten Algorithmus liegen und der Iterative Destroy &
Recreate Algorithmus die Anzahl der Distrikte der Startlösungen, die von der Districting
Construction Heuristic erzeugt wurden, signifikant reduzieren kann.

http://publik.tuwien.ac.at/files/publik_254587.pdf