Customizable contraction hierarchies are one of the most popular route planning frameworks in practice, due to their simplicity and versatility. In this work, we present a novel algorithm for finding k-nearest neighbors in customizable contraction hierarchies by systematically exploring the associated separator decomposition tree. Compared to previous bucket-based approaches, our algorithm requires much less target-dependent preprocessing effort. Moreover, we use our novel approach in two concrete applications. The first application are online k-closest point-of-interest queries, where the points of interest are only revealed at query time. We achieve query times of about 25 milliseconds on a continental road network, which is fast enough for interactive systems. The second application is travel demand generation. We show how to accelerate a recently introduced travel demand generator by a factor of more than 50 using our novel nearest-neighbor algorithm.
翻译:可定制的收缩等级是实践中最受欢迎的路线规划框架之一,因为其简单性和多功能性。在这项工作中,我们通过系统探索相关的分离器分解树,提出了在定制的缩缩等级中寻找 k 近邻的新算法。与以前以桶为基础的方法相比,我们的算法需要的远不那么取决于目标的预处理努力。此外,我们在两个具体的应用程序中采用了我们的新颖的方法。第一个应用程序是在线的 k- closest 点查询,其中感兴趣的点只在查询时间披露。我们在大陆公路网络上达到大约25毫秒的查询时间,这个时间对于互动系统来说足够快。第二个应用程序是旅行需求生成。我们展示了如何利用我们新的近邻算法以超过50倍的系数加速最近引入的旅行需求生成器。