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. The second part is about routing in the Personal Rapid Transit (PRT) application. PRT is a public transportation mode in which small automated vehicles transport passengers on demand. Central control of the vehicles leads to interesting possibilities for optimized routings. Routing in PRT is an online problem where transit requests appear over time and where routing decisions need to be taken without knowledge of future requests. Further, the network in PRT is directed. The complexity of the routing problems together with the fact that routing algorithms for PRT essentially have to run in real-time often leads to the choice of a fast sequential scheme. The simplicity of such schemes stems from the property that a chosen route is never changed later. This is as well the main drawback of it, potentially leading to large detours. It is natural to ask how much one could gain by using a more adaptive routing strategy. This question is one of the core motivations of this second part. We first suggest a variation to the routing model used in the first part which is suitable for PRT. We show that the routing problem remains hard in the directed setting. Further, we introduce a capacity notion for PRT networks and derive a bound for it. Computational results show that the capacity bound is close to the achievable throughput. It therefore is a useful quantity for estimating network capacity in PRT system design. We then introduce a new adaptive routing algorithm that repeatedly uses solutions to an LP as a guide to route vehicles. New requests are integrated into the LP as soon as they appear and the routing is reoptimized over all vehicles concurrently. We provide computational results that give evidence of the potential gains of an adaptive routing strategy. For this we compare the presented adaptive strategy to sequential routing and to a simple distributed routing strategy in a number of scenarios. Diese Dissertationsarbeit untersucht das konfliktfreie Befördern von Fahrzeugen durch Schienennetzwerke - eine Herausforderung, wie sie oft in verschiedensten Anwendungen in den Transport- und Logistikbranchen vorkommt. Der bekannteste Ansatz für die konfliktfreie Fahrplanung ist ein sequentieller, in dem eine Anfrage nach der anderen mit einer möglichst kurzen Reisezeit eingeplant wird, ohne mit den früheren Anfragen in Konflikt zu geraten. Solche Ansätze haben oft keine Qualitätsgarantien für den resultierenden Fahrplan, und es besteht ein Bedarf für ein besseres theoretisches Verständnis. Das Problem der konfliktfreien Fahrzeugbeförderung ist auch von Interesse durch die enge Verwandtschaft mit dem besser bekannten und untersuchten Problem der Datenbeförderung durch Kommunikationskanäle. Im ersten Teil der Dissertation präsentieren wir neue theoretische Resultate für den Fall von ungerichteten (in beiden Richtungen befahrbaren) Schienennetzwerken. Wir betrachten ein natürliches Modell für die konfliktfreie Beförderung eines Sets von k Fahrzeugen. Zuvor war kein effizienter Algorithmus mit einer sublinearen (in k) Approximationsgarantie für allgemeine Netzwerktopologien bekannt. Wir zeigen, dass es NP-schwer ist, eine optimale Lösung zu finden, sogar wenn das Netzwerk nur aus einem Pfad besteht. Wir präsentieren einen Algorithmus für Baum-Netzwerke, der auf dem sequentiellen Ansatz aufbaut und zu einem Fahrplan führt, der alle Fahrzeuge in Zeit O(OPT) + k ans Ziel befördert. Indem wir dieses Resultat mit Methoden aus dem Bereich der Datenbeförderung kombinieren, erhalten wir den ersten effizienten Algorithmus mit sublinearer Approximationsgarantie von O(?k). Zusätzlich präsentieren wir einen randomisierten Algorithmus der zu Lösungen der Länge O(polylog(k)) * OPT + k führt. Der Ansatz generiert Baumgraphen, die in eine komprimierte Version des Netzwerks eingebettet werden, womit eine Approximationsgarantie erreicht werden kann die unabhängig von der Graphgrösse ist. Der zweite Teil der Dissertation handelt von der Beförderungen von Fahrzeugen in Personal Rapid Transit (PRT). PRT ist ein öffentliches Verkehrsmittel in welchem Passagiere auf Verlangen durch kleine automatisierte Fahrzeuge befördert werden. Zentrale Steuerung der Fahrzeuge führt zu interessanten Möglichkeiten für die optimierte Nutzung der Schienenressourcen. Die Fahrplanerstellung für PRT ist ein Online-Problem in dem die Transportaufträge über die Zeit eintreffen. Entscheidungen müssen ebenfalls über die Zeit getroffen werden, ohne Kenntnis der zukünftigen Aufträge. Ein weiterer Unterschied zum ersten Teil der Dissertation ist, dass die Schienen in PRT nur in eine Richtung befahren werden. Die Komplexität des PRT Beförderungs- Problems und die Anforderung, dass die Fahrpläne in Echtzeit berechnet werden müssen, führt oft zur Wahl von schnellen sequentiellen Algorithmen. Die Einfachheit dieser Ansätze ist bedingt durch die Eigenschaft, dass ein geplanter Fahrplan nicht mehr geändert wird sobald er einmal berechnet wurde. Diese Eigenschaft ist gleichzeitig der grösste Nachteil eines solchen Ansatzes, da sie zu grossen Umwegen oder Verzögerungen führen kann. Eine natürliche Frage ist, wie viel man gewinnen kann wenn man adaptive Strategien verwendet. Diese Frage steht im Zentrum dieses zweiten Dissertationsteils. Zuerst stellen wir eine auf PRT zugeschnittene Variation des mathematischen Modells aus dem ersten Dissertationsteils vor. Wir zeigen, dass das Beförderungs-Problem auch in dieser Variante NP-schwer bleibt. Weiter führen wir einen Kapazitätsbegriff für PRT Netzwerke ein und beweisen eine obere Schranke für diese. Mit Hilfe von Simulationen können wir zeigen, dass die Kapazitätsschranke nicht weit vom erreichbaren Netzwerk-Durchsatz entfernt ist. Sie kann deshalb eine nützliche Grösse zur Abschätzung der Netzwerkkapazität in der Designphase von neuen PRT Systemen sein. Dann präsentieren wir einen neuen adaptiven Algorithmus, der den Fahrplan auf der Grundlage von LP Lösungen erstellt. Neue Aufträge werden gleich beim Eintreffen in das LP integriert und der Fahrplan wird neu berechnet, für alle Fahrzeuge gleichzeitig. Wir zeigen mit Hilfe von Simulationsresultaten das Potential solch adaptiver Strategien. Wir vergleichen den neuen adaptiven Ansatz mit dem sequentiellen Ansatz und mit einem einfachen dezentralisierten Algorithmus in einer Anzahl von Szenarien.