Bachelor Thesis BCLR-2021-73

BibliographyRichter, Marcel: Finding candidate routes with intermediate stops for railroad scheduling on block systems.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 73 (2021).
52 pages, english.
Abstract

The high coordination effort involved in running a railroad network faces researchers with a collection of difficult planning problems. Among these problems are the routing problem and the scheduling problem in which train lines are mapped to one route / schedule respectively. Both problems serve to establish a conflict-free traffic plan, one by separating trains in space and the other in time. There are plenty of existing solutions for both problems already, however, they fail to maintain the efficiency to carry out planning for an extensive region like an entire country. An untapped opportunity for discovering new solution approaches is looking into other domains, as both problems share a lot of traits with similar planning problems of other domains. One such approach is the configuration-conflict graph based approach which Falk et al. [FGD+21] route and schedule computer network packets with. Because they combine routing and scheduling problem to be dealt with as a single problem, they rely on a sensible set of candidate configurations to withstand the exponential increase in configurations. Their adoption of a k-shortest path algorithm for picking candidate routes does not translate adequately into the railroad domain, because in highly detailed railroad networks the k-shortest paths are mostly identical, thus leaving their algorithm little opportunities to avoid conflicts. Our contribution in this thesis lies in providing algorithms like [FGD+21] which benefit from a small input set, with a sensible set of candidate routes, facilitating them to run efficiently. We propose two graph-based routing algorithms that find a set of alternative paths visiting a given list of stations (the train line) in order. One of our proposed algorithms, labeled the simple routing algorithm, implements Dijkstra in a fashion that is compatible with a railroad topology. In addition, it implements a framework to optimize for other goals than path shortness, mainly uniqueness of the various alternative paths in a result set. Alternatively, we propose the multi-dimensional routing algorithm which expands on the simple algorithm to find even more unique alternatives, at the cost of worse runtime scaling. Our evaluations show vast improvements in terms of the shared distance between the different paths of a result set compared to Yen’s k-shortest path algorithm. The runtime evaluations show enhanced performance of the simple routing algorithm compared to Yen in the majority of scenarios. They also demonstrate that great thought needs to be given to the algorithm parameters, since all optimization goals need to be balanced against each other.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Superviser(s)Rothermel, Prof. Kurt; Geppert, Heiko
Entry dateFebruary 15, 2022
   Publ. Computer Science