Contraction Hierarchies for State-Based Routing

Das Routing nach verschiedenen Aspekten wie Energie, Zeit oder Distanz seit längeren Forschungsgebiet mehrerer Universitäten. Dazu wurde unter anderem das mathematische Modell State-Based Routing geschaffen, das vom Routing nach einem speziellen Aspekt abstrahiert und es erlaubt, verschiedene komplexere Routing Probleme durch einfache Routing-Algorithmen zu lösen, die sonst nicht in das Schema dieser Algorithmen passen würden. Durch diese Abstraktion entsteht ein Mehraufwand für die Berechnung und damit eine höhere Laufzeit. In dieser Arbeit wird die Laufzeit durch den Einsatz von Kontraktions-Hierarchien signifikant reduziert.

Dazu wird für die einzelnen Phasen der Kontraktions-Hierarchien nicht nur gezeigt, dass diese mit dem Modell State-Based Routing kompatibel sind, sondern auch, dass auf die Rekonstuktionsphase der Kontraktions-Hierarchien durch den Einsatz von State-Based Routing verzichtet werden kann. Des Weiteren wird gezeigt, wie die Abbruchbedingung des bidirektionalen Dijkstra auf die Eigenschaften von State-Based Routing angepasst werden muss.

Die Implementierung der Kontraktions-Hierarchien am Beispiel von energieoptimalen Routing zeigt, dass die Anfragezeit gegenüber anderen energieoptimalen Algorithmen etwa um den Faktor 3,8 gesenkt werden kann.