[Back]


Talks and Poster Presentations (with Proceedings-Entry):

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.



English abstract:
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.