Aktuelles

Nächste Seminare

RoutePlanning@KIT, Der gläserne Routenplaner

Was leistet der gläserne Routenplaner?

Noch vor 10 Jahren ermittelte man die beste Strecke von A nach B am PC zu Hause per Routenplaner-Software. Während die Berechnung damals stets einige Zeit dauerte, kann die optimale Route heute in Sekundenbruchteilen uber das Internet berechnet werden, obwohl dort zigtausende Anfragen gleichzeitig bearbeitet werden.

Das liegt nicht nur an der enorm gestiegenen Rechenleistung, sondern auch an der Entwicklung neuer Verfahren zur Berechnung optimaler Wege. So werden die Basisdaten etwa um nüzliche Informationen für alle späteren Suchanfragen angereichert. Denn wer z.B. von Hamburg zum Oktoberfest nach München fährt, benötigt keine Informationen über Straßen in Frankfurts Innenstadt.

Moderne Routenplanungsverfahren sind also schneller, wenn sie gezielt alle für die Anfrage unwichtigen Straßen ausschließen. Der gläserne Routenplaner ermöglicht es, diesen Verfahren bei der Arbeit zuzuschauen.

Die folgenden Bilder zeigen die Suchräume einer Wegesuche innerhalb in Karlsruhe unter Verwendung unterschiedlicher Algorithmen. Der Routenplaner erlaubt es, den Ablauf der Suche und die Entwicklung der Suchräume interaktiv zu visualisieren.

Suchraum des Dijkstra-Algorithmus
Suchraum bidirektionaler Dijkstra
Suchraum des Landmark-Verfahrens von Goldberg et al.
Suchraum des Arcflag-Algorithmus von Möhring et al.

Wer entwickelt den gläsernen Routenplanar?

Der Routenplaner wurde im Rahmen des Projekts Entwicklung eines Frameworks zur Demonstration von Routenplanungsalgorithmen entwickelt. Die Entwicklung wurde aus Mitteln des Kompetenzbereichs Information, Kommunikation und Organisation des KIT finanziell gefördert. Der Gesamt-Entwicklungsaufwand betrug ca. 1500 Mann-Stunden.

Projektteilnehmer

Wissenschaftliche Hilfskräfte:

  • Sebastian Bayer
  • Roland Kluge
  • Alexander Kohl
  • Sebastian Meßmer

Betreuer:

Weitere Informationen

Die grundlegenden Funktionen und theoretischen Grundlagen sind auf einem Poster dargestellt. Ein zweites Poster bietet eine detaillierte Übersicht über eine Reihe von Speedup-Techniken sowie eine Zeitlinie.