Accurate and Fast Path Computation in Urban Environments Using Region Pruning Strategies
详细信息 查看官网全文
- 英文论文题名：Accurate and Fast Path Computation in Urban Environments Using Region Pruning Strategies
- 论文作者：Qing Song ; Meng Li ; Xiaolei Li
- 英文论文作者：Qing Song ; Meng Li ; Xiaolei Li ; School of Electrical Engineering ; University of Jinan ; School of Control Science and Engineering ; Shandong University
- 年：2017
- 作者机构：School of Electrical Engineering,University of Jinan;School of Control Science and Engineering,Shandong University;
- 英文论文关键词：Path computation ; heuristics ; hierarchical ; urban road network
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（B）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
- 语种：英文
- 分类号：U495
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：6
- 文件大小：130k
- 原文格式：D
- 会议级别：全国
摘要
Accurate and fast path computation is essential for applications such as onboard navigation systems and traffic network routing.While a number of heuristic algorithms have been developed in the past few years for faster path queries,the accuracy of them are always far below satisfying.To facilitate accurate and fast routing applications,a three-level graph model is presented for structuring the urban road network,and a hierarchical path computation algorithm is then proposed,which benefits from the hierarchical graph model and utilizes a region pruning strategy to significantly reduce the search space without compromising the accuracy.The experimental evaluation on the real urban road network of New York City demonstrates the effectiveness of the proposed approach to generate optimal fast paths and to facilitate real-time routing applications.
Accurate and fast path computation is essential for applications such as onboard navigation systems and traffic network routing.While a number of heuristic algorithms have been developed in the past few years for faster path queries,the accuracy of them are always far below satisfying.To facilitate accurate and fast routing applications,a three-level graph model is presented for structuring the urban road network,and a hierarchical path computation algorithm is then proposed,which benefits from the hierarchical graph model and utilizes a region pruning strategy to significantly reduce the search space without compromising the accuracy.The experimental evaluation on the real urban road network of New York City demonstrates the effectiveness of the proposed approach to generate optimal fast paths and to facilitate real-time routing applications.
Accurate and fast path computation is essential for applications such as onboard navigation systems and traffic network routing.While a number of heuristic algorithms have been developed in the past few years for faster path queries,the accuracy of them are always far below satisfying.To facilitate accurate and fast routing applications,a three-level graph model is presented for structuring the urban road network,and a hierarchical path computation algorithm is then proposed,which benefits from the hierarchical graph model and utilizes a region pruning strategy to significantly reduce the search space without compromising the accuracy.The experimental evaluation on the real urban road network of New York City demonstrates the effectiveness of the proposed approach to generate optimal fast paths and to facilitate real-time routing applications.
引文
[1]H.Bast,D.Delling,A.Goldberg,et al.,Route planning in transportation networks,Algorithm Engineering:Selected Results and Surveys,19-80,2016.
[2]C.Sommer,Shortest-path queries in static networks,ACM Computing Surveys,46(4):Article 45,2014.
[3]E.W.Dijkstra,A note on two problems in connexion with graphs,Numer.Math.,1:269-271,1959.
[4]I.Pohl,Bi-directional search,Mach.Intell.,6:127-140,1971.
[5]E.P.Hart,N.J.Nilsson,and B.Raphael,A formal basis for the heuristic determination of minimum cost paths,IEEE Trans.Syst.Sci.Cybern.,SSC-4(2):100-107,1968.
[6]J.Lysgaard,A two-phase shortest path algorithm for networks with node coordinates,European Journal of Operational Research,87(2):368-374,1995.
[7]H.KARIMI,Real-time optimal route computation:a heuristic approach,ITS Journal,3(2):111-127,1996.
[8]B.Cherkassky,A.Goldberg,and T.Radzik,Shortest path algorithms:theory and experimental evaluation,Mathematical Programming,73:129-174,1996.
[9]D.Wagner and T.Willhalm,Geometric containers for efficient shortest-path computation,ACM J.Exp.Algor.,10(1.3):1-30,2005.
[10]R.M?hring,H.Schilling,B.Sch(u|")tz,et al.,Partitioning graphs to speed up Dijkstra's algorithm,ACM J.Exp.Algor.,11(2.8):1-29,2006.
[11]J.Maue,P.Sanders,and D.Matijevic,Goal directed shortest path queries using precomputed cluster distances,ACM J.Exp.Algor.,14(3.2):1-27,2009.
[12]S.Jung and S.Pramanik,An efficient path computation model for hierarchically structured topographical road maps,IEEE Trans.Knowl.Data Eng.,14(5):1029-1046,2002.
[13]R.Rajagopalan,K.Mehrotra,C.Mohan,et al.,Hierarchical path computation approach for large graphs,IEEE Trans.Aerosp.Electron.Syst.,44(2):427-440,2008.
[14]T.Chondrogiannis and J.Gamper,Exploring graph partitioning for shortest path queries on road networks,in Proceedings of the 26 GI-Workshop on Foundations of Databases,2014:1-6.
[15]B.Liu,Route finding by using knowledge about the road network,IEEE Trans.Syst.Man&Cyber.,Part A,27(4):436-448,1997.
[16]G.Jagadeesh,T.Srikanthan,and K.Quek,Heuristic techniques for accelerating hierarchical routing on road networks,IEEE Trans.Intell.Transp.Syst.,3(4):301-309,2002.
[17]http://www.dis.uniromal.it/~challenge9/download.shtml
[2]C.Sommer,Shortest-path queries in static networks,ACM Computing Surveys,46(4):Article 45,2014.
[3]E.W.Dijkstra,A note on two problems in connexion with graphs,Numer.Math.,1:269-271,1959.
[4]I.Pohl,Bi-directional search,Mach.Intell.,6:127-140,1971.
[5]E.P.Hart,N.J.Nilsson,and B.Raphael,A formal basis for the heuristic determination of minimum cost paths,IEEE Trans.Syst.Sci.Cybern.,SSC-4(2):100-107,1968.
[6]J.Lysgaard,A two-phase shortest path algorithm for networks with node coordinates,European Journal of Operational Research,87(2):368-374,1995.
[7]H.KARIMI,Real-time optimal route computation:a heuristic approach,ITS Journal,3(2):111-127,1996.
[8]B.Cherkassky,A.Goldberg,and T.Radzik,Shortest path algorithms:theory and experimental evaluation,Mathematical Programming,73:129-174,1996.
[9]D.Wagner and T.Willhalm,Geometric containers for efficient shortest-path computation,ACM J.Exp.Algor.,10(1.3):1-30,2005.
[10]R.M?hring,H.Schilling,B.Sch(u|")tz,et al.,Partitioning graphs to speed up Dijkstra's algorithm,ACM J.Exp.Algor.,11(2.8):1-29,2006.
[11]J.Maue,P.Sanders,and D.Matijevic,Goal directed shortest path queries using precomputed cluster distances,ACM J.Exp.Algor.,14(3.2):1-27,2009.
[12]S.Jung and S.Pramanik,An efficient path computation model for hierarchically structured topographical road maps,IEEE Trans.Knowl.Data Eng.,14(5):1029-1046,2002.
[13]R.Rajagopalan,K.Mehrotra,C.Mohan,et al.,Hierarchical path computation approach for large graphs,IEEE Trans.Aerosp.Electron.Syst.,44(2):427-440,2008.
[14]T.Chondrogiannis and J.Gamper,Exploring graph partitioning for shortest path queries on road networks,in Proceedings of the 26 GI-Workshop on Foundations of Databases,2014:1-6.
[15]B.Liu,Route finding by using knowledge about the road network,IEEE Trans.Syst.Man&Cyber.,Part A,27(4):436-448,1997.
[16]G.Jagadeesh,T.Srikanthan,and K.Quek,Heuristic techniques for accelerating hierarchical routing on road networks,IEEE Trans.Intell.Transp.Syst.,3(4):301-309,2002.
[17]http://www.dis.uniromal.it/~challenge9/download.shtml