Inferring Personalized Multi-criteria Routing Models from Sparse Sets of Voluntarily Contributed Trajectories

点击翻译按钮获取中文摘要

In the past decade, the activities of many volunteers have resulted in almost complete representations of road networks and large sets of trajectories. The latter 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 road network. Therefore, new algorithmic approaches are needed. In particular, we need to be aware of the risk that training a routing model that involves a large number of parameters with only few trajectories will 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 driven largely 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. Since we expect our problems to be of high complexity, 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. For a thorough evaluation, we will compare solutions of our heuristics with those 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.