, J. Speck

Zeitabhängige Routenplanung in Straßennetzen

In der Routenplanung werden Straßennetze durch gewichtete Graphen repräsentiert, z.B. mit der Fahrzeit als Kantengewicht. Mit Dijkstras Algorithmus kann nun eine optimale Route berechnet werden. In der Realität können Fahrzeit und optimale Route jedoch auch von der Zeit abhängen. Z.B. sind viele Straßen während der Rushhour stärker belastet, was zu deutlich längeren Fahrzeiten führen kann. Um dies zu modellieren, ersetzt man die konstanten Kantengewichte nun durch Funktionen. Zur Routenberechnung kann man dann eine zeitabhängige Variante von Dijk\-stras Algorithmus verwenden.

Für realistische Problemgrößen ist der zeitabhängige Dijkstra-Algorithmus viel zu langsam. Mit aktuellen algorithmischen Methoden, wie z.B. den zeitabhängigen Contraction Hierarchies erreicht man gegenüber Dijkstras Algorithmus eine mehr als 1000-mal kürzere Rechenzeit.

Thema der Arbeit

Ziel der Arbeit ist die Anpassung der zeitabhängigen Contraction Hierarchies an die Erfordernisse von mobilen Geräten, was auch die Implementierung für ein Smartphone beinhaltet. Da mobile Geräte über recht wenig Hauptspeicher verfügen, müssen die Algorithmen auf den deutliche langsameren Flashspeicher des Smartphones zugreifen. Da diese Zugriffe den Flaschenhals der Berechung darstellen, geht es darum, die Anzahl der Zugriffe durch geschickte Kodierung und Kompression auf Bitebene zu reduzieren.

Vorraussetzungen

• Interesse an Algorithmen und Datenstrukturen sowie solide Kentnisse auf diesen Gebieten
• Gute Programmierkentnisse in C++

Gebotenes

• Sammeln von Erfahrungen in der Programmierung mobiler Geräte
• Kennenlernen modernster Algorithmen zur Routenberechnung
• Mitarbeit an einem echten Forschungsthema in einer auf diesem Gebiet führenden Forschungsgruppe

Weitere Informationen

Bei Interesse bitte bei oder Jochen Speck melden