Effiziente Algorithmen für wegbasierte und dynamische Flussprobleme in großen Netzwerken

• Antragsteller: Professor Dr. Rolf H. Möhring; Professor Dr. Martin Skutella
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2007
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5322708

Effiziente Algorithmen für Flussprobleme sind von entscheidender Bedeutung für eine Vielzahl netzbasierter Anwendungen, etwa bei der Verkehrsführung und -planung, der Telekommunikation und dem Datenverkehr im Internet. Wichtiges Leitthema solcher Anwendungen ist - im weitesten Sinne - die Minimierung der Netzbelastung bei (weitgehender) Erfüllung aller vorhandenen Nutzerwünsche. Diese Thematik führt zu Optimierungsproblemen in Netzen, die bisher meist traditionell mit Standardverfahren der Netzwerkoptimierung behandelt werden. Diese Verfahren lassen jedoch wesentliche Aspekte außer Acht, die gerade in komplexen und großen Netzen von Bedeutung sind: Netze sind i.a. nur noch implizit gegeben und beliebige Flussführungen sind nicht mehr zulässig. In diesem Projekt sollen Algorithmen zur Behandlung solcher "wegbasierter" Fluss- bzw. Mehrgüterflussprobleme entwickelt und erprobt werden. Hierzu muss insbesondere in theoretischer Hinsicht Neuland betreten werden, da zugleich neue, aus der Wegbasierung resultierende Nebenbedingungen und die Forderung nach Effizienz auf großen Netzen berücksichtigt werden müssen. In praktischer Hinsicht bilden Fragen der optimalen Verkehrsführung den Anwendungshintergrund, wobei hierfür auch große Netze als Praxisdaten zur Verfügung stehen.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke