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

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.