In automated logistic systems Automated Guided Vehicles (AGVs)
are used for transportation tasks. To deal with
the interaction in such an AGV system one needs efficient
and intelligent routing on the one hand and collision
avoidance on the other. Obviously, AGV routing
is an online routing problem (nothing is known about
future requests) and even a real-time problem, because fast
answers are required.
A route should be computed in less than a second.
We present an algorithm which avoids
collisions, deadlocks, livelocks and other conflicts
already at the time of route computation (conflict-free routes).
To this end, we create a mapping between each arc and the arcs
that cannot be used at the same time in the underlying
directed graph
that represents the lanes of the AGV system. This
is realized in a preprocessing step. The
time-dependent behavior of the AGVs is modelled by time-windows
(implicit time-expansion). Thus, the real-time computation for each
request consists of the determination of a shortest path with
time-windows (routing) and a following readjustment of
these time-windows (blocking).
The Shortest Path Problem with Time-Windows is NP-hard,
but in the relevant case where costs correlate with
transit times our algorithm solves the problem in
polynomial time using a
generalized Dijkstra algorithm. For additional
acceleration we use goal-oriented search.
On instances with more than 30.000 arcs and up to
50 AGVs routing and blocking together take less than half
a second (maximal) and some hundreth of a second
on the average, respectively, which is appropriate for
real-time AGV routing. Additionally, in comparison with a static
(not time-dependent)
routing approach which is used in praxis
our algorithm performs much better.
