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

  • Axel Forsch
    Axel Forsch
  • Jan-Henrik Haunert

In the past decade, the activities of many volunteers have resulted in almost complete representations of street networks and large sets of trajectories. The latters have to a large extent been collected by recreational sportspeople who, for example, have recorded bicycle tours or hikes with GPS receivers. In this project we will use trajectories of bicyclists and pedestrians to analyze and visualize user-dependent routing preferences. In particular, we will pursue the question of whether differences in the observed routing behavior of different users can be attributed rather to different weights for a fix set of criteria or rather to differences between the sets of criteria that the users consider. Other than in existing approaches for learning parameters of routing models, which often aim at revealing general preferences of a larger population, we cannot rely on a large set of trajectories when learning individual preferences, since most users contribute only few trajectories that sparsely cover the street network. Therefore, new algorithmic approaches are needed. In particular, we need to be aware that training a routing model that involves a large number of parameters with only few trajectories will eventually lead to overfitting. Therefore, our aim is to automatically simplify a routing model by selecting the most relevant criteria and to determine weights for the selected criteria. In order to reveal similarities of and differences between the routing preferences of different users we will develop new algorithms for clustering and methods for the visualization of routing preferences in a geographic context. To this end we will investigate how weighted geometric graphs whose edge weights reflect routing preferences can be visualized with maps. Our algorithmic development will be largely driven by mathematical models, meaning that we will first strive for exact algorithms that will allow us to compute optimal solutions at least for small samples. Due to the high complexity of our problems that we expect, however, we will also develop efficient heuristics for processing trajectories of many users, which will be necessary for detecting clusters and for investigating differences as well as similarities within a larger population. To evaluate our heuristics we will compare solutions that we obtained with them with solutions of our exact methods. Based on extensive experiments we will highlight new possibilities of analyzing user-generated trajectories and address the initially raised question of whether different routing behaviors can be explained better with different weightings or with different selections of criteria.