Wöltche, AdrianAdrianWöltche0000-0002-1662-36622026-09-222026-09-222026978-3-98989-134-0978-3-98989-135-7https://fis.uni-bamberg.de/handle/uniba/116612Dissertation, Otto-Friedrich-Universität Bamberg, 2026Map matching is a widely used technology for resolving discrepancies between sequences of geocoordinates from movements and road networks. During movement, geocoordinates can be measured with the help of global navigation satellite systems. However, due to the nature of these systems, the measured geopositions contain considerable noise. Consequently, discrepancies generally occur between the measured positions and the underlying roads on which the movement originally occurred. Map matching is a combination of defined models, algorithms, and metrics for correcting these discrepancies. The goal of map matching is to find routes within the road network that most accurately represent the recorded movements. The results of map matching exactly overlap with the road network, are free from the original noise, and are corrected concerning impossible detours and gaps from the measured movements. These results facilitate further analyses in the domain of mobility research. In this thesis, we present a novel map matching method based on Markov decision processes and reinforcement learning algorithms. Our novel method introduces various advances in multiple aspects of the map matching process pipeline for increasing the accuracy of our results in comparison to existing solutions. Our process includes an improved trajectory simplification preprocessing step for improving matching performance both in terms of accuracy and speed, a novel candidate adoption feature that enables the stochastic process to dynamically resolve outliers and noise clusters, a new metric that evaluates direction changes in routes for reducing detours and round trips in the results, and finally, a new comparison algorithm that can evaluate results from different map matching solutions with varying numerical coordinate precision. Our novel map matching solution is provided as ready-to-use open source software, and we compare our solution with multiple third-party open source solutions in terms of computational speed, resource consumption, and accuracy of the results. For achieving high performance, our open source reference implementation contains several specific data structures, algorithmic customizations, and software design decisions, that we explain in context. For our extensive benchmark, we use multiple existing map matching data sets, with a mixture of ground truth and hand-corrected solutions. Furthermore, we introduce and analyze a novel open source process for generating artificial ground truth map matching data. Our evaluation demonstrates that our novel map matching method is more robust to noise and outliers than existing methods and that it outperforms them in terms of accuracy and computational performance. Our new map matching approach contains several key concepts that can be individually transferred to other solutions. Additionally, our new approach generates further ideas for future research, some of which we present in this work.Map Matching ist eine weit verbreitete Technologie zur Behebung von Diskrepanzen zwischen Geokoordinatensequenzen aus Bewegungen und Straßennetzen. Während der Bewegung können Geokoordinaten mithilfe von globalen Satellitennavigationssystemen gemessen werden. Aufgrund der Beschaffenheit dieser Systeme enthalten die gemessenen Geopositionen jedoch erhebliche Störsignale. Infolgedessen treten in der Regel Diskrepanzen zwischen den gemessenen Positionen und den zugrunde liegenden Straßen auf, auf denen die Bewegung ursprünglich stattfand. Map Matching ist eine Kombination aus definierten Modellen, Algorithmen und Metriken zur Korrektur dieser Diskrepanzen. Das Ziel von Map Matching ist es, Routen innerhalb des Straßennetzes zu finden, die die aufgezeichneten Bewegungen am genauesten wiedergeben. Die Ergebnisse des Map Matching decken sich exakt mit dem Straßennetz, sind frei von dem ursprünglichen Rauschen und wurden hinsichtlich unmöglicher Umwege und Lücken aus den gemessenen Bewegungen korrigiert. Diese Ergebnisse erleichtern weitere Analysen im Bereich der Mobilitätsforschung. In dieser Arbeit stellen wir eine neuartige Methode zum Map Matching vor, die auf Markov-Entscheidungsprozessen und Algorithmen des verstärkenden Lernens basiert. Unsere neuartige Methode führt verschiedene Verbesserungen in mehreren Aspekten des Map-Matching-Prozesses ein, um die Genauigkeit unserer Ergebnisse im Vergleich zu bestehenden Lösungen zu erhöhen. Unser Prozess umfasst einen verbesserten Vorverarbeitungsschritt zur Vereinfachung der Trajektorien, um die Matching-Leistung sowohl in Bezug auf die Genauigkeit als auch auf die Geschwindigkeit zu verbessern, eine neuartige Funktion zur Kandidatenauswahl, die es dem stochastischen Prozess ermöglicht, Ausreißer und Rauschcluster dynamisch aufzulösen, eine neue Metrik, die Richtungsänderungen in Routen bewertet, um Umwege und Rundfahrten in den Ergebnissen zu reduzieren, und schließlich einen neuen Vergleichsalgorithmus, der Ergebnisse aus verschiedenen Map-Matching-Lösungen mit unterschiedlicher numerischer Präzision der Koordinaten bewerten kann. Unsere neuartige Map-Matching-Lösung wird als gebrauchsfertige Open-Source-Software bereitgestellt und wir vergleichen unsere Lösung mit mehreren Open-Source-Lösungen von Drittanbietern hinsichtlich Rechengeschwindigkeit, Ressourcenverbrauch und Genauigkeit der Ergebnisse. Um eine hohe Leistung zu erzielen, enthält unsere Open-Source Referenzimplementierung mehrere spezifische Datenstrukturen, algorithmische Anpassungen und Software-Design-Entscheidungen, die wir im jeweiligen Kontext erläutern. Für unseren umfangreichen Benchmark verwenden wir mehrere vorhandene Map-Matching-Datensätze, die eine Mischung aus Ground-Truth und handkorrigierten Lösungen enthalten. Darüber hinaus stellen wir einen neuartigen Open-Source-Prozess zur Generierung künstlicher Ground-Truth-Map-Matching-Daten vor und analysieren diesen. Unsere Evaluation zeigt, dass unsere neuartige Map-Matching-Methode robuster gegenüber Rauschen und Ausreißern ist als bestehende Methoden und diese in Bezug auf Genauigkeit und Rechenleistung übertrifft. Unser neuer Map-Matching-Ansatz umfasst mehrere Schlüsselkonzepte, die einzeln auf andere Lösungen übertragen werden können. Darüber hinaus liefert unser neuer Ansatz weitere Ideen für die zukünftige Forschung, von denen wir einige in dieser Arbeit vorstellen.engmap matchingopen sourcebenchmarkgeographic information sciencemarkov decision processreinforcement learning004doctoralthesisurn:nbn:de:bvb:473-irb-116612x