Algorithm Engineering für Routenplanung

• Applicants: Professor Dr. Peter Sanders; Professorin Dr. Dorothea Wagner
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 67847980

Im Mittelpunkt des Projekts stehen Algorithmen zur sehr schnellen Berechnung kürzester Wege in sehr großen Graphen. Dabei wollen wir uns an Szenarien orientieren, die bei der Routenplanung im Straßenverkehr oder der Fahrplanauskunft in öffentlichen Verkehrssystemen auftreten. Die meisten unserer Ziele sind motiviert durch die Vision des „zukünftigen Routenplaners“, d.h. eines komfortablen, mobilen hybriden Routenplaners mit dezentralen und zentralen Komponenten. Routenplaner müssen in der Lage sein, im Bruchteil einer Sekunde eine optimale Route oder Zugverbindung (bezüglich Fahrzeit oder Distanz oder auch anderer Kriterien) zu ermitteln, wobei vorberechnete Information ausgenutzt werden kann. In der Praxis werden heutzutage meist heuristische Verfahren eingesetzt, die zwar schnell eine Route berechnen, deren Optimalität aber nicht garantiert werden kann. Weitergehende Anforderungen wie die schnelle Aktualisierung bei veränderter Verkehrssituation oder Verspätungen, die Berücksichtigung von Zeitabhängigkeit, mehreren Kriterien oder Nebenbedingungen werden kaum oder gar nicht unterstützt. Ausgangspunkt für die schnelle Berechnung kürzester Wege in Graphen ist der klassische Algorithmus von Dijkstra. Ziel des Projekts ist der Entwurf, die theoretische Analyse sowie die Implementierung und experimentelle Bewertung von Algorithmen zur Berechnung kürzester Wege, insbesondere von Beschleunigungstechniken für den Algorithmus von Dijkstra. Dabei soll der Fokus einerseits auf zeitabhängigen und dynamischen Szenarien, andererseits auf der Berücksichtigung von Nebenbedingungen und auf mehreren Optimierungskriterien liegen.

• DFG Programme: Research Grants