In this thesis, we considered two important problems from the field of railway optimization. First, we investigated delay management in passenger transport for the case of one train line as an online optimization problem. We provided competitive analysis for the objective of minimizing the total passenger delay in a setting where passengers enter the train line either with no delay or with a source delay of 8. Furthermore, we extended this basic model to two possible source delays, to consecutive trains serving the same train line with a frequency of T, and to connecting trains such that each segment of the train line is served by a different train. We also considered the situation that large delays lead to a refund for the passengers and looked into the problem of maximizing the profit. Our second main theme was the efficient distribution of empty freight cars. We presented the practical requirements of our project partner DB Schenker Rail Deutschland AG, including prioritization of demands and 2-to-l-substitutions, and explained how we modeled and solved the problem using a network optimization approach. Moreover, we developed efficient reoptimization methods for the problem. Lastly, we focused on a more theoretical aspect which arose in the modeling of the empty freight car distribution: the computation of generalized max flows. We studied this problem for the class of series-parallel graphs and provided efficient algorithms for both the case of continuous and integral flow. There still remain many open problems in the considered topics. For online delay management, we considered rather simple models. One step towards more realistic results could be the combination of different extensions to the basic setup into one model. Another approach might be to follow the idea of studying online delay management with an adversary that is restricted and hence more realistic. For the empty freight car distribution problem, it might be interesting to investigate more general k-to-l-substitutions. With this extension, the continuous solution to our model will not be half-integral anymore, which requires a different heuristic approach to obtain integral solutions.
Efficient algorithms for online delay management and railway optimization
Mathematik ; 1-132
2012
132 Seiten, Bilder, Tabellen, 38 Quellen
Theses
English
A Review of Online Dynamic Models and Algorithms for Railway Traffic Management
Online Contents | 2015
|Online disruption and delay management
TIBKAT | 2013
|