Diplomarbeit (Nr. 3232)

Contraction Hierarchies für komplexe Kostenmaße

Manuel Ruopp

Die Routenplanung ist ein erheblicher Bestandteil im alltäglichen Leben. Es können Kosten beim gewerblichen Transport von Waren oder Zeit bei privaten Reisen eingespart werden. Über die letzten Jahre sind immer mehr mobile Geräte -- vor allem Smartphones -- in alltäglicher Benutzung. Daher liegt es nahe, die Routenplanungsalgorithmen speziell für mobile Geräte zu optimieren. Dabei spielen die Geschwindigkeit, der Stromverbrauch (Rechenaufwand, Speicherzugriffe) und der beschränkte Speicherplatz eine bedeutende Rolle. In letzter Zeit wurde dafür als Grundlage oft das Contraction Hierarchy Verfahren in der Forschung verwendet.

Contraction Hierarchies ermöglichen eine schnelle Routenberechnung in Graphen. Die Graphen werden bei diesem Verfahren in einer Vorbereitungsphase um eine Hierarchie erweitert. Der Graph kann nun aber nachträglich nur noch mit großem Aufwand verändert werden. Es lohnt sich daher nur, wenn viele Routen auf einem gleichbleibenden Graphen berechnet werden sollen. Der Speicherplatzverbrauch ist niedrig, da sich nur die Kantenanzahl des Graphen in der Vorbereitungsphase in etwa verdoppelt.

Diese Arbeit erweitert das Contraction Hierarchy Verfahren um komplexe Kostenmaße für die Berechnung von kürzesten Wegen. Dabei haben wir zwei voneinander getrennte Zielsetzungen. Als Erstes wird versucht, verschiedene Metriken für die Kantengewichte des Graphen in einer einzigen Hierarchie zu vereinen. Damit könnten verschiedene Kantengewichte für unterschiedliche Fahrzeugstypen, wie zum Beispiel PKW und Fahrrad in einem Graphen modelliert werden. Und als Zweites werden die Kantengewichte durch Gewichtsfunktionen ersetzt. So lassen sich zeitliche Bedingungen modellieren: zum Beispiel ist zur Mittagszeit auf dieser Straße immer Stau, und deshalb wird für diese Strecke das Vierfache der Zeit benötigt.