Stochastic Routing
Green Navigation ist ein prototypisches Werkzeug zur Berechnung von energie-optimalen Routen und von Reichweitenprognosen für Elektrofahrzeuge. Es basiert auf dem offenen Kartenmaterial von OpenStreetMap (OSM) und den offenen Höhenkarten des SRTM-Projekts.
Das Routing von Fahrzeuge geschieht üblicherweise durch die Lösung eines Shortest Path Problems, in dem das Straßennetz mit einem Graphen und reelwertigen Kantengewichten modelliert wird. Dies ist jedoch keine besonders realistische Annahme, weil die Kosten einer Teilstrecke von vielen, nicht genau vorhersehbaren Ereignissen wie beispielsweise Stau, Wetter und Ampelschaltungen abhängen. Um dies zu modellieren, werden Kantengewichte mit Zufallsvariablen beschrieben, die entlang eines Pfades aufsummiert werden. Dabei unterscheiden wir zwischen stochatisch unabhängigen, lokal abhängigen und global abhängigen Zufallsvariablen.
Es existieren bereits unterschiedliche Modelle für stochastisches Routing, im Rahmen dieses Projekts sollen diese zusammengetragen und implementiert werden. Dabei soll der Fokus auf verschiedenen Diskretisierungsverfahren liegen, um elementare Operationen wie die Addition von Zufallsvariablen zu realisieren.
Zielsetzung
Das Thema reicht von einer theoretischen Betrachtung (beispielsweise in der Algorithmik) über eine Analyse der Anwendungsfälle bis hin zu praktischen Entwicklungsaufgaben:
- Recherche unterschiedlicher Modelle des stochastischen Routings
- Implementierung unterschiedlicher Diskretisierungsverfahren, auch im Rahmen des am ISP entwickelten zustandsbasierten Profil-Routings
- Integration in die Routing-Algorithmen von Green Navigation
- Erweiterung des GreenNav-Frontends um Wahrscheinlichkeits-Informationen in einer für die Zielgruppe verständlichen Darstellung
- Anpassung der Datengrundlage um geeignete Felder für stochastische Information und nach Möglichkeit Integration von Stauwahrscheinlichkeiten, Ampelschaltungen und Wetterdaten.
Die Implementierungsarbeit auf der Frontend-Seite kann in Projektpraktikas ausgelagert werden, eine serverseitige Umsetzung ist jedoch notwendig für die Evaluation des gewählten Ansatzes.
Voraussetzung
Die Abschlussarbeit wird für Studierende der Informatik angeboten (andere Studiengänge sind möglich, müssen aber abgesprochen werden). Im Rahmen einer Abschlussarbeit am Projekt 'Green Navigation' wird die Zusammenarbeit mit anderen Teammitgliedern vorausgesetzt. Wir treffen uns (bisher unregelmäßig) zu Projekt-Treffen - beispielsweise Fortschrittsberichte der Projekte, Workshops zu verschiedenen Themen (z.B. wissenschaftliches Schreiben), und andere.
Wie der Titel bereits sagt, wäre ein gutes Verständis für Stochastik sinnvoll. Die Arbeit darf gerne in Zusammenarbeit mit dem Institut für Mathematik durchgeführt werden.
Kontaktperson