Bachelorarbeit BCLR-2023-32

Bibliograph.
Daten
Breckner, Jannik: Contraction Hierarchies mit Abbiegekosten.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 32 (2023).
58 Seiten, deutsch.
Kurzfassung

Herkömmliche Routenplanung im Straßenverkehr basiert auf gerichteten Graphen und ordnet einer Straße das Gewicht zu, welches zum Passieren benötigt wird. Es werden daher keine Abbiegekosten berücksichtigt. Für diese Arbeit wurden Graphen mit Abbiegekosten aus realen Daten von OpenStreetMap extrahiert. Anschließend wurden Verfahren betrachtet und implementiert, um Abbiegkosten für Contraction Hierarchies zu verwenden, im Folgenden TCH (Turn-CH) genannt. Da Contraction Hierarchies nicht für Routenberechnung mit Abbiegekosten gedacht sind, mussten Modifizierungen vorgenommen werden. Es konnte eine Verbesserung der Anfragezeit von ca. 5000 im Vergleich zum Turn-Dijkstra erreicht werden. Die implementierten TCHs sind bezüglich der Anfragezeit aber nur ungefähr gleich schnell zu den Anfragen an eine Contraction Hierarchie des Kantengraphes. Der benötigte Speicherplatz wird im Vergleich zu diesen um den Faktor 2 reduziert.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
BetreuerFunke, Prof. Stefan; Proissl, Claudius
Eingabedatum15. September 2023
   Publ. Informatik