Trassenbörse

Direkt zum Inhalt springen

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 untere Abbildungen.

Fahrzeitentreppe ohne Bündelung. Fahrzeitentreppe 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 erste der unteren Abbildungen) modellieren. Auch arbeiten wir an neuen Modellen für diese Aufgabenstellung als gekoppeltes Pfad-Überdeckungsproblem.

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 großen Instanzen, zu verwirklichen, müssen wir die Leistungsfähigkeit dieses Verfahrens verbessern. Eine Zusammenfassung dieser ersten Arbeiten und der erzielten Ergebnisse finden sich im Artikel „An Auctioning Approach to Railway Slot Allocation“, der im Journal Competition and Regulation in Network Industries 2006 veröffentlicht wurde.

Trassenplanungsgraph. Makroskopische Fahrplanlösung.

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.

Diese Herangehensweise angewandt auf ein neues Modell des Trassenallokationsproblemes wird in der Arbeit „Solving Railway Track Allocation Problems“ thematisiert. Einen analytischen Vergleich dieses neuen Modells mit dem oben bereits erwähnten Mehrgüterflussmodell mit zusätzlichen Packungsbedingungen enthält der Bericht „Models for Railway Track Allocation“.

Zur besseren Illustration der Probleme und ihrer berechneten Lösungen, aber auch zur Ideenfindung und Datenanalyse entwickeln wir 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.

TraVis 2008

Sorry, the comment form is closed at this time.