Mobile Time-Dependent Route Planning

  • Subject:Routenplanung, mobile Geräte, Algorithmen für externen Speicher
  • Type:Master- oder Diplomarbeit
  • Supervisor:

    , 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