Metaheuristics for the districting and routing problem for security control

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.