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.