Algorithmen zur Lösung zeitabhängiger Routing-Probleme mit exponentieller Ausgabegröße

• Antragsteller: Professor Dr. Martin Skutella
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 255184784

Im vergangenen Jahrzehnt hat bei Routing-Problemen in diversen Transportnetzen eine dramatische Explosion des Datenvolumens stattgefunden. Dieses Phänomen hat unterschiedliche Ursachen, unter anderem die gewachsene Nachfrage nach Modellen und Lösungen, die auch die zeitliche Dynamik des Flusses in Transportnetzen berücksichtigen. Prominente Beispiele sind Routenplaner in Verkehrsnetzen, Evakuierungsplanung für große Bezirke oder ganze Großstädte, sowie Planungsprobleme in riesigen Logistiknetzen.Im Bereich der effizienten Algorithmen und in der mathematischen Optimierung wurden in den vergangenen 50-60 Jahren schnelle Methoden zur Lösung statischer (d.h. nicht zeitabhängiger) Routingprobleme entwickelt. Im Gegensatz dazu wurde der Erforschung dynamischer Routing-Probleme deutlich weniger Beachtung geschenkt. Das vorliegende Projekt behandelt grundlegende Fragestellungen im Bereich der dynamischen Netzwerkflüsse und zeitexpandierten Netze, die ein geeignetes Werkzeug zur Modellierung und Lösung zeitabhängiger Routing-Probleme darstellen. Besonderer Wert wird dabei auf sogenannte Earliest-Arrival-Flüsse gelegt, die von grundlegender Bedeutung für Evakuierungsprobleme sind.Ein interessantes Artefakt dynamischer Flussprobleme besteht darin, dass statische (also kleine) Eingabedaten dynamische (also große) Ausgabedaten erzeugen. Die wahre Schwierigkeit derartiger Probleme, bei denen die Kodierungslänge der Lösung exponentiell in der Eingabegröße ist, wird von der traditionellen Komplexitätstheorie kaum erfasst. Weitere prominente Beispiele findet man in der parametrischen Optimierung, der Mehrkriteriellen Optimierung und bei Aufzählproblemen. Zusätzlich zum eigentlichen Schwerpunkt dieses Projekts, dem zeitabhängigen Routing, zielen wir auf einer grundlegenderen Ebene auf ein besseres Verständnis der Komplexität von Problemen und Algorithmen mit exponentieller Ausgabegröße.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1736: Algorithmen für große Datenmengen