Analyzing Crowd-Sourced Trajectories to Infer Routing Preferences of Cyclists

Abstract

In the last decade, the activities of many volunteers have resulted in almost complete representations of street networks and large sets of trajectories. The latter have primarily been collected by recreational sportspeople who, for example, have recorded bicycle tours or hikes with Global Navigation Satellite System (GNSS) receivers. This new source of geospatial data collected within the realm of Volunteered Geographic Information (VGI) contributed to the rise of trajectory data mining methods that analyze movement based on historical movement data. <br /> Using crowd-sourced data has multiple benefits due to its availability and volume, particularly in domains where administrative data is scarce. Moreover, VGI data is mainly collected by local users. This local perspective is advantageous when using the data to gain insights into user behavior, as the data can be assumed to reflect the users' views. However, working with VGI data presents challenges due to its high heterogeneity. This heterogeneity occurs in different aspects of the data, resulting in four main challenges: (1) unknown spatial accuracy, (2) lack of metadata, (3) participation bias, and (4) ethics in data usage. <br /> This thesis contributes to the analysis of crowd-sourced trajectory data by presenting a methodic pipeline for inferring the users' routing preferences from their past movements. The pipeline is structured into preprocessing, analysis, and visualization. Each part is specifically designed to address the aforementioned challenges. The underlying problems are modeled as optimization problems, and efficient algorithms to solve them are developed. <br /> The preprocessing part includes a map-matching algorithm that adapts to varying spatial data quality and explicitly models potential off-road movement. Additionally, a discussion on ethical considerations and privacy preservation techniques is performed. <br /> The subsequent analysis part presents an algorithm to infer routing preferences from trajectory recordings. The algorithm accommodates diverse user intents and addresses participation inequality by working even with sparse input data and trajectories that cannot be explained by a single (combined) optimization criterion, such as round trips. <br /> The visualization part introduces a method for computing glyphs to visualize the off-screen parts of trajectories to facilitate the exploration of large trajectory datasets. Additionally, novel approaches to communicate travel times and distances through schematic isolines are presented. These visualizations utilize schematic representations to convey potential inaccuracies, enhancing understanding while acknowledging data limitations. <br /> Overall, this thesis contributes efficient algorithms that offer insights into the routing behavior of cyclists based on crowd-sourced data. The results can be applied to support decision-making in urban planning and transportation.

Im letzten Jahrzent haben die Aktivitäten vieler Freiwilliger zu fast vollständigen Darstellungen von Straßennetzen und großen Mengen von Trajektorien geführt. Letztere wurden vor allem von Freizeitsportlern gesammelt, die zum Beispiel Fahrradtouren oder Wanderungen aufgezeichnet haben. Diese neue Quelle von Geodaten, die im Bereich der freiwilligen geografischen Informationen (Volunteered Geographic Information, VGI) gesammelt werden, hat zum Aufkommen von Methoden zur Auswertung von Bewegungsdaten beigetragen. <br /> Auf der einen Seite bietet die Nutzung von nutzergenerierten Daten aufgrund ihrer großen Menge und Verfügbarkeit sowie der intrinsischen Nutzersicht zahlreiche Vorteile. Auf der anderen Seite stellt die große Daten-Heterogenität eine Herausforderung dar. Diese Heterogenität tritt in verschiedenen Aspekten der Daten auf, was zu vier Herausforderung führt: (1) unbekannte räumliche Genauigkeit, (2) fehlende Metadaten, (3) ungleichmäßige Beteiligung und (4) ethische Aspekte der Datennutzung. <br /> Diese Arbeit stellt eine methodische Pipeline vor, mit der sich die Routingpräferenzen der Nutzer aus ihren Bewegungsdaten ableiten lassen. Die Pipeline gliedert sich in Vorverarbeitung, Analyse und Visualisierung. Jeder Teil ist darauf ausgerichtet, die oben genannten Herausforderungen zu bewältigen. Die zugrundeliegenden Probleme sind als Optimierungsprobleme modelliert, und es werden effiziente Algorithmen zu ihrer Lösung entwickelt. <br /> Im Vorverarbeitungsteil wird ein Algorithmus zum Kartenabgleich vorgestellt, der mögliche Bewegungen abseits des Straßennetzes explizit modelliert. Außerdem werden Techniken zum Schutz der Privatsphäre der Nutzer diskutiert. <br /> Im Analyseteil wird ein Algorithmus vorgestellt, mit dem aus Bewegungsdaten Routingpräferenzen abgeleitet werden können. Der Algorithmus funktioniert auch mit wenigen Eingabedaten und kann selbst Bewegungungen, die nicht durch ein einziges (kombiniertes) Optimierungskriterium erklärt werden können, wie z.B. Rundfahrten, auswerten. Damit wird auf unterschiedliche Bewegungsintentionen und Ungleichheit der Beteiligung eingegangen. <br /> Der Visualisierungsteil führt eine Methode zur Berechnung von kartographischen Symbolen ein, die die Fortsetzung der Bewegungsdaten außerhalb des Bildschirms visualisieren und so die Erkundung großer Bewegungsdatensätze erleichtern. Weiterhin werden Ansätze zur Visualisierung von Reisezeiten durch Isolinien vorgestellt. Diese Visualisierungen nutzen schematische Darstellungen, um einfache, schnell zu begreifende Abbildungen zu erzeugen. <br /> Insgesamt trägt diese Arbeit zu effizienten Algorithmen bei, die Einblicke in das Routing-Verhalten von Radfahrern auf der Grundlage von Nutzerdaten bieten. Die Ergebnisse können zur Unterstützung der Stadt- und Verkehrsplanung eingesetzt werden.