Candidate Sets for Alternative Routes in Road Networks
Candidate Sets for Alternative Routes in Road Networks
复制标题
DOI：
10.1145/2674395
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Dennis Luxen;D. Schieferdecker
中科院分区：
文献类型：
--
作者：
Dennis Luxen;D. Schieferdecker
我们研究了道路网络中最短路径的良好替代方案的计算。我们的方法基于收缩层次结构之上的单个通过节点路由，并且与以前的方法相比，质量和效率更高。我们提出了一种快速的预处理方法，用于计算多种良好的替代方案，并将此结果应用于在线环境中。此设置使我们的结果适用于具有可忽略的内存开销的旧系统。对大陆大小的实地世界道路网络进行了广泛的实验分析，证明了我们的算法的性能，并支持一般的系统算法工程方法。我们还展示了如何将结果与替代图的竞争概念结合起来，这些图立即编码许多替代路径。
We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We present a fast preprocessing method for computing multiple good alternatives and apply this result in an online setting. This setting makes our result applicable in legacy systems with negligible memory overhead. An extensive experimental analysis on a continental-sized real- world road network proves the performance of our algorithm and supports the general systematic algorithm engineering approach. We also show how to combine our results with the competing concept of alternative graphs that encode many alternative paths at once.