Umlaufplanung ist eine grundlegende Aufgabe im Schienenverkehr. Sie beschäftigt sich mit der Konstruktion von Fahrzeugumläufen für Schienenfahrzeuge bei gleichzeitiger Zugbildung. Der Fokus des Projekts ist der Personenfernverkehr. Hier müssen Fahrzeuge in einer bestimmten Reihung und Orientierung und unter Beachtung von "Gleichförmigkeit" zu Zügen verbunden werden.

Wir unterscheiden vier Typen von Gleichförmigkeit:

• Betriebliche Gleichförmigkeit: Wenden sollen regelmäßg sein, d.h., wenn der Zug 4711 in Frankfurt endet und als Zug 4712 am Montag weiterfährt, sollte dies auch am Dienstag, Mittwoch etc., wenn möglich, der Fall sein.
• Fahrtengleichförmigkeit: Fahrzeugverbände sollen gleichförmig sein, d.h., Zug 4711 soll aus den gleichen Fahrzeugtypen in der gleichen Reihung und Orientierung an jedem Wochentag bestehen. Diese Art von Gleichförmigkeit kann gut auf Wagenstandsanzeigern beobachtet werden.
• Darstellungsgleichförmigkeit: Bei der Darstellung von Umlaufplänen sollen ähnliche Wochentage zu einem Umlauftag gruppiert werden.
• Umlaufgleichförmigkeit: Fahrzeugumläufe sollen in möglichst wenige Teile unterteilt sein. Dies hat eine gleichmäßige Abnutzung zum Ziel.

Gleichförmigkeit minimiert durch bessere Übersichtlichkeit die Fehleranfälligkeit und sorgt für eine höhere Transparenz, indem sie einen routinierten Umgang mit allen beteiligten Belangen ermöglicht.

Unser Ansatz basiert auf einem neuartigen Hypergraphen-Modell für das Umlaufplanungsproblem, welches eine universelle Betrachtung aller Zugbildungsregeln inklusive der Reihung, Orientierung, betrieblicher- und Fahrtengleichförmigkeit ermöglicht. In diesem Modell werden Unlaufpläne als Hyperzuordnungen modelliert.

Hyperzuordnungen sind eine Verallgemeinerung von Zuordnungen. Wir haben uns mit Hyperzuordnungen im Allgemeinen und auf sogenannten partitionierten Hypergraphen beschäftigt. Die letzteren haben eine spezielle Struktur, die auch in Umlaufplanungsmodellen vorliegt.

Unsere Komplexitätsuntersuchung hat ergeben, dass das Hyperzuordnungsproblem sogar auf partitionierten Hypergraphen mit Hyperbögen mit nur zwei Start- und Endknoten ist. Außerdem führt die kanonische Formulierung als ganzzahliges lineares Programm zu beliebig großen Lücken zwischen der Lösung des ganzzahligen Programms und der LP-Relaxierung und beliebig großen Basismatrixdeterminanten.

Rechnungen mit realen Daten haben ergeben, dass Cliquenungleichungen den Abstand zwischen IP- und LP-Lösung stark senken, wenn sie zu der kanonischen IP-Formulierung hinzugefügt werden, und deshalb eine wichtige Rolle spielen. Wir haben eine extended formulation des Hyperzuordnungsproblems entwickelt, die beweisbar alle Cliquenungleichungen impliziert und mit Hilfe von Spaltengenerierung gelöst werden kann. Aufbauend auf diesen Ergebnissen haben wir eine polyedrische Untersuchung begonnen und eine Reihe von interessanten Schnittebenen identifiziert.

Polyeder des Hyperzuordnungsproblems haben sogar für kleine Instanzen eine komplexe Struktur. Wir haben die Facetten für den partitionierten Fall mit Hyperbögen mit maximal zwei Start- und Endknoten und sechs Knoten klassifiziert. Wir wollen diese Ergebnisse auf größere Hypergraphen ausweiten und verallgemeinern.

Durch die Entwicklung von Zerlegungs-, Schrumpfungs-, und Lifting-Techniken für Hypergraphen, wollen wir diese Ergebnisse für sehr große Probleme nutzbar machen. Unsere Experimente zeigen auch, dass das Hyperzuordnungproblem gut durch die Benutzung einer kleinen Anzahl wichtiger Facetten approximiert werden kann. Wir versuchen deshalb spezielle Strukturen zu finden, die Approximationsergebnisse zur Folge haben und in praktischen Implementationen genutzt werden können.

Weiterhin wären in Polynomialzeit lösbare Spezialfälle hilfreich, die zu Approximationsergebnissen unter Modifikation der Zielfunktion führen könnten.

Außerdem möchten wir unsere Forschung auf multi-commodity Hyperzuordnungen ausweiten, da diese für die Umlaufplanung von Relevanz sind.