Forward Search in Contraction Hierarchies
Forward Search in Contraction Hierarchies
复制标题
收缩层次结构中的正向搜索
DOI：
10.1609/socs.v9i1.18454
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Peter James Stuckey
中科院分区：
文献类型：
--
作者：
Daniel Damir Harabor;Peter James Stuckey
收缩层次结构是基于图的数据结构，旨在加速道路网络中的最短路径搜索。在离线预处理步骤中构建的收缩层次结构始终与在线查询算法配对，该算法是双向 Dijkstra 搜索的变体。尽管有效且非常流行，但这种组合有时可能难以扩展，例如为了利用目标导向的启发法或其他前向驱动的修剪技术。在本文中，我们解构了收缩层次结构的双向查询算法，并推导了一种与标准单向或双向搜索兼容的新算法模式。然后，我们开发了各种新的单向查询算法，以在收缩层次结构中找到最佳路径。这些基于 A* 搜索和几何容器（一种众所周知且成功的边缘修剪技术）的组合。经验结果表明，与双向 Dijkstra 相比，我们的方法可以将搜索时间缩短一个数量级，尽管代价是额外的内存和预处理时间。
Contraction hierarchies are graph-based data structure developed to speed up shortest path search in road networks. Built during an offline pre-processing step, contraction hierarchies are always paired with an online query algorithm which is a variation on bi-directional Dijkstra search. Though effective and highly popular this combination can sometimes be difficult to extend, for example in order to leverage goal-directed heuristics or other forward-driven pruning techniques. In this paper we deconstruct the bi-directional query algorithm of contraction hierarchies and derive a new algorithmic schema which is compatible with standard uni-directional or bi-directional search. We then develop a variety of new uni-directional query algorithms to find optimal paths in contraction hierarchies. These are based on the combination of A* search and Geometric Containers, a well known and successful edge-pruning technique. Empirical results show that our approach can improve search times by an order of magnitude vs bi-directional Dijkstra, albeit at the cost of additional memory and pre-processing time.
DOI：
10.1016/j.tcs.2016.07.003
发表时间：
2013-07
期刊：
--
影响因子：
--
作者：
Reinhard Bauer;Tobias Columbus;Ignaz Rutter;D. Wagner
通讯作者：
Reinhard Bauer;Tobias Columbus;Ignaz Rutter;D. Wagner