Umlaufplanung ist die Zuordnung von Fahrzeugen zu Fahrten eines Fahrplans und die Verknüpfung dieser Fahrten zu Umläufen. Durch die mathematische Optimierung von insbesondere Fahrzeugressourcen und Leerfahrkilometern können erhebliche Kosteneinsparungen erzielt werden. Dabei ist es möglich, maßgebliche Optimalitätsschranken anzugeben und zu beweisen. Wir betrachten in diesem Projekt ein sehr komplexes Umlaufplanungsproblem für den Personenschienenverkehr.

Im Vordergrund steht die Integration verschiedener Teile zu einem Gesamtmodell. Unser Modell implementiert folgende Komponenten:

• die Wahl von Fahrzeugverbänden für Fahrplan- und Leerfahrten, d.h. es können Einfach- und Mehrfachtraktionen sowie Reisezugwagen abgebildet werden
• die Berücksichtigung von mehreren Instandhaltungsintervallen für einzelne Fahrzeuge
• die Optimierung von "gleichförmigen" Umläufen, vereinfacht bedeutet dies z.B., dass an verschiedenen Verkehrstagen möglichst gleiche Wenden geplant werden
• die Optimierung von Robustheit durch Optimierung von Planwendezeiten

Um zulässige Umläufe zu erzeugen, sind die einzelnen Komponenten sehr detailliert ausmodelliert. Beispielsweise können Reihungspositionen und Orientierungen von einzelnen Fahrzeugen in ihren Fahrzeugverbänden unterschieden und dadurch sehr komplexe Regeln abgebildet werden.  

Wir arbeiten in enger Kooperation mit unserem Praxispartner DB Fernverkehr AG zusammen. Hier betrachten wir die Umlaufplanung für ICE- und IC-Verkehre in Deutschland. Dadurch ist es uns möglich, unser Modell und Lösungsverfahren für reale Anforderungen zu skalieren.

Als Lösungstechniken verwenden wir Ganzzahlige und Dynamische Programmierung. Neben der Verwendung von kommerziellen Lösern entwickeln wir auch eigene, auf das Problem spezialisierte Hochleistungsalgorithmen, um das Umlaufplanungsproblem von Grund auf zu lösen.