TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2004

COGA 5-Wheel

Page Content

to Navigation

Preprints 2004

Conflict-free Real-time AGV Routing
Citation key Report-026-2004
Author Rolf H. M\öhring and Ekkehard K\öhler and Ewgenij Gawrilow and Bj\örn Stenzel
Year 2004
Number 026
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe