Transit Node Routing Reconsidered
Transit Node Routing Reconsidered
复制标题
DOI：
10.1007/978-3-642-38527-8_7
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
Julian Arz;Dennis Luxen;P. Sanders
中科院分区：
文献类型：
--
作者：
Julian Arz;Dennis Luxen;P. Sanders
公交节点路由（TNR）是一种快速、准确的道路网络距离预测方法。我们展示了TNR的几个新结果。首先，我们给出了一个令人惊讶的简单的实现完全基于收缩层次结构，加快了预处理的数量级接近的时间，只是找到一个收缩层次结构（仅具有两个数量级更大的查询时间）。我们还开发了一个非常有效的纯图论局部性过滤器，在查询时间没有任何妥协。最后，我们证明了一个专门的在线多对一（或一对多）的最短路径问题。
Transit Node Routing (TNR) is a fast and exact distance oracle for road networks. We show several new results for TNR. First, we give a surprisingly simple implementation fully based on contraction hierarchies that speeds up preprocessing by an order of magnitude approaching the time for just finding a contraction hierarchy (which alone has two orders of magnitude larger query time). We also develop a very effective purely graph theoretical locality filter without any compromise in query times. Finally, we show that a specialization to the online many-to-one (or one-to-many) shortest path problem.