immer einen Algorithmus voraus



R-OPT


Steckbrief

R-OPT ist ein integrierter Algorithmus zur Optimierung von Zugumläufen für den Schienenverkehr. Aus den Fahrten eines Fahrplans berechnet der Algorithmus gleichzeitig effiziente Fahrtenketten und Zugverbände sowie notwendige Fahrzeugwartungen.

Die Bindung der Fahrzeuge an die Schiene führt zu den besonderen Herausforderungen des Bahnsystems. So dürfen z.B. Fahrzeuge nur unter bestimmten Voraussetzungen zu Zugverbänden vereinigt werden können, weil es beispielsweise schwieriger oder unmöglich ist ein Fahrzeug von einem blockierten Ende des Verbandes abzukuppeln, um mit einem anderen Zugverband weiterzufahren. Fachlich heißt das insbesondere, dass die Reihung und die Orientierung von Fahrzeugen innerhalb von Zugverbänden eine zentrale Rolle spielt.
Neben den unbedingt einzuhaltenden Wartungsfristen für Fahrzeuge gibt es z.B. auch begrenzte Abstellkapazitäten in Betriebshöfen und Abstellgleisen, die nicht ignoriert werden dürfen.
Mathematisch gesehen sind die für Züge üblichen mehrwöchigen Umläufe Kreise eines Hypergraphen, mit dem sich die Zugumläufe mit gegenseitigen Abhängigkeiten elegant und äußerst exakt modellieren lassen.

LBW entwickelt neue mathematische Optimierungsverfahren basierend auf aktuellen wissenschaftlichen Ergebnissen, die von LBW in Zusammenarbeit mit dem Zuse-Institut Berlin im RailLab des Forschungscampus Modal erarbeitet worden sind. Diese Algorithmen zerlegen das riesige kombinatorische Planungsproblem in einzelne strukturierte mathematische Teile, sogenannte Layer. Mit diesen gelingt der Übergang zwischen übergeordneten Aspekten wie Fahrzeugauswahl und Wenden bis hin zur Reihung und Orientierung. Alle Layer haben eine hohe Bedeutung für die Gesamteffizienz und Umsetzbarkeit der Planungsresultate. Mithilfe komplexer parallelisierbaren Hochleistungsalgorithmen lassen sich auf diese Weise äußerst effiziente und fahrbare Umläufe im Planungssystem IVU.rail berechnen.

Beschreibung


R-OPT optimiert zyklische Fahrzeug-Umläufe für eine Standardwoche. Die zu verplanenden Fahrten der Fahrzeuge stammen aus einem Fahrplan, das können z.B. Fahrgastfahrten sein, die von Personenzügen bedient werden müssen. R-OPT arbeitet auf der Basis von Einzelfahrzeugumläufen. D.h. für jede Fahrzeugeinheit (d.h. für Gruppen aus Fahrzeugen, die aus planerischer Sicht eine Einheit bilden) wird ein Umlauf erstellt.
Die Umläufe überdecken alle zu verplanenden Fahrten. Eine Fahrt kann von mehreren Fahrzeugen bedient werden, die dann einen Zugverband bilden. Hauptziele der Optimierung ist die Reduktion der Fahrzeuganzahl, der gefahrenen Fahrzeugkilometer, der Wartungskosten und die Erhöhung der betrieblichen Stabilität.
Damit R-OPT berechnen kann, welche Fahrten in welcher Reihenfolge zu Umläufen verknüpft werden können, benötigt unser Algorithmus Informationen über die Fahrzeit zwischen den verschiedenen Betriebspunkten, Vorschriften über Wendezeiten zwischen den Fahrten und der Beschaffenheit der Gleise an bestimmten kritischen Abschnitten des Netzes. Damit kann R-OPT unter anderem folgende technischen und betrieblichen Vorgaben bei der Erstellung von Umläufen berücksichtigen:

Typischerweise muss ein Fahrzeug nach einer bestimmten zurückgelegten Strecke oder nach einer gewissen Betriebsdauer in einer Werkstatt gewartet werden. Dabei kann es je Fahrzeugtyp mehrere Wartungen mit unterschiedlichen Intervallen geben, die berücksichtigt werden müssen. Ähnlich modelliert sind Fahrzeugreinigung und -betankung, die auch in bestimmten Intervallen an vorgegebene Betriebsstellen durchgeführt werden müssen
Fahrzeuge können nicht an beliebigen Stellen im Netz abgestellt oder gewartet werden. Die Orte an denen Wartungen und Abstellungen durchgeführt werden dürfen, haben aber eine begrenzte Kapazität.

R-OPT muss daher berücksichtigen, dass nicht zuviele Fahrzeuge gleichzeitig an einem Ort sein dürfen. Dasselbe gilt für Bahnhöfe, auch hier dürfen sich gleichzeitig nur eine begrenzte Zahl von Fahrzeugen aufhalten.

Wenn ein Fahrplan an verschiedenen Betriebstagen die gleichen Fahrten zu denselben Uhrzeiten enthält, dann solten diese Fahrten auch auf die gleiche Art zu Umläufen verknüpft werden.

Dies erleichtert die Planungsschritte, die auf die Umlaufplanung folgen, und erhöht die betriebliche Stabilität.

Fahrzeuge, die gemeinsam eine Fahrgastfahrt bedienen, werden zu Zugverbänden (oder kurz Zügen zusammengefasst). Dabei muss beachtet werden in welcher Reihenfolge die Fahrzeuge im Zugverband enthalten sind und welche Ausrichtung sie haben. Von der Reihenfolge ist z.B. abhängig, welche Folgefahrten Fahrzeuge machen können,
wenn sie eine Fahrt beendet haben, da je nach Gleistopologie z.B. nur Fahrzeuge am Zugbeginn oder -ende abgekuppelt werden können. Außerdem kann es Vorgaben geben, auf welcher Seite vom Bahnsteig sich die Wagen der ersten Klasse befinden sollten.

Abbildung 1– zyklische Lösung des Planungsproblems mit Fahrgastfahrten in blau, Standzeiten und Leerfahrten in rot.

Modell

Unser mathematisches Basismodell ist ein ganzzahliges LP-Modell, das auf einem Mehrgüter-Fluß-Problem basiert, welche um Zugbildungs-Bedingungen ergänzt wurde. Der Planungsgraph enthält (jeweils mehrere) Kanten für die zu verplanenden Fahrgastfahrten und Kanten für die möglichen Verknüpfungen der Fahrgastfahrten. Der Planungsgraph ist zyklisch, das heißt, die Fahrten am Sonntag sind wieder mit den Fahrten am Montag verknüpft.

Wartungen sind in diesem Modell nur rudimentär durch verschiedene Schichten im Graphen abgebildet. Dieses Modell unterscheidet sich von den Vorarbeiten im Forschungsprojekt des ZIB (siehe Reuther et al.), da es angepasst wurde, um es mit einer Bündel-Method lösbar zu machen. Die allgemeine Methodik ist für IS-OPT entwickelt worden und hier publiziert. Das Modell von R-OPT beinhaltet aber die selben Grundeigenschaften.

Algorithmischer Ansatz


R-OPT läuft in zwei Phasen. In der ersten Phase wird eine fast optimale Lösung unseres mathematischen Modells mit einem Rapid-Branching-Ansatz berechnet. Damit bekommen wir eine zulässige Lösung eines vereinfachten Umlaufplanungsproblems. In der zweiten Phase werden alle Restriktionen und Anforderungen in einer Tauschheuristik mit dynamischer Tiefensuche (DEX) berücksichtigt. Dadurch wird ein lokales Optimum gefunden, das sich typischerweise in der Nähe der unteren Schranke befindet, die wir in der ersten Phase berechnet haben.

Anwendung


R-OPT ist integriert in dem Planungssystem IVU.rail der IVU Traffic Technologies AG. Es wird von vielen Eisenbahngesellschaften, wie z.B. von Trenitalia (siehe Pressemitteilung der IVU) benutzt.