| Popis: |
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 |
