Anwendung von Contraction Hierarchies und Hierarchical Hub-Labeling auf Geometrischen Graphen

Abstract

Während Contraction Hierarchies (CH) auf Straßengraphen erfolgreich eingesetzt werden und hohe Speedups bei der Berechnung von kürzesten Pfaden ermöglichen, ist ihre Anwendung auf große Sichtbarkeitsgraphen in angemessener Zeit nicht möglich. Da bisher keine Contraction Hierarchies für die bearbeiteten Sichtbarkeitsgraphen erstellt werden konnten, war auch die Erzeugung von Hierarchical Hub Labelings (HHL) nicht realisierbar. Diese Arbeit untersucht die Hindernisse bei der Anwendung von Contraction Hierarchies auf Sichtbarkeitsgraphen und prüft, ob sich die Kontraktion durch den Einsatz von Heuristiken anstelle der Witness-Suche beschleunigen lässt. Trotz der Anwendung dieser Heuristiken konnten die Sichtbarkeitsgraphen nicht kontrahiert werden. Basierend auf bestehenden Charakterisierungen werden mit PEOPLE und CH-PEOPLE (PrEdetermined Order, Pruned Label) zwei Algorithmen vorgestellt, die es ermöglichen, ohne Kontraktion sowohl Hierarchical Hub Labelings als auch die für CH-Anfragen benötigte Datenstruktur zu erstellen. Beide Algorithmen sind trivial parallelisierbar und wurden erfolgreich auf die bearbeiteten Sichtbarkeitsgraphen angewendet. Während CH-Anfragen nur einen geringen Speedup erzielten, zeigte sich bei HHL-Anfragen ein deutlicher Performance-Gewinn. Zudem war die durchschnittliche Labelgröße der Sichtbarkeitsgraphen vergleichbar mit ihrem durchschnittlichen Knotengrad.