conference logo

Playlist "FOSSGIS 2022"

Map-Matching at Scale: Open-Source und (fast) kostenloses Map-Matching für Millionen von Trajektorien

Siavash Saki

In diesem Vortrag geht es um eine Open-Source-Alternative zu kostenpflichtigen APIs für den Map-Matching und darum, wie diese für den Map-Matching großer Datensätze genutzt werden kann. Konkret wird eine einfache Cloud-basierte Lösung vorgeschlagen, die die Open-Source-Routing-Engine Valhalla und OpenStreetMap-Daten für das Map-Matching von Millionen von Trajektorien nutzt. Die Effizienz der vorgeschlagenen Architektur wird anhand von Beispielen untersucht.

Beim Map-Matching werden die wahren Positionen aufgezeichneter GPS-Koordinaten einer Trajektorie auf einem digitalen Modell des Straßennetzes geschätzt. Dies ist ein wesentlicher Schritt bei der Vorverarbeitung von GPS-Daten. Er spielt eine entscheidende Rolle bei der Verringerung von Datenunsicherheiten und Standortfehlern, indem er die beste Übereinstimmung der GPS-Punkte mit dem Straßen-Graph findet. Derzeit gibt es viele Kartendienstanbieter, die Map-Matching anbieten. Diese sind jedoch kostenpflichtigspielig und nicht für das Map-Matching großer Datenmengen optimiert, z. B. wenn es sich um historische Floating Car Data handelt. Zudem können sie bzgl. der Anzahl der Wegpunkte pro Trajektorie begrenzt sein (z.B. 100 Punkte bei Google Maps).
Eine andere Möglichkeit, das Problem des Map-Matchings großer Datensätze zu lösen, ist der Aufbau eines eigenen Map-Matching-Servers. Diese Lösung bietet die Möglichkeit des Map-Matching einer beliebigen Anzahl von Trajektorien. Diese Präsentation zeigt, wie ein Open-Source-Routing-Server aufgebaut werden kann und wie das Map-Matching-Modul in Verbindung mit PostGIS verwendet werden kann, um eine Produktionslösung für das Map-Matching von Trajektorien zu entwickeln. Hier wird Valhalla eine Open-Source-Routing-Engine sowie dazugehörige Bibliotheken für die Verarbeitung von OpenStreetMap-Daten verwendet.
Der Aufbau des Vortrags gliedert sich wie folgt: Zunächst wird erklärt und anhand realer Beispiele demonstriert, warum Map-Matching notwendig ist, bevor man sich mit der Datenanalyse beschäftigt.
Derauf folgt eine kurze Einführung in die Methoden des Map-Matchings und es wird erklärt, wie hier der Hidden Markov Model-Ansatz angewendet wird. Nach einer vergleichenden Darstellung mehrere gängige Map-Matching-Dienstleister und ihre API-Einschränkungen und Kosten wird die hier genutzte Open-Source-Lösung vorgestellt. Es handelt sich um eine einfache Lösungsarchitektur in der AWS-Cloud für das Map-Matching von Millionen von Trajektorien und Milliarden von GPS-Punkten. Es wird gezeigt, wie Valhalla auf einem Cloud-Server aufgebaut werden kann und Straßennetzdaten aus OSM in diesen importiert werden können. Die vorverarbeiteten und in einer PostGIS-Datenbank gespeicherten Trajektorien werden in den Routing-Server eingespeist. Nach dem Map-Matching werden sie zurück in die PostGIS-Datenbank geschrieben oder direkt an die Datenanalyse-Pipeline weitergeleitet. Schließlich wird die Leistung des Map-Matching anhand einiger Beispiele mit „Echtdaten“ untersucht. Der Vortrag endet mit Empfehlungen für Entwickler*innen, die Map-Matching einsetzen möchten.