Conflict-free vehicle routing

Collision-free vehicle routing occurs in many applications from robot movements via scheduling multiple cranes in steel logistics to the transport of containers by automated guided vehicles. In cooperation with the HHLA Container Terminal Altenwerder (CTA), we have developed a dynamic online routing algorithm that computes collision-free routes for AGVs by considering implicit time-expanded networks. This approach proved to be very efficient in scenarios with a high traffic density. This is in contrast to the more frequent static approaches that use routes computed in the static graph—i.e., without time expansion—and employ additional methods for collision avoidance during execution of the static routes. These static approaches have the advantage that they are quite robust against disturbances but are rather unpredictable because of the usually heuristic collision avoidance rules that may even run into deadlocks in high traffic scenarios. In this paper, we study if the static approach can be suitably enhanced to meet the performance of the dynamic approach and become predictable and collision and deadlock-free. Our approach is based on online static route computations combined with load balancing techniques and graph algorithms for guaranteed deadlock avoidance. We evaluate our static algorithm on routing scenarios from the HHLA CTA. It turns out that the performance of our static router is slightly superior in low and medium traffic scenarios, but loses against the dynamic router in high traffic scenarios.