Berechnung von simplen Routen für Routen-Skizzen

Studienarbeit / Bachelorarbeit

Das Finden von kürzesten Wegen in Straßennetzwerken ist in der Algorithmentechnik ein sehr aktiver Bereich. Online-Dienste wie zum Beispiel Google Maps oder Maps24 bieten die Möglichkeit Routen zu berechnen und anzeigen zu lassen. Typischerweise wird dabei eine grobe Übersichtskarte angezeigt die mit Hilfe von textuellen Beschreibungen den genauen Routenverlauf erläutert. Solch eine Darstellung ist nicht immer optimal da einerseits, auf der groben Übersichtskarte die Details um Start- und Zielregion oft nur schwer zu erkennen sind und andererseits, weil die textuelle Beschreibung nicht in der Lage ist einen groben Überblick zu vermitteln. Eine gute Alternative sind handgefertigte Routen-Skizzen die sowohl kleine Details der Strecke darstellen als auch einen groben Überblick vermitteln können.

Google Maps Karlsruhe - Konstanz

Handgefertige Skizze der Strecke Karlsruhe - Konstanz

Automatisch generierte Routen-Skizze

Das automatische Generieren von Routen-Skizzen ist ein aktueller Forschungsbereich mit einer praktischen Anwendung. Aktuelle Verfahren beruhen aber auf der Annahme, dass der Fahrer immer die tatsächlich schnellste Route fahren will. Das widerspricht der Intuition hinter Routen-Skizzen die vor allem eine einfache Darstellung der Route im Blickpunkt haben. Eine einfache Darstellung von Routen wird vor allem dadurch begünstigt, dass eine Route selbst einfach ist. Im Rahmen dieser Studienarbeit soll ein Verfahren entwickelt werden welches eine Route berechnet, die vor allem einfach ist aber dabei nicht zu große Umwege produziert. Diese Anforderung unterscheidet diese Arbeit zu bereits bestehenden Untersuchungen zu simplen Routen [1,2].

Kürzeste Route [Google Maps]

Simple Route [Google Maps]

Grob strukturiert besteht die Studienarbeit aus zwei Schritten. Zunächst muss eine sinnvolle Modellierung für die Berechnung von simplen Routen gefunden werden. Anschließend soll die Modellierung implementiert und experimentell evaluiert werden.

Studienarbeit/Bachelorarbeit

Ziel ist es eine Modellierung für die Berechnung von simplem Routen zu erstellen. Diesen Ansatz dann zu implementieren, und anschließend experimentell zu evaluieren.

• Fundierte algorithmische Kenntnisse
• Kenntnis einer Programmiersprache wie Java oder C/C++ hilfreich, aber nicht zwingend notwendig.

Dr. Andreas Gemsa, PD Dr. Martin Nöllenburg

[1] Duckham, M. and Kulik, L. (2003) „Simplest Paths“: Automated route selection for navigation. In Kuhn, W., Worboys, M. and Timpf, S. (eds) Lecture Notes in Computer Science 2825, Springer, pp. 169-185

[2] Richter, K-F. and Duckham, M. (2008) Simplest Instructions: Finding Easy-to-Describe Routes for Navigation. In Cova, T., Beard, K, Goodchild, M., and Frank, A.U., editors, Lecture Notes in Computer Science 5266 (GIScience 2008), pp. 274-289. Springer, Berlin