Inferring routing preferences from user-generated trajectories using a compression criterion

Authors

DOI:

https://doi.org/10.5311/JOSIS.2023.26.256

Keywords:

trajectory mining, bicriteria optimization, compression, routing preferences, volunteered geographic information

Abstract

The optimal path between two vertices in a graph depends on the optimization objective, which is often defined as a weighted sum of multiple criteria. When integrating two criteria, their relative importance is expressed with a balance factor α. We present a new approach for inferring α from trajectories. The core of our approach is a compression algorithm that requires a graph G representing a transportation network, two edge costs modeling routing criteria, and a path P in G representing the trajectory. It yields a minimum subsequence S of the sequence of vertices of P and a balance factor α, such that the path P can be fully reconstructed from S, G, its edge costs, and α. By minimizing the size of S over α, we learn the balance factor that corresponds best to the user's routing preferences. In an evaluation with crowd-sourced cycling trajectories, we weigh the usage of official signposted cycle routes against other routes. More than 50% of the trajectories can be segmented into five optimal sub-paths or less. Almost 40% of the trajectories indicate that the cyclist is willing to take a detour of 50% over the geodesic shortest path to use an official cycle path.

Author Biographies

Axel Forsch, Working Group Geoinformation, University of Bonn

Axel Forsch finished his Master of Science in Geodesy and Geoinformation at the University of Bonn in 2019. Currently, he continues his studies at the University of Bonn within the frame of a Ph.D. program regarding Volunteered Geographic Information. His research is focused on the algorithmic analysis and visualization of movement patterns. A central topic of Axel Forsch's research is to infer routing preferences from trajectories recorded by cyclists.

Johannes Oehrlein, Working Group Geoinformation, University of Bonn

Johannes Oehrlein holds a Master's degree in mathematics from the University of Würzburg, Germany, and a doctoral degree in geodesy and geoinformatics from the University of Bonn. In his research, he focuses on exact algorithms for aggregating spatial data. Currently, he is part of a team that is developing national account systems for ecosystem services at the Federal Statistical Office of Germany. Within this team, he is responsible for the combination and aggregation of diverse nationwide data.

Benjamin Niedermann, Working Group Geoinformation, University of Bonn

Benjamin Niedermann obtained his Ph.D. degree in Computer Science from the Karlsruhe Institute of Technology (KIT), Germany, in 2017. From 2017 to 2021 he was a member of the research group Geoinformation at the University of Bonn. His research interests comprise the development of efficient algorithms in Computational Geometry, Computational Cartography, and Geoprocessing. One main focus of his research is label placement in figures, maps, and dynamic scenes. It includes mathematical models, the design of algorithms with provable guarantees as well as the empirical evaluation of the algorithms in real-world scenarios. Currently, he is an engineer at yWorks working on algorithms for automatic graph drawing.

Jan-Henrik Haunert, Working Group Geoinformation, University of Bonn

Jan-Henrik Haunert holds a diploma and doctoral degree in geodesy and geoinformatics from the University of Hannover, Germany. He has been a postdoctoral researcher at the institute of computer science at the University of Würzburg, Germany, and a professor for geoinformatics at the University of Osnabrück, Germany. In 2016, he took up a full professorship of geoinformation at the University of Bonn, Germany. His research is concerned with the development of efficient algorithms for geovisualization and spatial analysis. In particular, he applies methods from combinatorial optimization and computational geometry to tasks in automated cartography, such as map generalization and cartographic label placement.

256

Downloads

Published

2023-05-17

Issue

Section

Research Articles