Conflict-free Real-time AGV Routing

Rolf H. Möhring, Ekkehard Köhler, Ewgenij Gawrilow, and Björn Stenzel

agv routing, conflict-free routing, shortest path with time-windows

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.

Download as [PDF] [ps.gz] [ps]