C. Kloimüllner, G. Raidl:

"Efficient Consideration of Soft Time Windows in a Large Neighborhood Search for the Districting and Routing Problem for Security Control";

Talk: Evolutionary Computation in Combinatorial Optimization (EvoCOP), Amsterdam; 2017-04-19 - 2017-04-21; in: "Evolutionary Computation in Combinatorial Optimization", Evolutionary Computation in Combinatorial Optimization, (2017), ISBN: 978-3-319-55452-5; 91 - 107.

For many companies it is important to protect their physical

and intellectual property in an e cient and economically viable man-

ner. Thus, specialized security companies are delegated to guard private

and public property. These companies have to control a typically large

number of buildings, which is usually done by teams of security guards

patrolling di erent sets of buildings. Each building has to be visited sev-

eral times within given time windows and tours to patrol these buildings

are planned over a certain number of periods (days). This problem is

regarded as the

Districting and Routing Problem for Security Control

.

Investigations have shown that small time window violations do not re-

ally matter much in practice but can drastically improve solution quality.

When softening time windows of the original problem, a new subprob-

lem arises where the minimum time window penalty for a given set of

districts has to be found for each considered candidate route: What are

optimal times for the individual visits of objects that minimize the overall

penalty for time window violations? We call this

Optimal Arrival Time

Problem

. In this paper, we investigate this subproblem in particular and

rst give an exact solution approach based on

linear programming

. As this

method is quite time-consuming we further propose a heuristic approach

based on greedy methods in combination with dynamic programming.

The whole mechanism is embedded in a large neighborhood search (LNS)

to seek for solutions having minimum time window violations. Results

show that using the proposed heuristic method for determining almost

optimal starting times is much faster, allowing substantially more LNS

iterations yielding in the end better overall solutions.

Created from the Publication Database of the Vienna University of Technology.