Dynamic Vehicle Routing with Time Windows for Police Patrolling

Abstract

Das Patrouillieren mit Polizeifahrzeugen ist eine gängige Strategie zur Verbrechensprävention. Während einer Patrouille werden sogenannte „Points of Interest“ besucht, um Polizeipräsenz zu zeigen und potenzielle Kriminelle abzuschrecken. Das sind Orte, die besondere Aufmerksamkeit der Polizei bedürfen, wie zum Beispiel Parks, Geschäfte, Lokale und Drogen-Hotspots. Die Patrouillen müssen allerdings unterbrochen werden, wenn die Polizei an anderen Orten dringender eingesetzt werden muss. Der Einfluss von Unterbrechungen auf die patrouillierenden Fahrzeuge wird untersucht, um den Einsatz von Polizei-Ressourcen und die Durchführung von Patrouillen zu optimieren. Ziel dieser Arbeit ist die Behandlung dieses dynamischen Fahrzeugrouten-Problems mit Zeitfenstern. Hierfür werden Qualitätskriterien für eine Patrouille definiert, Monte-Carlo-Simulationen durchgeführt und die Qualitätskriterien abgeschätzt. Basierend auf realen Straßendaten von OpenStreetMap wird ein Netzwerkgraph erstellt. Knoten dieses Punktenetzes werden als „Points of Interest“ definiert und mit Zeitfenstern versehen, die im Rahmen einer Patrouille besucht werden sollen. Die Routenplanung erfolgt unter Verwendung von den metaheuristischen Algorithmen „Guided Local Search“ und „Simulated Annealing“. Es werden Patrouillen-Unterbrechungen angenommen, um Polizeieinsätze zu simulieren. Abschließend wird der Einfluss auf die Qualitätskriterien für Patrouillen statistisch ausgewertet.

Patrolling with police vehicles is a common strategy for crime prevention. During a patrol, so called points of interest are visited to show police presence and discourage potential criminals. Those are locations like parks, shops, bars and drug hotspots. However, patrols need to be interrupted eventually if police presence is needed more urgently elsewhere.The influence of interruptions on patrolling vehicles is determined to optimise the assignment of police resources and the execution of patrols. The aim of this thesis is to target this Dynamic Vehicle Routing Problem with time windows. For this purpose, quality criteria for a patrol are defined, Monte Carlo Simulations are performed and the quality criteria are evaluated. Based on real street data from OpenStreetMap, a network graph is created. Nodes of this network graph are defined as points of interest which should be visited in certain time windows during patrols. The routes are planned using the metaheuristic algorithms "Guided Local Search" and "Simulated Annealing". Patrol interruptions are introduced to simulate the unpredictable occurrence of police operations. Finally, the influence on quality criteria for patrols is evaluated statistically.