Unser Projekt Trassenbörse
(Stand dieser Informationen: 20. Dezember 2012)
Inhalt
Projektpartner
Dies ist eine gemeinsame Informationsseite des interdisziplinären Forschungsprojekts Trassenbörse, das von IMP entworfen und begleitet wurde. Es lief von 2004 bis 2009 in drei Phasen. Es wurde in Phase I durch das Bundesministerium für Bildung und Forschung (BMBF) gefördert, anschließend durch das Bundesministerium für Wirtschaft und Technologie (BMWi).
Als Projektpartner waren beteiligt:
IMP Ilgmann Miethner Partner | Management Consultants
IVE – Institut für Verkehrswesen, Eisenbahnbau und -betrieb, Universität Braunschweig (nur Phase II und III; auch war das IVE vor 2009 der Leibniz Universität Hannover zugeordnet)
SFWBB – Fachgebiet Schienenfahrwege und Bahnbetrieb an der Technischen Universität Berlin (TU Berlin)
WIP – Fachgebiet Wirtschafts- und Infrastrukturpolitik an der TU Berlin
ZIB – Konrad-Zuse-Zentrum für Informationstechnik Berlin (kurz: Zuse-Institut Berlin)
Überblick
Was ist die Trassenbörse? Ein langjähriges Forschungsprojekt. Und im Ergebnis eine neue Methode, Fahrpläne für die Eisenbahn zu schreiben und Schienennetze zu vermarkten, auszubauen und anzupassen.
Das Projekt hat viele Aspekte und handelt von mindestens zwei großen Ideen.
Die erste Idee ist eine mathematische. Computertechnik und Rechenverfahren entwickeln sich gewaltig und sind heute im Prinzip leistungsfähig genug, um Fahrpläne auch größerer Schienennetze nach vorher gewählten Zielfunktionen optimiert errechnen zu lassen.
Man muss dazu wissen: Traditionell schreiben oder zeichnen die Betreiber von Eisenbahnnetzen ihre Fahrpläne heute immer noch von Hand (wenn auch oft am Bildschirm), und natürlich wird dabei fast immer der Plan fortgeschrieben, der schon vergangenes Jahr und all die Jahre zuvor funktioniert hat. Von rühmlichen Ausnahmen von dieser Regel werden wir hier eines Tages hoffentlich noch berichten können.
Die zweite Idee stammt aus der Verkehrspolitik. Richtlinien der EU schreiben seit 1991 ihren Mitgliedsstaaten die Öffnung des Eisenbahnmarktes vor – ein langwieriges Vorhaben, das nur Schritt für Schritt zu bewältigen ist. Seit Anfang 2007 besitzen immerhin die Güterverkehrsunternehmen ein Recht auf beliebige grenzüberschreitende Verbindungen.
Die berechtigte Hoffnung ist, dass Wettbewerb die Leistungsfähigkeit des Systems Eisenbahn zu unser aller Nutzen in Europa steigern wird. Echter Wettbewerb und Konkurrenzdruck auf der Schiene sollen und werden zweifellos die Verkehrsunternehmen veranlassen, die Servicequalität in Form von Kundenfreundlichkeit, Pünktlichkeit, Energieeffizienz und einer transparenten Informationspolitik dauerhaft zu steigern.
Verlangt ist damit aber auch eine neue Vermarktung von Schienennetzen – also Fahrrechte (eben die „Trassen“) an diese Unternehmen im Wettbewerb zu vergeben. Das kann man zum Beispiel über Versteigerungen lösen. Der Einsatz simpler und bereits bekannter Verfahren von Auktionen wird dazu aber nicht reichen, und es wird in jedem Fall die computerisierte Erzeugung von Fahrplänen brauchen, um die Trassen optimal vergeben zu können.
Was ist der Hintergrund dieser Idee? Europäische Eisenbahnverkehrsunternehmen sehen sich gewaltigen Herausforderungen gegenüber, im Übergang von nationalen Staatsbahnen zu global agierenden Eisenbahnverkehrsunternehmen. Im Fall der Eisenbahninfrastrukturunternehmen ist vor allem die Zuteilung der Trassen und die Erstellung des Jahresfahrplans eine Kernaufgabe. Allein im Jahr 2012 stieg in Deutschland die Anzahl der Trassenanmeldungen um rund 6,6 Prozent gegenüber dem Vorjahr und erreichte ein neues Rekordhoch mit knapp 60 000 Bestellungen, die zur Konstruktion des Netzfahrplans 2013 berücksichtigt werden mussten.
Neben langfristigen Kapazitätserweiterungen der Eisenbahninfrastruktur ist es möglich, den Prozess der Trassenzuteilung durch mathematische Optimierung zu unterstützen, um diese steigende Nachfrage im gegebenen Netz zu bewältigen. Das ist eine der Grundideen für eine „Trassenbörse“. Es waren Prof. Jürgen Ewers von der Technischen Universität Berlin und Dr. Gottfried Ilgmann von IMP, die im Jahr 2002 unter diesem Namen ein ambitioniertes Forschungsvorhaben ins Leben riefen und die Förderung durch das Bundesministerium für Forschung und später durch das Bundesministerium für Wirtschaft und Technologie erhielten.
In der Frankfurter Allgemeinen Sonntagszeitung vom 29. Januar 2006 wurde der Artikel „Trassen unter dem Hammer“ von Klemens Polatschek veröffentlicht, der ebenfalls plastisch die Ambitionen dieses Projekts illustriert. (Der Artikel ist auf dieser Seite hier abrufbar.)
Marktwirtschaft auf der Schiene? Wie soll das überhaupt funktionieren? Beauftragt mit der Suche nach Antworten fand sich ein Team aus Wissenschaftlern aus den Bereichen Verkehrswesen, Bahnbetrieb, Wirtschafts- und Infrastrukturpolitik und der Mathematik. Die weiteren Seiten beleuchten Details der Vorgehensweise und Ergebnisse in der Erzeugung optimaler Fahrpläne.
Auktion
Wirtschaftlicher Wettbewerb bei der Eisenbahn verlangt eine neue Vermarktung von Schienennetzen – zum Beispiel die Vermarktung von Fahrrechten, der sogenannten „Trassen“. Eine Trasse ist gewissermaßen das Recht, einen physischen Gleisabschnitt für einen Zeitraum von zum Beispiel 8 bis 9 Uhr mit einem Zug – genauer gesagt einem Zug eines bestimmten Typs – zu befahren. Auftretende Konflikte zwischen den Trassenwünschen der verschiedenen Transportunternehmen über Versteigerungen zu lösen und mit Hilfe computergestützter Erzeugung von Fahrplänen die Trassen optimal zu vergeben – das war unsere Herausforderung.
Mittlerweile gibt es einen Präzedenzfall für ein solches Verfahren: im Land mit dem dichtesten Eisenbahnnetz der Welt. Die unabhängige Trassenvergabestelle der Schweiz – die Trasse Schweiz AG – hat unser Optimierungsverfahren bei der Erstellung des Fahrplans 2012 für einen kleinen Engpassbereich – den Simplon-Tunnel durch die Alpen – erfolgreich genutzt und so unsere Vision langsam Realität werden lassen. Dazu noch mehr im letzten Abschnitt Der optimale Fahrplan.
Etwas wissenschaftlicher gesprochen befasst sich das interdisziplinäre Projekt Trassenbörse mit der Fragestellung, ob ein auf einer Auktion basierender Vergabemodus für Eisenbahnfahrtrassen zu einer wettbewerbsorientierten Vermarktung eines Schienennetzes führen kann. Die Idee besteht darin, konkurrierende Eisenbahnverkehrsunternehmen in einer Auktion für beliebige Trassen bieten zu lassen und auftretende Konflikte über Preise zu lösen, indem die Trassen einer erlösmaximalen Allokation zugeteilt werden. In dem Projekt wird die Machbarkeit dieses Ansatzes untersucht. Dabei treten Fragestellungen aus den Bereichen Ökonomie, Eisenbahnbetrieb und Mathematik auf, die von den Kooperationspartnern des Projekts bearbeitet werden.
Die erste Herausforderung besteht darin, ein komplexes System wie den Schienenverkehr in geeigneter Weise so zu modellieren, dass es einerseits noch möglich ist, Berechnungen durchzuführen, aber andererseits keine betriebswichtigen Einzelheiten unterschlagen werden. Die Projektpartner SFWBB und IVE arbeiten an zwei unterschiedlichen Ansätzen, deren Kombination diese Eigenschaften haben soll. Es handelt sich dabei zum einen um eine makroskopische Modellierung, die durch vereinfachende Annahmen eine Grobplanung ermöglicht, und um ein mikroskopisches Modell, das durch eine gleis- und weichengenaue Darstellung der Fahrten individueller Züge eine Feinsimulation erlaubt. Durch eine geeignete Kopplung dieser Modelle soll ein iterativer Planungsablauf über eine Grob- zur Feinplanung realisiert werden.
Ein weiteres Problem besteht darin, ein geeignetes Design und Regelwerk für eine so komplexe Auktion wie die von Fahrtrassen zu finden, die zu einer verbesserten Netzauslastung und einem aus volkswirtschaftlicher und ökonomischer Sicht effizienten Fahrplan führt. Die Projektpartner am WIP arbeiten außerdem an der Entwicklung einer flexiblen Auktionssprache, die den Anforderungen von Eisenbahnverkehrsunternehmen entspricht und ihnen die Möglichkeit gibt, ihre Trassenwünsche zu spezifizieren; dies ist vor allem aus praktischer Sicht wichtig.
Trassenzuteilung
Im Verlauf der Auktion muss in jeder Runde auf der makroskopischen Ebene ein sogenanntes Trassenallokationproblem optimal gelöst werden, bei dem die jeweils zuzuteilenden Trassen bestimmt werden. Das Optimierungspotenzial liegt dabei hauptsächlich in der Gewinnung von Kapazität durch Bündelung von Verkehren, siehe die folgenden Abbildungen von Fahrzeittreppen.
… ohne Bündelung
… mit Bündelung
Das Bestimmen eines Zugfahrplanes oder äquivalent einer Gleisallokation kann als Parade-Anwendung des Operations Research gesehen werden. Dabei muss die richtige Entscheidung über den Verbrauch der raren Infrastrukturkapazitäten, also die Allokation der Gleisabschnitte und der Bahnhöfe gefunden werden. Dieses Optimierungsproblem lässt sich als ein Mehrgüterflussproblem der kombinatorischen Optimierung mit zusätzlichen Packungsbedingungen in einem zeitexpandierten Infrastrukturgraphen (siehe die nächste Abbildung) modellieren. Auch arbeiten wir an neuen Modellen für diese Aufgabenstellung als gekoppeltes Pfad-Überdeckungsproblem.
Trasssenplanungsgraph
Zur Lösung solcher Probleme hat der Projektpartner ZIB einen Ansatz zur ganzzahligen Optimierung (Integer Programming, IP) entwickelt, mit dem unter Zuhilfenahme der Modellierungsprache ZIMPL und des IP-Lösers CPLEX kleine und mittlere Szenarien mit einigen hundert Trassen optimal gelöst werden können. Um das langfristige Ziel, das Lösen von realitätsnahen und großen Instanzen, zu verwirklichen, muss die Leistungsfähigkeit dieses Verfahrens noch gesteigert werden.
Makroskopische Fahrplandarstellung
In Projektphase II wurde am ZIB mit der Entwicklung eines Optimierungswerkzeugs TS-OPT begonnen, das ein speziell auf das Trassenallokationsproblem angepasstes Spalten-Erzeugungs-Verfahren implementiert. Dieser Ansatz erlaubt es, lineare Programme mit Millionen von Variablen implizit optimal zu lösen, also ohne jemals die Gesamtheit aller Spalten oder Variablen betrachtet haben zu müssen. Mit Hilfe dieser Technik werden Planungsprobleme der Praxis von enormer Größenordnung nahezu optimal gelöst. In zahlreichen Projekten aus den Bereichen des öffentlichen Personenverkehrs zur Dienstplanung, zur integrierten Dienst- und Umlaufplanung, zur Angebots- und Linienplanung, aber auch zur Personalplanung im Luftverkehr wurde dieses Know-how bereits erfolgreich eingesetzt.
Zur besseren Illustration der Probleme und ihrer berechneten Lösungen, aber auch zur Ideenfindung und zur Datenanalyse entwickelt das ZIB neben dem Optimierungstool TS-OPT eine Darstellungs-Software namens TraVis (Trassen-Visualisierung). Basierend auf JavaView wurde dieses Programm von M. Kinder am ZIB implementiert und seit 2008 von B. Erol weiterentwickelt.
Screenshot des Programms TraVis
Der optimale Fahrplan
Zu den wichtigsten Ergebnissen des Projekts „Trassenbörse“ gehört die Erzeugung von Bahnfahrplänen, die beweisbar mathematisch optimal sind – also eine Strecke bestmöglich für ein definiertes und quantifizierbares Ziel nutzen. 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, über 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 tiefer gehende betriebliche Fahrplan aus Sicht des Netzunternehmens. Ein Fahrplan im Schienenverkehr legt den kompletten Fahrtverlauf eines Zuges fest, das heißt die Ankunfts-, Abfahrts- und Durchfahrtszeiten an allen Orten und in allen Gleisabschnitten. Das Netzunternehmen muss jedoch alle Züge, die im Netz verkehren, sowohl Personenzüge des Regional- und Fernverkehrs als auch die 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 der folgenden Abbildung zeigen wir das Beispiel einer Lösung für eine gegebene Trassennachfrage.
Fahrplan für 198 Züge, dargestellt in TraVis
Zu sehen ist ein Fahrplan-Bild in drei Dimensionen. Der Plan enthält 198 Züge in einem Ausschnitt des Schienennetzes zwischen Hannover, Kassel und Fulda. 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, Regionalbahnen, 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 großen 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. Der öffentliche Schlussbericht zur Betriebsqualitätsprüfung durch das beauftragte Unternehmen (SMA und Partner AG) macht klar, dass es sich eigentlich um einen winzigen Ausschnitt des deutschen Netzes 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 erschaffen – 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 Regionalverkehrsunternehmens 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 zusammengerechnet 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, also 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 zum Beispiel der Bündelmethode und der Rapid-Branching-Heuristik.
Diese Methoden 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 bei der Eisenbahn 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.