Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2849
Authors: Ruopp, Manuel
Title: Contraction Hierarchies für komplexe Kostenmaße
Other Titles: Contraction hierarchies for non-standard cost functions
Issue Date: 2012
metadata.ubs.publikation.typ: Abschlussarbeit (Diplom)
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-74129
http://elib.uni-stuttgart.de/handle/11682/2866
http://dx.doi.org/10.18419/opus-2849
Abstract: 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.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
DIP_3232.pdf11,97 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.