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
|
Betreuer | Funke, Prof. Stefan; Proissl, Claudius |
Eingabedatum | 15. September 2023 |
---|