Routenplanung: Kombiniertes Projekt und Seminar

Bachelor Informatik
5. Semester

Termine und Allgemeines für das Wintersemester 2023/2024

Organisation: In den ersten drei Wochen findet zu beiden oben angegebenen Zeiten nur das Seminar statt, in den verbleibenden 12 Wochen soll zu beiden oben genannten Zeiten und zu Hause an der Umsetzung des Projekts gearbeitet werden. Das Seminar dient zur Einarbeitung in das Themengebiet, es sollen Algorithmen und Datenstrukturen vorgestellt und analysiert werden, außerdem sollen Tools und API's vom Open-Street-Map-Projekt vorgestellt werden. Die Seminarausarbeitung dient auch als Projekt-Dokumentation. Im Projekt wird eine Software zur Routenplanung in C++ implementiert. Eine andere zeitliche Einteilung ist nach Absprache möglich.

Arbeitsaufwand: Sowohl das Seminar als auch das Projekt sind mit zwei Leistungspunkten (CP) in der Prüfungsordnung angegeben. Insgesamt werden also vier CP erworben, wenn das kombinierte Modul erfolgreich absolviert wird. Laut der Verordnung zur Regelung des Näheren der Studienakkreditierung in Nordrhein-Westfalen (Studienakkreditierungsverordnung - StudakVO) vom 25.01.2018, Paragraph 8 Leistungspunktesystem, Satz (1) entspricht ein Leistungspunkt einer Gesamtarbeitsleistung von 25 bis höchstens 30 Zeitstunden. Insgesamt ergibt sich also ein Arbeitsaufwand von 100 Stunden im Semester. Diese verteilen sich bei 15 Wochen Vorlesungszeit im Semester auf sechs Stunden pro Woche plus einmalig zehn Stunden zum Erstellen des Vortrags und der Seminarausarbeitung.

Inhalt

Täglich werden optimale Routen in Verkehrsnetzen berechnet. In diesem kombinierten Projekt und Seminar sollen verschiedene Teilaspekte der Routenplanung betrachtet werden. Die zu erstellende Software ist prinzipiell auch auf mobilen Geräten mit sehr begrenzter Hardware lauffähig.

Open-Street-Map  Frei verfügbare Karten, die zur Routenplanung genutzt werden können, findet man im Internet zum Beispiel bei Open-Street-Map. In diesem Projekt soll es darum gehen, solche Karten in den Computer einzulesen, aufzubereiten, Routen zu planen, diese Routen in geeigneter Form auszugeben sowie die Algorithmen und Datenstrukturen zu verstehen und zu analysieren.

External Memory Data Structures  Um die Routenplanung auch auf sehr großen Karten und auch auf Computern mit beschränkten Hardware-Ressourcen durchführen zu können, sind Datenstrukturen notwendig, die externen Speicher wie Festplatten oder SD-Karten nutzen. Da die Routenplanung effizient sein soll, ist die Software in C++ zu implementieren. Bibliotheken wie die Boost-Graph-Library oder die STxxL (Standard Template Library for Extra Large Data Sets) können und sollen in diesem Projekt genutzt werden.

Algorithmen für moderne Hardware  Moderne Hardware-Architekturen bauen auf einer Speicherhierarchie auf, die von Prozessorregistern über First-, Second- und Third-Level-Cache, RAM (also Hauptspeicher) bis zur Festplatte oder noch langsameren Massenspeichern wie Bandlaufwerken reicht. Daten werden dabei jeweils in Blöcken einer festen Größe aus nachgeordneten Speicherebenen geladen. Da die Zugriffszeiten auf die Speicherebenen jeweils um Größenordnungen auseinanderliegen können, müssen die Zugriffe möglichst effizient gestaltet werden. Das Papier What Every Programmer Should Know About Memory von Ulrich Drepper zu diesem Thema ist sehr lesenswert. Für die Intel Core i7 CPU findet man folgende Zugriffszeiten:

• 1 cycle to read a CPU register
• 4 cycles to reach L1-Cache (32 kB + 32 kB, 64 byte per line)
• 11 cycles to reach L2-Cache (256 kB, 64 byte per line)
• 39 cycles to reach L3-Cache (2 MB per core (shared), 64 byte per line)
• ≈100 cycles to reach main memory (RAM)
• ≈10.000 of cycles to reach external memory

Wir müssen also versuchen unsere Programme so zu schreiben, dass die Daten möglichst im Cache vorhanden sind, wenn wir sie benötigen. Um die Daten für kürzeste-Wege-Algorithmen Cache-effizient nutzen zu können, müssen die Knoten des Graphen z.B. mittels geo-hashing sortiert werden.

Routenplanung

Grundlage für die Routenplanung sind Graphen und Algorithmen zum Bestimmen von kürzesten Wegen. Im einfachsten Fall repräsentieren die Knoten des Graphen die Straßenkreuzungen, durch Kanten werden einzelne Straßenabschnitte modelliert. Um auch Einbahnstraßen darstellen zu können, wird unser Routenplaner auf gerichteten Graphen arbeiten. Außerdem besitzt jede Kante ein Gewicht, das die Länge des Straßenabschnitts modelliert.

Datenstrukturen  Zunächst ist eine Datenstruktur für Graphen zu implementieren, mit der das Programm zur Routenplanung arbeiten kann. Dazu kann z.B. die Boost Graph Library genutzt werden. Spezielle, für die Verwendung in Routenplanern optimierte Datenstrukturen sind bspw. in den folgenden Papieren beschrieben:

• Andrew V. Goldberg and Renato F. Werneck: Computing Point-to-Point Shortest Paths from External Memory. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, 2005
• Peter Sanders, Dominik Schultes, and Christian Vetter: Mobile Route Planning. Universität Karlsruhe, 2008

naive Implementierung  Eine sehr einfache und effiziente Datenstruktur für dünne Graphen ist eine Adjazenzliste: Header-Datei graph.hpp und die Implementierung graph.cpp. Hier noch einige Algorithmen und ein Programm zum Testen: algorithms.hpp, algorithms.cpp, testAlgo.cpp. Benötigt wird außerdem noch ein Min-Heap als Vorrangwarteschlange (Priority-Queue). Um große Karten wie die von Europa verarbeiten zu können, reicht diese Implementierung nicht aus. Dann müssen statt std::vector oder std::list Datenstrukturen der STxxL genutzt werden.

Einlesen der OSM-Daten  Die Rohdaten müssen eingelesen, aufbereitet und in die obige Datenstruktur eingefügt werden. Zunächst können mit einem Tool wie osmfilter die Daten von unnötigen Informationen wie Autor, Version, Änderungsdatum, Parkbänken, Häuser, Brunnen, Briefkästen usw. entfernt werden. Das eigentliche Kartenmaterial kann trotz der Filterung sehr umfangreich sein, zum Beispiel hat die Datei, die die Europa-Karte enthält, eine Größe von über 20 GB. Daher müssen auch beim Einlesen der Daten ggf. External-Memory-Datenstrukturen genutzt werden. Informationen zu diesem Thema findet man in dem Buch von Jeffrey Scott Vitter: Algorithms and Data Structures for External Memory. Entweder müssen solche Datenstrukturen implementiert werden oder es muss untersucht werden, ob z.B. die STxxL geeignete Datenstrukturen enthält.

Vorverarbeitung  Zur Vorverarbeitung gehört zum Beispiel, dass Pfade, deren innere Knoten vom Grad zwei sind, die also keine Kreuzung darstellen, zu einer einzigen Kante im Graphen reduziert werden, wobei die Länge der neuen Kante der Länge des Pfades entspricht. Warum? Die Laufzeit von Dijkstras Algorithmus ist:

Dabei bezeichnet T_ExtractMin bzw. T_DecreaseKey die Worst-Case-Laufzeit einer Extract-Min- bzw. Decrease-Key-Operation auf der Vorrangwarteschlange (Priority Queue). Eine Reduzierung der Anzahl 𝒱 der Knoten und der Anzahl ℰ der Kanten hat also einen großen Einfluss auf die Laufzeit, die für die Routenplanung benötigt wird.

Abbiegeinformationen  Oft ist an Kreuzungen das Abbiegen in bestimmte Richtungen nicht erlaubt, was durch verschiedene Verkehrsschilder ausgedrückt wird.

           

In OSM-Karten sind Abbiegeinformationen als Restriktionen hinterlegt. Solche Abbiegeinformationen müssen bei der Routenplanung berücksichtigt werden. Dazu ist zu überlegen, wie diese Informationen abgelegt werden können, ohne viele Ressourcen zu benötigen, und wie die Algorithmen bzw. die Graphen angepasst werden müssen. Informationen dazu finden Sie z.B. in den Vorlesungen vom KIT oder in dem Papier Customizable Contraction Hierarchies with Turn Costs der Autoren Buchhold, Wagner, Zeitz und Zündorf.

Routenplanung  Verschiedene Algorithmen zur Berechnung kürzester Wege wie Dijkstra, bidirektionaler Dijkstra, Bellman/Ford und der A^*-Algorithmus sollen implementiert und deren Laufzeiten anhand von konkreten Beispielen verglichen werden. Dabei ist die Auswirkung der External-Memory-Datenstrukturen zu untersuchen.

Darstellung der Routen  Damit die Routen auch visuell kontrolliert werden können, ist eine grafische Benutzeroberfläche zu erstellen, mittels derer auch der Start und das Ziel eingegeben werden können. Wenn die Route ermittelt wurde, ist diese Route in der Karte anzuzeigen, dazu kann bspw. die JavaScript-Library leaflet genutzt werden, außerdem steht die Overpass-API vom Open-Street-Map-Projekt zur Verfügung.

Seminarthemen

Jedes Seminarthema sollte von jeweils zwei bis vier Studierenden bearbeitet werden. Die Ausarbeitung der Themen, die allen Seminarteilnehmern zur Verfügung gestellt wird, muss so exakt sein, dass eine Definition der Schnittstellen und eine Implementierung möglich ist. Sie wird der Projekt-Dokumentation hinzugefügt. Mögliche Themen:

• Aufbau und Vorverarbeitung von Open-Street-Map-Daten mittels SAX- bzw. DOM-Parser oder OSM-Tools wie libosmium
• Visualisierung von Routen und Aufbau einer GUI mittels OSM-Tools wie leaflet und Overpass-API
• Datenstrukturen, Funktionsweise und Beschränkungen der STxxL zur Routenplanung auf Geräten mit begrenzter Hardware
• Darstellung von Graphen sowie Berechnung von kürzesten Wegen
• Berücksichtigen von Abbiegeinformationen in Graphen oder Algorithmen
• Datenorientiertes Design, Nutzen von Cache-Effekten durch Geo-Hashing
• optional: Beschleunigung der Algorithmen durch anreichern des Netzwerks mit Zusatzinformationen in einer Vorverarbeitungsphase

An diesem kombinierten Projekt und Seminar sollten nicht mehr als 20 Studierende teilnehmen.

zurück zur Startseite