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  
email: moehring[at]math.tuberlin.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  
email: stenzel[at]math.tuberlin.de gawrilow[at]math.tuberlin.de eguenth[at]math.tuberlin.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 realtime. 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.
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.
Model.
We model the AGV network as a directed graph. The idea is to compute conflictfree routes in that graph. To this end, we take the dimensions of the AGVs and their timedependent 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 timedependencies on the other hand.
Dynamic Routing.
The timedependent behaviour of the AGVs is modelled by timewindows on arcs. Each timewindow denotes that the corresponding arc is not occupied during this timeinterval. So for each new request we have to compute a (dynamic) path that enters and leaves each arc during the same timewindow (on that arc). The following figure illustrates the procedure for each request (red: blockings, green: timewindows).



The determination of a (shortest) path respecting timewindows was introduced by Desrosiers, Soumis and Desrochers [1]. Considering a cost function c and timewindows on the arcs the problem is to find a shortest path with respect to c through these timewindows. This is known as a NPhard 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).
References.
[1]  J. Desrosiers, F. Soumis, M. Desrochers. Routing with timewindows by column generation. Networks 14, 545565, 1984. 
[2]  M. Desrochers, F. Soumis. A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR 26, 191212, 1988. 