论文标题
将预测和实时流量与时间依赖的A*电势相结合
Combining Predicted and Live Traffic with Time-Dependent A* Potentials
论文作者
论文摘要
我们研究有效且最短的路径算法，用于在道路网络上使用现实的交通数据进行路由。对于导航应用程序，当前（即实时）流量事件和未来流量的预测在路由中都起着重要作用。尽管基于预处理的加速技术已成功地分别采用了两种设置，但组合模型却带来了重大挑战。支持预测的流量通常需要昂贵的预处理，而实时流量则需要快速更新以进行定期调整。我们针对此问题提出了基于A*的解决方案。通过将*电势推广到时间依赖性，即，从顶点到目标的距离的估计也取决于访问顶点的一天中的时间，我们达到的查询时间明显比以前可能更快。我们的评估表明，我们的方法可以在大陆大小的道路网络上进行交互式查询时间，同时允许在一分钟内进行实时交通更新。在Dijkstra的算法上，我们达到了至少两个数量级的加速，并且在最新时间独立的a*电位上最多可以达到一个数量级。
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.
