[Back]

M. Prischink, C. Kloimüllner, B. Biesinger, G. Raidl:
"Districting and Routing for Security Control";
Talk: International Workshop on Hybrid Metaheuristics (HM), Plymouth, United Kingdom; 2016-06-08 - 2016-06-10; in: "Hybrid Metaheuristics - 10th International Workshop on Hybrid Metaheuristics", LNCS, 9668 (2016), ISBN: 978-3-319-39636-1; 87 - 103.

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.

http://dx.doi.org/10.1007/978-3-319-39636-1_7

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