Online AGV Routing

Project director: Prof. Dr. Rolf H. Möhring
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 24594
e-mail: moehring[at]math.tu-berlin.de
Researcher: Björn Stenzel, Ewgenij Gawrilow, Elisabeth Günther
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
Tel: +49 (0)30 - 314 23598
e-mail: stenzel[at]math.tu-berlin.de gawrilow[at]math.tu-berlin.de eguenth[at]math.tu-berlin.de
Support: Bundesministerium für Bildung und Forschung (BMBF)
(Optimierungsverfahren zur dynamischen Routenführung in Verkehrs- und Transportnetzen)
Cooperation partner: Hamburger Hafen- und Lagerhaus AG (HHLA)

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. That means 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.

AGV
An AGV 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.

CTA
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
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 since we have a special cost function (the transit times). In that setting the problem can be solved in polynomial time. The challenge is to solve the problem in appropriate time (less than a second per request).

snapshot
Some traveling AGVs in our simulation environment

References.

[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 permanent labelling algorithm for the shortest path problem with time windows. INFOR 26, 191--212, 1988. 

gefoerdert vom BMBF