Vorberechnungstechniken in der Punkt-zu-Punkt-Kürzeste-Wege-Suche

• Stipendienempfänger: Tobias Columbus
• Projekt: »Vorberechnungstechniken in der Punkt-zu-Punkt-Kürzeste-Wege-Suche «

Projektbeschreibung

Die Frage nach dem kürzesten Weg zwischen zwei gegebenen Punkten in einem Straßennetzwerk, ist eines der klassischen Probleme der Informatik, welches bereits 1959 von Edsgar Dijkstra studiert und teilweise gelöst wurde. Das von Dijkstra entwickelte Verfahren ist zwar theoretisch zufriedenstellend, jedoch in manchen Anwendungen, wie zum Beispiel der Routenplanung, nicht performant genug. In der Praxis kommen deshalb oftmals Heuristiken zum Einsatz, die zwar mehr als beeindruckende Ergebnisse erzielen, deren Erfolg man sich aber nur teilweise oder unzureichend erklären kann. Insbesondere gab es zu Beginn meiner Arbeiten auf diesem Gebiet kaum theoretische Resultate, die tatsächlich belegen, dass diese Heuristiken besser, d.h. schneller, als die klassische Lösung von Dijkstra sind.

Während der Förderung durch die Begabtenstiftung Informatik habe ich aufbauend auf meiner Studienarbeit eine solche Vorberechnungstechnik, sogenannte Contraction Hierarchies, genauer unter die Lupe genommen und versucht eine theoretische Erklärung für die Performanz dieses Verfahrens zu finden. Für bestimmte Arten von Netzwerken konnte dieses Ziel teilweise erreicht werden, indem ich ein theoretisches Modell von Contraction Hierarchies entwickelt und mit einem älteren Problem, welches bereits eingehend studiert wurde, verglichen habe. Auf diesem Weg konnte ich zeigen, dass die Berechnung von kürzesten Wegen in Contraction Hierarchies tatsächlich weniger Knoten, d.h. Straßenkreuzungen, berücksichtigt als Dijkstra's Algorithmus. Während der Förderung durch die Begabtenstiftung Informatik habe ich diese Resultate für einige Beispiele und eingeschränkte Klassen von Netzwerken bewiesen und danach im Rahmen meiner Diplomarbeit weiter ausgebaut und verallgemeinert. Leider konnten und können diese Resultate momentan noch nicht in obere Schranken für die tatsächliche Laufzeit des Verfahrens übersetzt werden.
Ein Teil dieser Ergebnisse erschien auch als Konferenzbeitrag "Search Space Size in Contraction Hierarchies" auf der Konferenz ICALP2013. Dieser Artikel kann als Endergebnis des von der Begabtenstiftung geförderten Projektes gewertet werden.

Zur Person

• 2012 Abschluss des Informatikstudiums (Diplom)
• 2012 - heute Promotion am Institut für Algebra und Geometrie