Routing mit Zielfunktion für den Bahnhof Bern

Zusammenfassung

Auf Grund neuer Zugssicherungstechnologien können in Zukunft die Sicherheitsabstände zwischen zwei Zügen zeitlich verkürzt werden. Der dadurch gewonnene Freiraum kann für eine Fahrplanverdichtung genutzt werden, um so das Angebot für die Bahnkunden weiter auszubauen. Der Nachteil eines verdichteten Fahrplanes liegt auf der Hand: Durch die Verkürzung des Zugabstandes wächst die Gefahr, dass eine Verspätung eines Zuges grosse Auswirkungen auf den gesamten Fahrplan hat. Um bei verdichtetem Fahrplan den gleichen Qualitätsstandard wie heute zu erreichen, sind zwei Massnahmen notwendig: Einerseits muss die Pünktlichkeit der Züge auf allen Ebenen gesteigert werden und andererseits müssen allfällige Verspätungen bereits beim Einplanen der Züge berücksichtigt werden.

In dieser Diplomarbeit wurde ein Teilaspekt des Einplanens untersucht, nämlich das Routing der Züge, d.h. das Auffinden von Wegen – je einen pro Zug – in einer vorhandenen Gleistopologie bei gegebenem Fahrplan unter Einhaltung aller Sicherheitsabstände. Ein Weg besteht aus einer Kantenfolge der verwendeten Topologie vom Ein- bis zum Austrittsort des betracheten Gebiets mit den entsprechenden Durchfahrtszeiten. Gesucht ist aber nicht ein beliebiges zulässiges Routing, sondern eine Lösung mit möglichst grossen Zeitfenstern, so dass Verspätungen des einen Zuges möglichst „automatisch“ behoben werden, d.h. ohne dass die geplanten Routen anderer Züge geändert werden müssen. Als Testszenarien wurden zwei Varianten der Topologie der Region Bern mit dem dazugehörigen aktuellen Fahrplan, sowie einem Beispiel eines künftigen verdichteten Fahrplans verwendet.

Bisherige Methoden haben stets nach zulässigen Lösungen des Routing-Problems gesucht, ohne die Abstände – ausser den notwendigen Sicherheitsabständen – zwischen den Zügen zu berücksichtigen. Hier wurden nun Kriterien eingeführt, damit die Zeitfenster respektive die Abstände zwischen den Zügen maximiert werden. Als ersten Ansatz wurde eine bereits bestehende Methode zur Bestimmung zulässiger Routings erweitert, indem eine Gewichtung eingeführt wurde. Aus der Überlegung, dass bei der Wahl kurzer Routen auch eine Entflechtung der Züge und so grosse Zugabstände realisiert werden können, wurden kurze Wege stärker gewichtet als lange. Es hat sich aber herausgestellt, dass kurze Wege zu bevorzugen, nur eine leichte Vergrösserung der Zeitfenster zur Folge hat, und umso kleiner wird – manchmal sogar schlechter als irgendeine randomisierte Lösung – je dichter der betrachtete Fahrplan ist.

Auf Grund dieser Erfahrungen wurde eine neue Heuristik entwickelt, die versucht bestehende Lösungen lokal zu verbessern. Dabei wurde eine Nachbarschaftssuche implementiert, die, ausgehend von einer Startlösung, einer gewissen Anzahl Züge jeweils neue, bessere Routen zuweist. Wie die erhaltenen Resultate zeigen, können so Lösungen erhalten werden, die etwa doppelt so gut wie die Startlösung sind und kaum von dieser abhängen. Auch bei sehr dichten Fahrplänen konnte so eine deutliche Verbesserung erzielt werden, wenn auch nicht immer eine Verdoppelung des Zielfunktionswertes erreicht wurde.

Durch diese Arbeit wurde aufgezeigt, dass es sich lohnt bereits bei der Planung den Zügen vorbestimmte Wege zuzuordnen und dass dadurch gewisse (kleinere) Verspätungen behoben werden, ohne dass ein Disponent aktiv in das System eingreifen muss. In zukünftigen Arbeiten könnte man versuchen den Fahrplan nicht mehr zu fixieren und durch kleine zeitliche Verschiebungen einzelner Züge die Zeitfenster noch einmal zu vergrössern.