Conflict-free Vehicle Routing: Load Balancing and Deadlock Prevention
Please always quote using this URN:urn:nbn:de:0296-matheon-5013
- We study a so-called static approach for the problem of routing vehicles conflict-free through a given street network. In fact, we assume that routes are computed without taking time-dependences into account and collisions are avoided via a particular reservation procedure. In this context, the task is to cope with two arising problems: the appearance of congestion and detours on the one hand and the risk of deadlocks on the other. We provide a two-stage routing approach for that problem. In the first phase we focus on balancing the load on the edges of the given graph that models the underlying street network. Therefore, we consider the Online Load Balancing Problem with Bounded Stretch Factor and give an optimal algorithm with respect to a specific performance ratio, the stretch factor restricted competitive ratio. Furthermore, in a second phase, we investigate the detection and avoidance of deadlock situations. For the evaluation of the entire algorithm we consider the routing of Automated Guided Vehicles (AGVs) at HHLA Container Terminal Altenwerder (CTA).
Author: | Max Klimm, Ewgenij Gawrilow, Rolf H. Möhring, Björn Stenzel |
---|---|
URN: | urn:nbn:de:0296-matheon-5013 |
Referee: | Rolf H. Möhring |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2008/03/26 |
Release Date: | 2008/03/26 |
Institute: | Technische Universität Berlin |
Preprint Number: | 497 |