Seamless Interpolation Between Contraction Hierarchies and Hub Labels for Fast and Space-Efficient Shortest Path Queries in Road Networks

被引：4
作者：
Funke, Stefan [1 ]
机构：
[1] Univ Stuttgart, Stuttgart, Germany
来源：
COMPUTING AND COMBINATORICS (COCOON 2020) | 2020年 / 12273卷
关键词：
Route planning; Contraction hierarchies; Hub labelling;
D O I：
10.1007/978-3-030-58150-3_10
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We propose a conceptually simple, yet very effective extension of the highly popular Contraction Hierarchies (CH) speedup technique improving query times for shortest paths in road networks by one order of magnitude with very modest space overhead. Using our scheme we are able to answer queries on continental-sized road networks with more than half a billion edges in the microseconds range on standard workstation hardware. Previous approaches that are considerably faster than CH were only for shortest path distance queries (recovering the actual path required additional effort and space) or suffered from humongous space consumption hindering their practicality for large real-world road networks. Our approach can be interpreted as a seamless interpolation between Contraction Hierarchies and Hub Labels.
引用
收藏
页码：123 / 135
页数：13
相关论文
共 18 条
  • [1] Abraham I, 2012, LECT NOTES COMPUT SC, V7501, P24, DOI 10.1007/978-3-642-33090-2_4
  • [2] Abraham I, 2011, LECT NOTES COMPUT SC, V6630, P230
  • [3] Arz Julian, 2013, Experimental Algorithms 12th International Symposium, SEA 2013. Proceedings, P55, DOI 10.1007/978-3-642-38527-8_7
  • [4] Bast H., 2015, ROUTE PLANNING TRANS, P1
  • [5] Bast H, 2007, SIAM PROC S, P46
  • [6] Fast routing in road networks with transit nodes
    Bast, Holger
    Funke, Stefan
    Sanders, Peter
    Schultes, Dominik
    [J]. SCIENCE, 2007, 316 (5824) : 566 - 566
  • [7] Bauer R., 2010, ACM J EXP ALGORITHMI, V15
  • [8] Bauer R, 2008, SIAM PROC S, P13
  • [9] Cohen E, 2002, SIAM PROC S, P937
  • [10] Delling Daniel, 2013, Experimental Algorithms 12th International Symposium, SEA 2013. Proceedings, P18, DOI 10.1007/978-3-642-38527-8_4
12