ISBN 9783843943871

978-3-8439-4387-1, Reihe Informatik

Maximilian Barta
Transformation von Straßennetzgraphen mittels Data Science Methoden für multikriterielle Routenalgorithmen

231 Seiten, Dissertation Bergische Universität Wuppertal (2020), Hardcover, B5

Zusammenfassung / Abstract

In dieser Arbeit wird ein System entwickelt, mit dem Graphendaten von Straßennetzen so modifiziert werden, dass automatisch bestimmte Orte von Interesse identifiziert und kategorisiert werden und gleichzeitig dazu verwendet werden können, Routen mit mehr als einem Eingabeparameter zu berechnen.

Hierzu werden Algorithmen zur Berechnung von kürzesten Pfaden zwischen zwei Punkten in Graphen um eine dynamische Gewichtungsfunktion erweitert, die es erlaubt, mit den modifizierten Graphendaten Routen zu erzeugen, die mit mehr als einem Gewichtungsparameter berechnet werden.

Der Hauptteil der Arbeit beschäftigt sich mit der Modifikation des zugrunde liegenden Geo-Datensatzes, sowie der Modifikation des Algorithmus von Dijkstra, bzw. des A*-Algorithmus, exemplarisch für alle Algorithmen, die den kürzesten Pfad in einem Graphen zwischen zwei Punkten mittels Kantengewichten berechnen.

Außerdem wird die Implementierung in ein praxistaugliches System erläutert.

Neben der Vorstellung der Architektur des Systems und den entwickelten Kommunikationsprotokollen, werden die einzelnen Module näher diskutiert und Optimierungen an den verwendeten Algorithmen und Datenstrukturen, zur Verbesserung der Laufzeit und Skalierbarkeit, aufgezeigt.

Der Teilbereich der Identifizierung und Kategorisierung von Orten von Interesse wird mit einem Vergleich zu bestehenden Mechanismen verifiziert.

Der Teilbereich zur Berechnung von Routen mit mehreren Eingangsparametern wird mittels Doppel-Blind-Test verifiziert.

Abgeschlossen wird die Arbeit mit einer Zusammenfassung und einem Ausblick für Verbesserungen und Erweiterungen für das entwickelte System, sowie weiteren möglichen Einsatzszenarien.