[Mittagsseminar TI] Mittagsseminar am Dienstag, 24.10.2023

[Günter Rote <rote@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der Theoretischen Informatik der
FU Berlin spricht am

   Dienstag, 24.10.2023, 12:00 Uhr, SR 051, Takustraße 9
   Oskar Besler
   zum Thema: Vergleich von kernbasierten Routing-Algorithmen
   in Straßennetzwerken (B.Sc.-Verteidigung, auf Deutsch/in German)

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.