Dekompositionsalgorithmen für mehrstufige Optimierungsprobleme

• Antragsteller: Professor Dr. Marco Lübbecke
• Fachliche Zuordnung: Verkehrs- und Transportsysteme, Intelligenter und automatisierter Verkehr ; Mathematik
• Förderung: Förderung von 2015 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 238487308

Mehrstufige Optimierungsprobleme treten allgemein auf, wenn bestmögliche Entscheidungen im Zeitverlauf getroffen werden müssen und spätere Entscheidungen von früheren abhängen. Beispiele sind die (stufenweise) Erstellung eines Flugplans, Losgrößenplanung oder mehrstufige stochastische Optimierung.Dekompositionsalgorithmen basieren auf einer Reformulierung von ganzzahligen Programmen, die eine dem Problem zugrundeliegende Struktur geschickt ausnutzen können. Diese Algorithmen kommen in zahlreichen Anwendungen sehr erfolgreich zum Einsatz, insb. in einigen Stufen des Planungsprozesses im Öffentlichen Verkehr (ÖV). Jüngste Forschungsergebnisse legen nahe, dass auch Mehrstufigkeit eine ausnutzbare Struktur darstellt. Die zur allgemeinen algorithmischen Umsetzung notwendige Grundlagenforschung ist Gegenstand dieses Teilprojekts.Übergeordnetes Ziel ist daher die Erforschung der Struktur mehrstufiger Optimierungsprobleme, derer Modellierung durch ganzzahlige Programme, und die Entwicklung und experimentelle Untersuchung von Dekompositionsalgorithmen zu deren exakter Lösung. Da mehrstufige Optimierungsprobleme aufgrund ihrer typischerweise langen Zeithorizonte und der Fehlerfortpflanzung entlang der zeitlichen Dimension besonders sensitiv auf Änderungen in Daten oder Restriktionen sind, soll dem Aspekt der Robustheit von Lösungen besondere Rechnung getragen werden. Prototypischer Anwendungsfall ist der Planungsprozess im ÖV, bestehend aus Liniennetz-, Fahr-, Umlauf- und Dienstplanung. An ihm soll die Praxistauglichkeit der entwickelten Theorie und Algorithmik validiert werden.

• DFG-Verfahren: Forschungsgruppen
• Teilprojekt zu: FOR 2083: Integrierte Planung im öffentlichen Verkehr