Evaluation von Strategien für die Konstruktion von Contraction Hierarchies

Abstract

Eine altbewährte Lösung des shortest-path-problem liefert der Dijkstra-Algorithmus. In den vergangenen 20 Jahren wurden dennoch diverse Techniken zur Verbesserung der Effizienz entwickelt. Eine dieser Techniken stellen die Contraction Hierarchies dar, welche auf einer Vorverarbeitung des Graphen basieren. Auf sehr dichten Graphen, beispielsweise bei realen Straßennetzwerken, stellte sich der Dijkstra als ineffizient heraus. Mithilfe dieser Voerverarbeitungstechnik Contraction Hierarchie kann eine Suchanfrage um ein Vielfaches schneller beantwortet. Eine weitere bekannte Technik, zur Verschnellerung solcher Anfragen, stellen Hub-Labels dar. Es kann dadurch ein Distanzorakel aufgebaut werden, sodass die Antwortzeit auf eine kürzeste Distanzanfrage im Bereich weniger Mikrosekunden liegt. Die vorliegende Bachelorarbeit stellt verschiedene Strategien zur Erstellung einer Contraction Hierarchie vor und bemisst ihre Qualität an der Menge der berechneten Hub-Labels. In einem experimentellen Vergleich, wurden verschiedene Strategien vorgestellt, evaluiert und miteinander verglichen. Dabei wurde der ”Tradeoff”zwischen der Berechnungszeit und der gemessenen Qualität ebenfalls berücksichtigt.