Bachelor Thesis BCLR-2023-32

BibliographyBreckner, Jannik: Contraction Hierarchies mit Abbiegekosten.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 32 (2023).
58 pages, german.
Abstract

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.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Prof. Stefan; Proissl, Claudius
Entry dateSeptember 15, 2023
New Report   New Article   New Monograph   Computer Science