Railway Shunting via Kronecker Algebra

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.