Trassenbörse

Direkt zum Inhalt springen

Der optimale Fahrplan

Zu den wichtigsten Ergebnissen des Projekts „Trassenbörse“ gehört die Erzeugung von Eisenbahnfahrplänen, die beweisbar mathematisch optimal sind – also eine Strecke bestmöglich zur Erreichung eines definierten Zieles ausnutzen. Unabhängig von der Vermarktung eines Schienennetzes – zum Beispiel eben über eine spezielle Versteigerung – kann schon die automatisierte Fahrplanung bei Entscheidungen über den Umgang mit der Infrastruktur, ihre Nutzung und die Art eines Ausbaus, höchst hilfreich sein. Unseres Wissens ist eine Fahrplanung dieser Art hier weltweit erstmals gelungen.

Ein Fahrplan ist ja nicht nur das, was wir alle als Passagiere an den üblichen Aushängen sehen, sondern der viel tiefergehende betriebliche Fahrplan aus Sicht des Netzunternehmens. Ein Fahrplan im Schienenverkehr legt den kompletten Fahrtverlauf eines Zuges fest, d.h. die Ankunfts-, Abfahrts- und Durchfahrtszeiten an allen Orten und in allen Gleisabschnitten. Das Netzunternehmen muss nun aber alle Züge, die im Netz verkehren, sowohl Personenzüge des Regional- und Fernverkehrs als auch unterschiedlichste Güterzüge, gleichzeitig koordinieren und steht so vor einem gewaltigen Fahrplanrätsel.

Die Konstruktionsgrundlagen richten sich dabei nach den Sicherungssystemen im Schienenverkehr, die überall auf der Welt dem selben Prinzip folgen. Ein Zug muss Gleisabschnitte für eine gewisse Zeit für die Durchfahrt reservieren – sogenannte Blöcke. Das gleichzeitige Belegen eines Blocks durch zwei Züge wird Blockkonflikt genannt und ist dementsprechend in der Konstruktion des Fahrplans verboten.

In untenstehender Abbildung ist ein möglicher Fahrplan für eine gegebene Trassennachfrage in 3D zu sehen.

Darstellung von 198 Zügen im Visualisierungsprogramm TraVis

Dargestellt ist ein Fahrplan mit 198 Zügen in einem Ausschnitt des Schienennetzes zwischen Hannover, Kassel und Fulda mit unserem Visualisierungsprogramm TraVis. In der x-y-Ebene sind die Schienenwege räumlich dargestellt, der z-Wert zeigt die Zeitinformation und führt so die Zugfahrten plastisch vor Augen – für jeden Zugtyp (ICE/IC, RE, Güterzüge) werden dabei unterschiedliche Farben verwendet.

Traditionell erstellen die Betreiber von Eisenbahnnetzen ihre Fahrpläne immer noch von Hand, wenn auch mittlerweile an unzähligen Bildschirmen und mit Hilfe von gigantischen Datenbanken in Rechenzentren. Der neue Fahrplan orientiert sich jedoch meist an seinem Vorgängerplan vom Jahr zuvor. Die Komplexität der Bahnwelt zu beherrschen ist schier unmöglich für den Einzelnen. Bereits scheinbar überschaubare Fragestellungen können nicht schlüssig und stichhaltig beantwortet werden.

Das umstrittene Projekt Stuttgart 21 ist hierfür ein Paradebeispiel. Dem öffentlichen Schlussbericht zur Betriebsqualitätsüberprüfung des beauftragten Unternehmens (SMA und Partner AG) kann man entnehmen, dass es sich eigentlich um einen winzigen deutschen Netzausschnitt handelt, jedoch umfasst dieser bereits 360 Stationen, 2500 Weichen und Kreuzungen, 5400 Signale und 7700 Blockabschnitte. Im Betrachtungszeitraum von 4 bis 13 Uhr wurde ein Fahrplan mit 760 Zügen aus 20 unterschiedlichen Typen, wie er mit einer gewissen Wahrscheinlichkeit in Zukunft zu erwarten ist, 100-mal simuliert. Eine abschließende überzeugende Aussage hinsichtlich des Projektnutzens kann ein einziger simulierter Fahrplan jedoch nicht glaubhaft liefern.

Erstrebenswert und mit mathematischen Methoden und der heutigen Rechenleistung ist eine deutlich umfangreichere Untersuchung verschiedener zukünftiger Szenarien mit zahlreichen variierenden Modellannahmen durchaus möglich. Einen Fahrplan zu kreieren – also konfliktfreie Trassen der Züge zu planen – ist letztendlich ein klassisches Optimierungsproblem. Die Trassen sind die Objekte, die wir auswählen müssen, und das Schienennetz mit Milliarden von Blöcken in Ort und Zeit beschreibt die beschränkte Ressource.

Nehmen wir an, für den Gleisabschnitt von A nach B wird zuerst die Anfrage eines Regionalverkehrsunternehmen für Trassen auf diesem Abschnitt von 8 bis 10 Uhr, von 12 bis 14 Uhr und von 16 bis 18 Uhr angenommen. Erst danach meldet sich ein Fernverkehrsanbieter, der Trassen von 8 bis 9 und 16 bis 17 Uhr benötigt. Diese Anfrage kann natürlich vom Netzbetreiber nicht mehr akzeptiert werden, da jeweils immer ein Blockkonflikt zwischen den Trassen vorliegt, genauer gesagt für den Block von 9 bis 10 Uhr und für den Block von 13 bis 14 Uhr. Nehmen wir jetzt an, zwei weitere Unternehmen wollen Güterzüge von 9 bis 12 und 13 bis 16 Uhr fahren lassen, dann wird es schon deutlich komplizierter. Anstelle der drei zu Beginn zugeteilten Trassen liefert mathematische Optimierung, unter der Annahme, dass alle die gleichen Trassenpreise für ein Stunde zahlen müssen, eine Lösung mit vier Trassen und mit einer Nutzung der Strecke von 8 Stunden anstelle von lediglich 6 Stunden.

Im Szenario einer Trassenbörse würde dieser Konfliktfall gelöst, indem alle Beteiligten Gebote abgeben dürfen und somit diejenigen den Zuschlag bekommen, deren Zahlungsbereitschaften insgesamt am höchsten sind. Das Regionalverkehrsunternehmen müsste demzufolge mehr bieten als alle anderen Beteiligten zusammen, um seine Wunschtrassen zu bekommen. Nur so könnte es den Wettstreit um die Nutzung der beschränkten und kostbaren Infrastruktur gewinnen. Die Kernidee einer Trassenbörse ist deshalb eine mathematische. Computertechnik und Rechenverfahren entwickeln sich gewaltig und sind heute leistungsfähig genug, um Fahrpläne für Schienennetze bezüglich einer vorher gewählten Zielfunktion zu optimieren und die Planungsabteilung der Netzbetreiber bei der Bewältigung ihrer großen Herausforderung zu unterstützen. Optimierung bedeutet, aus der Menge aller technisch realisierbaren Fahrpläne einen auszuwählen, der – im Fall einer Trassenbörse – die Erlöse maximiert, oder der beispielsweise die Kundenzufriedenheit maximiert, oder der die Betriebskosten minimiert oder der einen geeigneten Kompromiss verschiedener Ziele insgesamt optimiert. Das Prinzip ist, eine Modellwelt zu konstruieren und die Trassen optimal auszuwählen.

Diese Modellwelten bilden alle Elemente der Eisenbahninfrastruktur, d.h. Weichen, Signale, Neigungen und Kurvenwinkel, vollständig und genau ab, ebenso das Beschleunigungs- und Bremsverhalten der verschiedenen Züge. Sie bieten die Möglichkeit, das System Schiene exakt zu simulieren. Ein so feiner Detaillierungsgrad ist allerdings nicht überall erforderlich. Große Teile des Netzes lassen sich ohne Informationsverlust zusammenfassen. Der Trick besteht darin, aus dem riesigen Datenberg ein geeignetes grobes Netz zu konstruieren, in diesem die Planung durchzuführen und das Ergebnis wieder in den Mikrokosmos der Bahnwelt zurückzurechnen. Die Reduktion auf das Wesentliche ist einer der Schlüssel der Mathematik, um derart komplexe und gigantische Probleme überschauen und lösen zu können. Das Wesentliche bei der Trassenplanung ist die Betrachtung der Kapazität.

Wir haben deshalb einen neuartigen Ansatz entwickelt, der Kapazität konfliktabhängig definiert. In unseren Modellen wird die Infrastruktur nur dort, wo tatsächlich Blockkonflikte zwischen den angeforderten Trassen entstehen können, genau unter die Lupe genommen. In den Gleisabschnitten und Netzbereichen, wo problemlos alle angefragten Züge verkehren können, bleibt das Modell grob. Das Neuartige unseres Ansatzes ist hierbei die Beschreibung der Konflikte. Während klassische Modelle immer eine „äußere“ Beschreibung nutzen und so unzulässige Lösungen abschneiden, wird in unserem Konfigurationsmodell die Menge der zulässigen Lösungen durch Hilfsvariablen aufgespannt. Diese Art der Modellierung bezeichnet man in der mathematischen Literatur mit „extended formulation“ – einer inneren Beschreibung des Optimierungsproblems. Ein weiterer Schlüssel zum Lösen derart umfangreicher Probleme ist der Einsatz von leistungsfähigen Algorithmen wie z.B. der Bündelmethode und der Rapid Branching Heuristik.

Diese Methodik haben wir 2009 im Rahmen einer Studie zur Berechnung der theoretischen Kapazität der Simplon-Strecke in der Schweiz entwickelt und eingesetzt. Untersucht wurden verschiedene Betriebskonzepte mit unterschiedlichen Pufferzeiten und variierenden Ausprägungen dieser Strecke zwischen Brig in der Schweiz und Domodossola in Italien. Die errechneten optimierten Fahrpläne wurden simuliert und auf ihre technische Umsetzbarkeit hin erfolgreich überprüft. Unter Annahme der günstigsten realistischen Bedingungen ergänzt unser Plan in optimaler Weise 63 voreingelegte Fahrtrassen des Personenverkehrs durch 137 neu berechnete Güterverkehrs-Trassen. Damit konnte erstmals eine theoretische Kapazität dieser Strecke von 200 Zügen pro Tag nachgewiesen werden.

Dieser Erfolg demonstriert, dass unser Ansatz praxistauglich ist und dass moderne Mathematik Netzbetreiber bei zahlreichen Planungsaufgaben zukünftig unterstützen kann. Fairer Wettbewerb und die Nutzung innovativer Optimierungsverfahren mit dem Ziel einer effizienten Trassenplanung im Eisenbahnbereich kommt uns letztlich allen zugute – schließlich sollte nur die beste Nutzung gut genug sein für ein Eisenbahnnetz, in deren Aufbau so viel Aufwand investiert wurde.

Sorry, the comment form is closed at this time.