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

在过去的十年中，许多志愿者的活动几乎完整地展示了道路网络和大量的轨迹。后者在很大程度上是由休闲运动员收集的，例如，他们用GPS接收器记录了自行车旅行或徒步旅行。在这个项目中，我们将使用骑自行车的人和行人的轨迹来分析和可视化用户依赖的路线首选项。具体而言，我们将探讨观察到的不同用户的路由行为的差异是否可以归因于固定准则集的不同权重，或者更确切地说，归因于用户考虑的准则集之间的差异。除了现有的路线模型参数学习方法通常旨在揭示更大人群的总体偏好之外，我们在学习个人偏好时不能依赖大集合的轨迹，因为大多数用户只贡献了稀疏覆盖道路网络的几条轨迹。因此，需要新的算法方法。特别是，我们需要意识到训练一个涉及大量参数而只有几个轨迹的路线选择模型将导致过度拟合的风险。因此，我们的目标是通过选择最相关的标准来自动简化路由模型，并确定所选标准的权重。为了揭示不同用户的路由偏好的异同，我们将开发新的聚类算法和地理环境下的路由偏好可视化方法。为此，我们将研究如何使用地图可视化其边权重反映布线偏好的加权几何图。我们的算法开发将在很大程度上受到数学模型的推动，这意味着我们将首先努力获得准确的算法，这些算法将使我们至少在小样本中计算出最优解。然而，由于我们预计我们的问题将具有高度的复杂性，我们还将开发有效的启发式算法来处理许多用户的轨迹，这将是检测集群和调查更大人群中的差异和相似之处所必需的。为了进行彻底的评估，我们将把我们的启发式方法的解与我们的精确方法的解进行比较。基于广泛的实验，我们将强调分析用户生成轨迹的新可能性，并解决最初提出的问题，即不同的权重或不同的标准选择是否可以更好地解释不同的路由行为。

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.