Finding candidate routes with intermediate stops for railroad scheduling on block systems

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.

Da der Betrieb eines Eisenbahnnetzes einen hohen Grad an Koordination erfordert, stehen Wissenschaftler vor einer Ansammlung an schwierigen Planungsproblemen. Unter diesen Problemen sind auch das Zug-Routenproblem und das Zug-Zeitplanproblem, in denen Zuglinien jeweils eine Route / ein Zeitplan zugewiesen wird. Beide Probleme dienen dazu einen konfliktfreien Verkehrsplan zu erzeugen, eines separiert die Züge räumlich und das andere zeitlich. Es gibt bereits einige Lösungen für beide Probleme, diese scheitern allerdings daran, die Effizienz beizubehalten um Pläne für weitläufige Regionen wie ganze Länder zu erstellen. Eine unausgeschöpfte Möglichkeit neue Lösungsansätze zu entdecken, ist es dabei einen Blick in andere Domänen zu werfen, da beide Probleme viele Gemeinsamkeiten mit ähnlichen Planungsproblemen anderer Domänen haben. Eine dieser Ansätze ist der konfigurations-konfliktgraphbasierte Ansatz mit dem Falk et al. Routen und Zeitpläne für Datenpakete in einem Computernetzwerk planen. Da sie Routenfindung und Zeitplanung in ein einziges Problem verschmelzen, sind sie allerdings abhängig davon, eine sinnvolle Menge an Kandidatenpfaden zu besitzen um den exponentiellen Anstieg an Konfigurationen zu widerstehen. Ihre Verwendung eines k-kürzeste Pfade Algorithmus', um diese Kandidatenpfade zu wählen, lässt sich allerdings nicht gut in Eisenbahndomäne übernehmen, da in hochdetaillierten Eisenbahnnetzen die k-kürzesten Pfade größtenteils identisch sind und ihrem Algorithm so wenig Möglichkeiten geboten werden, einen Konflikt zu vermeiden. Unser Beitrag in dieser Arbeit liegt darin, Algorithmen die von einer kleinen Eingabemenge profitieren, mit einer sinnvolle Menge an Kandidatenpfaden zu versorgen und es ihnen so zu ermöglichen, effizient ausgeführt zu werden. Wir präsentieren zwei graphbasierte Routenfindungsalgorithmen, die unter Eingabe einer geordneten Liste an Stationen (die Zuglinie), eine Menge an alternativen Wegen produzieren, die diese besuchen. Einer der präsentierten Algorithmen, den wir simple routing algorithm benennen, implementiert Dijkstra auf eine Weise die kompatibel mit der Topologie eines Eisenbahnnetzes ist. Zusätzlich implementiert er eine Umgebung die es erlaubt, für andere Ziele als Routenlänge zu optimieren, hauptsächlich die Einzigartigkeit der verschiedenen Alternativen. Alternativ präsentieren wir den multi-dimensional routing algorithm, der den simple routing algorithm erweitert, um noch differenziertere Alternativen zu finden, auf Kosten schlechterer Laufzeitskalierung. Unsere Evaluationen zeigen große Verbesserungen im Vergleich zu Yen's Algorithmus, bezüglich der Distanz die sich die Alternativen teilen. Die Laufzeitevaluationen zeigen größtenteils eine verbesserte Performanz des simple routing algorithm im Vergleich zu Yen. Sie zeigen auch, dass die mitgegebenen Parameter gut überlegt sein müssen, da eine Balance zwischen den verschieden Optimierungszielen erzielt werden muss.