Planungsmethoden für die automatische Fahrplangestaltung im Eisenbahnverkehr

Die Gestaltung eines Fahrplans ist jedoch eine hochkomplexe Aufgabe, die zur Zeit nur durch Unterteilungsprozesse gelöst wird. Viele der bestehenden Eisenbahnnetze sind so groß, dass ihre Betreiber gezwungen sind, die Planung eines netzweiten Fahrplans in mehrere Teilschritte zu unterteilen. Oft wird die Planung eines netzweiten Fahrplans durch die Geographie des Netzes in lokale Fahrplanprobleme unterteilt und dann werden die lokalen Ergebnisse manuell oder computergestützt wieder zu einer konsistenten netzweiten Lösung zusammengeführt. Meistens werden die lokalen Ergebnisse anhand von Praxisregeln zusammengeführt, d. h. mittels Heuristiken oder praktischen Erfahrungen menschlicher Planer (z. B. Hochgeschwindigkeitszüge haben Vorrang vor Vorortzügen, First-come-first-serve-Strategien usw.). Als Folge dieses Prozesses entsprechen die berechneten Fahrpläne oft nicht dem optimalen netzweiten Fahrplan. Außerdem lassen sie eine große Anzahl möglicher Lösungen außer Acht, von denen einige wahrscheinlich besser abschneiden würden als die Ergebnisse der derzeitigen Praxis.

Es ist eine große Herausforderung für die Organisation der Eisenbahnen, die derzeitigen Praktiken über die Regeln der Praxis hinaus zu verbessern und bestmögliche Lösungen für alle Probleme des Eisenbahnverkehrsmanagements zu finden.

Netzweite optimale Fahrpläne

Das von Florin Leutwiler unter der Leitung von Francesco Corman, Professor für Verkehrssysteme, durchgeführte Forschungsprojekt konzentrierte sich auf neue Methoden und Algorithmen zur Automatisierung der Bahnplanung mit Anwendung von Dekompositionen. Obwohl theoretisch jede Art der Zerlegung möglich ist, entschied sich das Team, die bei der SBB vorhandene geografische Zerlegung als Ausgangspunkt zu verwenden. Die Idee hinter dieser Unterteilung ist, dass die Auswirkungen von Fahrplanentscheidungen meist lokal sind, d.h. sie betreffen eher zeitlich und räumlich nahe gelegene Züge als weit entfernte. Der neuartige Beitrag des Projekts bestand in der Einbeziehung der Interferenzen zwischen den Zügen, sowohl in der Nähe als auch in der Ferne. Interferenzen zwischen Zügen führen zur Ausbreitung von Verspätungen, was ein bekanntes Problem in dicht befahrenen Eisenbahnnetzen ist.

Mit diesem Ansatz konnte eine Reihe von Gleichungen aufgestellt werden, die angeben, inwieweit die Züge ohne Beeinträchtigung geplant werden können und wann eine Beeinträchtigung unvermeidbar ist. Nur in diesem zweiten Fall ist eine Koordinierung erforderlich. Der daraus resultierende Algorithmus, der diesen Ansatz nutzt, übertrifft die Standardansätze in Bezug auf die Skalierbarkeit deutlich und zeigte eine wesentlich schnellere Rechenleistung.

Die neuartige Methode wurde ausgiebig getestet und auf der Grundlage statistischer Erkenntnisse über wiederkehrende Situationen im Eisenbahnbetrieb verbessert. Die Forschung ging über die ursprünglichen Ziele der SBB hinaus, um einen möglichen innovativen Ansatz in diesem Bereich zu verstehen. Die Wissenschaftler der ETH Zürich haben gezeigt, dass wiederkehrende Situationen teilweise erlernt werden können und die Zerlegungsmethode beschleunigt werden kann.

Kann die Methode noch verbessert werden?

Das Projektteam wollte noch weiter gehen und untersuchte, wie die Berechnungen beschleunigt werden könnten. Sie formulierten das Problem in eine andere Reihe von Gleichungen um, die gleichbedeutend sind mit dem Verständnis, welche Ereignisse leicht in ihrer ursprünglichen Zielzeit geplant werden können und welche nicht.

In dieser neuen Struktur kann ein optimaler Fahrplan mit Hilfe eines in der Literatur weithin bekannten Problems, dem Mengenabdeckungsproblem, gefunden werden, das äußerst effizient gelöst werden kann. In praktischen Experimenten erwies sich die neuartige heuristische Zerlegungsmethode als extrem schnell für Probleme mit Eisenbahnfahrplänen, um eine erste machbare Lösung mit guter Qualität zu bestimmen.

Die Arbeit stellt mehrere neue Ansätze und Erweiterungen für die Automatisierung der Bahnplanung vor. Die neu entwickelten Methoden und Algorithmen zeigen ein verbessertes Laufzeit- und Skalierungsverhalten im Vergleich zu bestehenden Ansätzen. Die Ergebnisse des Projekts wurden in der Dissertation von Florin Leutwiler ausführlich dokumentiert und bilden eine hervorragende Grundlage für die künftige Entwicklung vollautomatischer Systeme für die Bahnfahrplanung und eines Werkzeugs zur Berechnung optimaler Fahrpläne netzweit.

Francesco Corman und Florin Leutwiler reflektieren über ihre erfolgreiche Zusammenarbeit an einem Projekt, das einige Herausforderungen mit sich brachte. Die agilen Arbeitsmethoden und die nicht festgelegten Spezifikationen brachten Schwierigkeiten mit sich, zumal sich der akademische Zeitplan vom Zeitplan der Industrie unterschied. Trotzdem stellte das Team fest, dass die Daten aus der realen Welt für die Validierung ihrer Forschung von großer Bedeutung waren. Florin sah sich aufgrund der Komplexität der Daten mit unerwartetem Mehraufwand bei der Verarbeitung konfrontiert, aber die Vorteile der Verwendung von Daten aus der realen Welt überwogen die Herausforderungen.

Die Zusammenarbeit mit der SBB lieferte dem Team nicht nur wichtige Daten, sondern ermöglichte es ihm auch, vom Fachwissen der SBB beim Verstehen und Verarbeiten der Daten zu profitieren. Darüber hinaus spielte die SBB eine entscheidende Rolle bei der Vorbereitung der für die Erprobung der neuen Lösungen erforderlichen IT-Systeme, so dass sich Florin auf das eigentliche Forschungsthema konzentrieren konnte. Der Weitblick des Teams und der häufige Austausch trugen dazu bei, kurzfristige und innovative Lösungen für die Forschungsfrage zu finden und risikoreichere Ansätze zu erarbeiten, die nur die Wissenschaft bieten kann.

Julian Jordi von der SBB schätzte die reibungslose Zusammenarbeit und die Tatsache, dass die Forscher das reale Problem und die aktuelle Methodik als Ausgangspunkt für die Untersuchung alternativer Methoden und Algorithmen nahmen. Das SBB-Team freute sich über die vielfältigen Möglichkeiten, im Laufe des Projekts Inputs und Ratschläge zu bevorzugten potenziellen Lösungen zu geben.

Der freundschaftliche Wettbewerb zwischen den beiden Parteien ermöglichte es, an der Verbesserung der algorithmischen Methoden zur Lösung des jeweiligen Problems zu arbeiten, was zu einem schnelleren Fortschritt führte.

"Die kontinuierliche Zusammenarbeit mit den Forschern verschaffte unserem Team einen freundschaftlichen Wettbewerb. Beide Parteien arbeiteten gleichzeitig an der Verbesserung der algorithmischen Methoden, die zur Lösung des jeweiligen Problems verwendet wurden. Das war für beide Seiten fruchtbar und hat uns wahrscheinlich schneller vorangebracht, als wenn wir diesen Austausch nicht gehabt hätten."

Die betriebswirtschaftlichen Probleme häuften sich, was zu ständigen Änderungen der Anforderungen und des Datenmodells führte. Dies stellte eine Herausforderung für die Forscher dar, die stabile Instanzen und Datenmodelle für reproduzierbare Forschung benötigten. Trotzdem war die Zusammenarbeit für beide Parteien eine großartige Erfahrung, und sie würden sich wieder für ein Kooperationsprojekt im Rahmen der ETH-Mobilitätsinitiative anmelden. Florin hat seine Dissertation im vergangenen Oktober erfolgreich verteidigt und ist kurz darauf als Applikationsingenieur bei der SBB eingestiegen.