Railway Shunting via Kronecker Algebra

Abstract

Das Rangieren von Zügen ist eine grundlegende und zugleich rechnerisch anspruchsvolle Aufgabe des Bahnbetriebs. Diese Arbeit untersucht, inwiefern sich Kronecker-Algebra als Modellierungsgrundlage für Rangierprobleme eignet, und ob sich der daraus entstehende Zustandsraum effizient durchsuchen lässt, um Rangierlösungen zu finden. Wir formalisieren Gleise, Wagen und zulässige Bewegungen mithilfe matrixbasierter Operationen (Kronecker-Produkte und -Summen) und erhalten so ein Zustandsraummodell. Wir erweitern die Problemstellung auf mehrere Lokomotiven. Insbesondere betrachten wir eineVariante mit zwei Lokomotiven, die jeweils an den beiden Enden des Gleisfelds positioniert sind, eine Anordnung, die nach unserem Kenntnisstand bislang nicht untersucht wurde. Zur Lösungssuche setzen wir eine A-star-Suche mit mehreren, unterschiedlichen Heuristiken ein. Eine experimentelle Auswertung auf zufällig generierten Instanzen, inspiriert durch das Inglenook Shunting Puzzle, und mehrgleisigen Layouts zeigt, dass die Wahl der Heuristik maßgeblich die Suchleistung bestimmt. Die wesentliche Einschränkung unseres Ansatzes liegt in der Skalierbarkeit. Der Zustandsraum wächst mit der Anzahl der Gleise und Wagen exponentiell, wodurch große Konfigurationen schwer durchsuchbar werden. Abschließend skizzieren wir Ansatzpunkte für zukünftige Arbeiten, darunter stärkere Heuristiken, parallele Suche und alternative Zustandskodierungen.

Railway shunting is a fundamental and computationally challenging task in rail operations. This thesis investigates whether Kronecker algebra can provide a modeling foundation for shunting problems and whether such models can be searched efficiently to produce shunting solutions. We formalize tracks, railcars, and admissible movements using matrixbased operations (Kronecker products and sums) to obtain a state-space model. The framework is extended to multiple locomotives, specifically for the two-locomotive version, with one locomotive at each end of the tracks, which to our knowledge has not been studied before. To search for a solution, we ended up using A-star search with several different heuristics. An experimental evaluation on randomized instances inspired by theInglenook Shunting puzzle and multi-track layouts shows that the choice of heuristics is crucial for the performance of the search. The main limitation is scalability. The state space grows exponentially with tracks and railcars, which makes large configurations challenging to search. We outline directions for future work, including stronger heuristics, parallel search, and alternative state encodings.