Android-Offline-Routenplaner mit Contraction Hierarchies

Abstract

Contraction Hierarchies sind ein Ansatz zur Optimierung von Pfadsuch-Algorithmen, bei welcher eine Graphstruktur um zusätzliche Elemente erweitert wird. Inhalt dieser Arbeit ist die Implementierung einer Android-App zur Berechnung kürzester Pfade auf Teilgraphen unter Verwendung ebensolcher Contraction Hierarchies. Dabei wird unter anderem der Prozess der Extraktion eines Teilgraphen von einem um Contraction Hierarchies erweiterten Graphen auf potentielle Probleme untersucht. Die dabei entdeckten Probleme der Pfadkorrektheit und der Gewährleistung der Absenz ungültiger Kanten werden auf ihre Ursache analysiert und mögliche Lösungsansätze formuliert. Dem folgt eine Dokumentation der Umsetzung der Lösungsansätze in der implementieren Software. Ebenfalls Teil der Arbeit ist eine Untersuchung der Effizienz von einem für Contraction Hierarchies modifizierten Dijkstra-Algorithmus gegenüber einem unmodifizierten Dijkstra. Anhand der Messungen ergab sich eine signifikante Optimierung der Laufzeit des Algorithmus, wenn Contraction Hierarchies zum Einsatz kommen.