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.

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

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.