contents
|
|
AGV Routing
Online AGV Routing
Problem description.
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. Additionally, the route computation
has to be done in real-time. So we have to answer the requests
online and in appropriate time. Each request consists of the source, the target
and the starting time of a transportation task.
An AGV as it is used at Container Terminal Altenwerder (CTA)
Application.
The Container Terminal Altenwerder (CTA)
at Hamburg Harbour
is the most modern Container Terminal worldwide. The high level
of automation requires modern techniques to coordinate the
automated processes. Routing of Automated Guided Vehicles is a very
important part of the automation.
The Container Terminal Altenwerder at Hamburg Harbour
Model.
We model the AGV network as a directed graph. The idea is to
compute conflict-free routes in that graph. To this end, we take the
dimensions of the AGVs and their time-dependent
behaviour into account. To detect collisions we need a
mapping between each arc and the arcs that cannot
be used at the same time
on the one hand and a dynamic approach to model time-dependencies
on the other hand.
Dynamic Routing.
The time-dependent behaviour of the AGVs is modelled by
time-windows on arcs. Each time-window denotes that the
corresponding arc is not occupied during this time-interval.
So for each new request we have to compute a (dynamic) path that enters
and leaves each arc during the same time-window (on that arc).
The following figure illustrates the procedure for each request (red: blockings,
green: time-windows).
 ---->
|
 ---->
|
|
|
graph with blockings
|
new path
|
graph with new blockings
|
The determination of a (shortest) path respecting time-windows
was introduced by Desrosiers, Soumis and Desrochers [1].
Considering a cost function c and time-windows on the arcs the problem is to
find a shortest path with respect to c through these time-windows. This is
known as a NP-hard problem.
Our setting is special in two senses. We have a special cost function
(the transit times) and we have also to wait in time-windows (not just
travelling through time-windows).
The challenge is to solve the problem in that special setting
in appropriate time (less than a second).
Literatur.
| [1] |
J. Desrosiers, F. Soumis, M. Desrochers.
Routing with time-windows by column generation.
Networks 14, 545--565, 1984. |
| [2] |
M. Desrochers, F. Soumis.
A generalized permnanent labelling algorithm for the shortest path problem
with time windows. INFOR 26, 191--212, 1988. |
Some cruising AGVs
|
top