Districting and Routing for Security Control

摘要

Regular security controls on a day by day basis are an essential and important mechanism to prevent theft and vandalism in business 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 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, must satisfy the visits' time window constraints, and any two visits of one object must be separated by a minimum time difference. 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. These parts cannot be solved independently though. We propose an exact mixed integer linear programming model and a routing construction heuristic in a greedy like fashion with variable neighborhood descent for the routing part as well as a districting construction heuristic and an iterative destroy & recreate algorithm for the districting part. Computational results show that the exact algorithm is only able to solve small routing instances and the iterative destroy & recreate algorithm is able to reduce the number of districts significantly from the starting solutions.