You are here

Home › Teaching › Thesis ›

Flexible and Dynamic CSPs for Routing

for Degree: 
Bachelor
Status: 
Completed

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.

Constraint Satisfaction Problems (CSPs) sind mathematische Probleme, in denen Objekte einer Menge gefunden werden müssen, die bestimmte Bedingungen (Constraints) erfüllen. In diesem Kontext heißt dynamisch, dass diese Constraints sich aufgrund der Umgebung (Environment) ändern können, im Routing könnte dies ein anderer Fahrzeugtyp oder eine andere Wetterlage bedeuten. Dagegen heißt flexibel in diesem Kontext, dass Constraints nicht unbedingt erfüllt sein müssen; stattdessen wird die Anzahl der Constraints maximiert, die erfüllt sind, oder die Constraints werden gewichtet. Dies könnte im Routing-Beispiel das Optimierungskriterium sein (statt nur die Erreichbarkeit).

Das langfristige Ziel dieses Projekts ist es, die Ideen aus dem Algorithm-Engineering im Rahmen von Constraint Problemen innerhalb von Green Navigation anwenden zu können.

Zielsetzung

  • Recherche zum Thema CSPs (dynamische und flexible), ihre Verwendung für Routing, sowie Werkzeuge und Algorithmen zur Lösung von CSPs.
  • Formulierung verschiedener Routing-Probleme als CSPs, insbesondere das energie-effiziente Routing-Problem.
  • Erweiterung oder Entwicklung eines Werkzeugs für die Lösung von CSPs spezialisiert auf Routing-Probleme.
  • Verwendung von algorithmischen Ideen zum Shortest Path Problem für mögliche Ansätze zu CSP-Lösungen.

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.

Kontaktperson