Conflict-free Vehicle Routing with an Application to Personal Rapid Transit

This thesis investigates the conflict-free routing of vehicles through a track network, a problem frequently encountered in many applications in transportation and logistics. The most common routing approach for conflictfree routing problems in various settings is a sequential one, where requests are greedily served one after the other in a quickest way without interfering with previously routed vehicles. There is a need for a better theoretical understanding as guarantees on the quality of the routings are often missing. Conflict-free vehicle routing also is of inherent interest as a sister problem of the well-studied packet routing problem. In the first part, we present new theoretical results for the case of bidirectional networks. We consider a natural basic model for conflict-free routing of a set of k vehicles. Previously, no efficient algorithm is known with a sublinear (in k) approximation guarantee and without restrictions on the graph topology. We show that the conflict-free vehicle routing problem is hard to solve to optimality even on paths. Building on a sequential routing scheme, we present an algorithm for trees with makespan bounded by O(OPT) + k. Combining this result with ideas known from packet routing, we obtain a first efficient algorithm with sublinear approximation guarantee, namely an O(¿k)-approximation. Additionally, a randomized algorithm leading to a makespan of O(polylog(k)) ¿ OPT + k is presented that relies on tree embedding techniques applied to a compacted version of the graph to obtain an approximation guarantee independent of the graph size.