, 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 oder einem aktuelleren Verfahren 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, den sogenannten Reisezeitfunktionen.

Thema der Arbeit

In der zeitabhängigen Routenplanung benötigen die Reisezeitfunktionen sehr viel Speicherplatz. Insbesondere für die Verwendung auf Mobilgeräten wie z.B. Smartphones ist dies ziemlich ärgerlich, da auf diese Weise sehr viele Zugriffe auf den langsamen Flashspeicher anfallen. Der Platzbedarf soll daher so weit wie möglich reduziert werden. Ziel dieser Arbeit ist es deshalb, eine auf Bitebene kodierte und komprimierte Datenstruktur zu entwickeln, die einerseits möglichst platzeffizient ist, andererseits aber auch eine möglichst zeiteffiziente Auswertung der dargestellten Fuktionen ermöglicht.

Vorraussetzungen

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

Gebotenes

• Sammeln von Erfahrungen in maschienennaher Programmierung
• Kennenlernen moderner 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.