Oskar Besler:
Vergleich von kernbasierten Routing-Algorithmen in Straßennetzwerken
Kurzbeschreibung
Hintergrund: Das effiziente Finden eines kürzesten Pfades in einem Straßennetzwerk zwischen zwei Positionen ist eine wichtige Aufgabe für Echtzeitanwendungen wie Navigationssysteme, um flexibel auf dynamische Veränderungen im Straßennetzwerk, wie Änderungen von Start- und Endpositionen, reagieren zu können. In der Literatur gilt der Highway-Hierarchies-Star-Algorithmus als einer der effizientesten Algorithmen zur Ermittlung des kürzesten Pfades zwischen zwei Knoten in einem Straßennetzwerk.
Ziele: In dieser Arbeit soll überprüft werden, ob der Highway-Hierarchies-Star-Algorithmus tatsächlich effizienter ist als verschiedene etablierte Algorithmen zum Finden des kürzesten Pfades, wie in der Literatur beschrieben. Methoden: Dafür werden verschiedene Algorithmen zur Berechnung des kürzesten Pfades implementiert und anhand unterschiedlicher Suchanfragen in deutschen Straßennetzwerken bewertet.
Ergebnisse: Die Experimente zeigen, dass der Highway-Hierarchies-Star-Algorithmus die besten Ergebnisse bei den Suchanfragen erzielt und dabei auch eine annehmbare Vorverarbeitungszeit aufweist.
Schlussfolgerungen: Der Highway-Hierarchies-Star-Algorithmus bietet schnelle Anfragezeiten in statischen Graphen, sodass verschiedene Anfragen mit unterschiedlichen Start- und Endpositionen in Millisekunden berechnet werden können. Dies bestätigt weitgehend die Bewertung in der Literatur. Dennoch sind weitere Tests auf dynamischen Graphen erforderlich, um eine komplette Beurteilung vornehmen zu können.