VGIscience

Inferring personalized multi-criteria routing models from sparse sets of voluntarily contributed trajectories (VGI-Routing)

  • Axel Forsch
    Axel Forsch
    Bonn
  • Jan-Henrik Haunert
    Jan-Henrik Haunert
    Bonn
VGI-Routing

In the past 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 GPS receivers. In this project, we used trajectories of bicyclists and pedestrians to analyze user-dependent routing preferences.

Other than in existing approaches for learning parameters of routing models, which often aim at revealing the general preferences of a larger population, we cannot rely on a large set of trajectories when learning individual preferences since most users contribute only a few trajectories that sparsely cover the street network. Additionally, existing approaches often assume that the user followed a clear minimization goal when recording the trajectory, e.g., minimizing the geometric length of the route. For crowd-sourced trajectories, which are often recorded during recreational activities, this assumption often does not hold. Therefore, we present a compression-based algorithm that is designed in view of the heterogeneity of crowd-sourced data.

Using VGI data sources imposes algorithmic challenges, such as the input data’s unknown quality, and ethical challenges, such as the users’ privacy. Therefore, we present a pipeline for processing VGI trajectories, including preprocessing, analysis, and visualization approaches. The following provides an overview of that pipeline and the project results.

Summary

Anonymizing Trajectory Data

Trajectories are personal data, and as such, they come within the ambit of the General Data Protection Regulation (GDPR). Therefore, the user’s privacy must always be considered when collecting or analyzing users’ trajectories.

k-site-unidentifability We introduce k-site-unidentifability, which transfers the concept of k-anonymity to sensitive locations along a trajectory. k-site-unidentifability for a given site requires that the site is hidden within a set of at least k-1 other sites.

Trajectory T ending at ē. Site ē should be hidden in the protetion set C(ē) (squares). Truncation based on proximity to destination. None of the sites in C(ē) is the closest site to the end of T'. Truncation based on direction towards destination. Either all or none of the sites in C(ē) are in the gray direction cone.

For further information, see Brauer et al. (2022).

Map Matching

In the context of a Young Researchers Group (YRG), a collaboration together with the VGI projects Trajectories 2 and AQA on the topic of map matching has been done.

Map Matching for Semi-Resticted Trajectories How can trajectories leaving the mapped road network be continuously matched to an underlying graph?

The results are on the project page of the YRG.

Inferring Routing Preferences From User-Generated Trajectories

Our approach is to determine the parameter of a routing model such that a given trajectory can be partitioned into a minimum number of paths that are optimal with respect to that model.

Compression Criterion The fewer subpaths are needed, the better α matches the routing preference of the user.

α = 0.56

α = 0.78

Using our model, we analyzed a dataset of 1016 cycling trajectories from the crowd-sourced community platform GPSies1 towards the usage of official cycling routes. We were able to identify three groups of cyclists. Cyclists in the group PRO are willing to cover 50% longer distances to stick to official cycling routes, while cyclists in the group CON avoided these routes. Cyclists in the group INDIF are not influenced by the official cycling routes.

Multi-Criteria approach

In general, the preference of a cyclist cannot be described by two influence factors alone. Therefore, we apply an iterative scheme to consider an arbitrary amount of influence factors. First, we merge two criteria into a combined criterion. Then, this combined criterion can be merged with an additional criterion.

iterative approach

The routing preferences of cyclists do not only differ with respect to the numerical values of the weights for a prescribed set of criteria but also with respect to the subset of the criteria that explains the chosen routes. We stop this iterative process when a certain quality is reached to not to overfit our model.

Visualizing Routing Preferences With Schematic Isochrones

The routing preferences calculated with our approach presented above are parameters of a mathematical model. As such, they are hard to interpret. To improve the interpretability of the results, we use isochrone visualizations for the identified routing profiles. Traditionally, an isochrone visualizes the reachable area within a specific time. We adapt this definition and display the reachable area within a specific effort. The better a specific route meets your preferences, the less effort is needed to ride along this route.

The following two images show the routing profiles PRO and CON as identified above.

Visualization of the routing profile PRO using isochrones. Visualization of the routing profile CON using isochrones.

For further information, see Forsch et al. (2021).

Schematic Morphing Between Polylines

An efficient map comparison between the two states is needed to explore the differences between the routing profiles. One way for such a comparison is to use animated transitions between the two states. We present an algorithm for computing such animations, called morphs, between schematized polygonal map objects. In particular, our morph guarantees that the morph is:

  • self-intersection free,
  • topologically correct (intermediate polyline is always in between the two input polylines), and
  • preserves the schematization of the input polylines.

A schematic morph animation between the routing profile CON and PRO. Roads in the background map that are official cycling routes are drawn in blue and purple. Maps © Thunderforest, Data © OpenStreetMap contributors.

Visualizing the Off-Screen Evolution of Trajectories

Trajectories often span large distances. This imposes challenges for the visual exploration of trajectory datasets: on small scales, the overall context of the trajectory is captured, but details get lost, while the opposite is true for larger scales. We present an approach for visualizing the off-screen continuation of a trajectory to preserve the overall context when zooming into trajectory datasets.

Glyphs indicating how the trajectory in the dataset evolves outside the visible map frame. The glyphs indicate the trajectory's direction and variability of the direction outside the map. Detailed view on a glyph. The right-hand side is part of the visible map frame; the left-hand side is not visible. The glyph is placed in a region along the map boundary.
Maps © CARTO, Data © OpenStreetMap contributors.

For further information, see Forsch et al. (2022).

Code, Data, and Supplementary Material

Source code, supplementary material, and example datasets are provided for most projects as open source. The following gives an overview of the available sources.

  1. no longer available ↩

Publications

  1. Brauer, A., Mäkinen, V., Forsch, A., Oksanen, J., & Haunert, J.-H. (2022). My home is my secret: concealing sensitive locations by context-aware trajectory truncation. International Journal of Geographical Information Science, 36(12), 2496–2524. DOI: 10.1080/13658816.2022.2081694
  2. Forsch, A., Amann, F., & Haunert, J.-H. (2022). Visualizing the Off-Screen Evolution of Trajectories. KN - Journal of Cartography and Geographic Information, 72(3), 201–212. DOI: 10.1007/s42489-022-00106-6
  3. Korir, V., Forsch, A., Dehbi, Y., & Haunert, J.-H. (2022). Visualizing the Modal Split in Public Transportation Networks. Abstracts of the ICA, 5, 89. DOI: 10.5194/ica-abs-5-89-2022
  4. Forsch, A., Kemna, R., Langetepe, E., & Haunert, J.-H. (2022, April). Morphing of Schematized Polygons for Animated Travel-Time Maps. 3rd Schematic Mapping Workshop.
  5. Forsch, A., Dehbi, Y., Niedermann, B., Oehrlein, J., Rottmann, P., & Haunert, J.-H. (2021). Multimodal Travel-Time Maps with Formally Correct and Schematic Isochrones. Transactions in GIS, 25(6), 3233–3256. DOI: 10.1111/tgis.12821