Optimierung

ZIB  →  Diskrete Methoden  →  Optimierung  →  Projekte  →  Verkehr und Logistik  →  Trassenbörse

Trassenbörse

Trassenvergabe im Bahnverkehr

Das interdisziplinäre Projekt Trassenbörse befasst sich 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, in dem 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 im Verbund bearbeitet werden.

teaser

Ziele

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 ausserdem 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 von grosser Wichtigkeit.

Modell

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 untere Abbildungen. Aber auch die netzweite Betrachtung des Problem bietet Potentiale, z.B. verschiedene Laufwege und Routen - im Gegensatz zur üblichen Korridorplanung.

Fahrzeitentreppe ohne Bündelung. Fahrzeitentreppe mit Bündelung.
Fahrzeitentreppe ohne Bündelung. Fahrzeitentreppe mit Bündelung.

Das Bestimmen eines Zugfahrplanes oder äquivalent einer Gleisallokation kann als Parade-Anwendungs-Beispiel des Operations Research gesehen werden. Die richtige Entscheidung über den Verbrauch der raren Infrastrukturkapazitäten, d.h. die Allokation der Gleisabschnitte und der Bahnhöfe, muss dabei gefunden werden. Natürlich gibt es verschiedenste Wege dieses Problem zu spezifizieren. Wir haben uns deshalb entschlossen eine Standardisierung des makroskopischen Fahrplanproblems einzuführen, siehe unter TTPLib.

Optimierung

Dieses Optimierungsproblem lässt sich als ein Mehrgüterflussproblem der kombinatorischen Optimierung mit zusätzlichen Packungsbedingungen in einem zeitexpandierten Infrastrukturgraphen (siehe untere Abbildung links) modellieren. Zur Lösung solcher Probleme hat unsere Arbeitsgruppe einen IP-Ansatz 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 unser langfristiges Ziel, das Lösen von realitätsnahen und grossen Instanzen, zu verwirklichen, müssen wir die Leistungsfähigkeit dieses Verfahrens verbessern. Wir haben dazu in der Projektphase II mit der Entwicklung eines Optimierungstools TS-OPT begonnen, das ein speziell auf das Trassenallokationsproblem angepasstes Spalten-Erzeugungs-Verfahren implementiert.

In diesem Modell wird das Problems als gekoppeltes Pfad-Überdeckunsproblem dargestellt, wobei wir darauf verzichten alle Pfade zu generieren. Vielmehr erzeugen wir auf Basis der Lösung der linearen Relaxierung lediglich dynamisch die relevanten Variablen. Aktuell arbeiten wir daran einzelne Komponenten des Verfahrens zu beschleunigen, z.B. das Lösen der linearen Relaxierungen mit Hilfe des Bündelverfahren anstelle eines Standard-LP Lösers in CPLEX. Aber auch Heuristiken zum Finden von Primallösungen können den gesamten Branch-Bound-Price-Ansatz erheblich unterstützen und letztendlich zu einer beweisbar optimalen Lösung führen.

Trassenplanungsgraph. Makroskopische Fahrplanlösung.
Trassenplanungsgraph. Makroskopische Fahrplanlösung.

TraVis

Unter folgenden Link (> 8MB) ist ein live Mitschnitt unseres Visualisierungstools TraVis zu sehen. Basierend auf JavaView wurde es von M.Kinder und B.Erol am ZIB entwickelt. Ein zulässiger Fahrplan mit ungefähr 200 Zügen wird animiert. Eine für akademische Zwecke frei verfügbare Version kann hier runtergeladen werden.

Screenshot von TraVis.

TTPLib

Die Train Timetabling Problem Library TTPLib bietet frei verfügbar unsere entwickelte XML-Spezifikation des Problems, eine Reihe von Instanzen, die während des Projektes entstanden sind, und zahlreiche hilfreiche Informationen rund um das TTP.

TTP Lib Banner

Publikationen

Poster und mehr

  • Poster (2004) [.pdf]
  • Poster (2006) [.pdf]
  • Film (2007) [.mpg]
  • Poster (2008) [.pdf]