We study efficient and exact shortest path algorithms for routing on road networks with realistic traffic data. For navigation applications, both current (i.e., live) traffic events and predictions of future traffic flows play an important role in routing. While preprocessing-based speedup techniques have been employed successfully to both settings individually, a combined model poses significant challenges. Supporting predicted traffic typically requires expensive preprocessing while live traffic requires fast updates for regular adjustments. We propose an A*-based solution to this problem. By generalizing A* potentials to time dependency, i.e. the estimate of the distance from a vertex to the target also depends on the time of day when the vertex is visited, we achieve significantly faster query times than previously possible. Our evaluation shows that our approach enables interactive query times on continental-sized road networks while allowing live traffic updates within a fraction of a minute. We achieve a speedup of at least two orders of magnitude over Dijkstra's algorithm and up to one order of magnitude over state-of-the-art time-independent A* potentials.
翻译:我们用现实的交通数据研究公路网络路线的高效和精确最短路径算法。关于导航应用,当前(即现场)交通事件和对未来交通流量的预测在航程中起着重要作用。虽然预先处理的加速技术已经成功地个别地适用于两种环境,但一个综合模型却构成重大挑战。支持预测的交通通常需要昂贵的预处理,而现场交通则需要快速更新,以便定期调整。我们提出了一个基于A*的解决方案。通过将A* 的可能性概括到时间依赖性,即估计从顶层到目标的距离也取决于访问顶层的一天时间,我们比以前更快的查询时间。我们的评估表明,我们的方法使得大陆大小的公路网络能够交互查询时间,同时允许在一分钟内进行现场交通更新。我们比Dijkstra的算法实现至少两个数量级的加速速度,并达到一个数量级的距离,超过该时间依赖的A*的潜力。