路网中基于地理位置和区域封闭性的最短路径的查询算法

计算机科学 ›› 2016, Vol. 43 ›› Issue (6): 188-193.doi: 10.11896/j.issn.1002-137X.2016.06.038

路网中基于地理位置和区域封闭性的最短路径的查询算法

顾明皓,徐明

上海海事大学信息工程学院上海201306,上海海事大学信息工程学院上海201306;同济大学电子与信息工程学院上海201804

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受国家自然科学基金项目(61202370),上海市教委科研创新项目(14YZ110),中国博士后科学基金资助

Shortest Path Searching Algorithm Based on Geographical Coordinates and Closed Attribute in Road Network

GU Ming-hao and XU Ming

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分；其次利用ECT树对划分出的MCL格进行存储；最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。

关键词: MCL格,最短路径,虚拟路径,ECT树,预处理

Abstract: Concerning the problem of finding the shortest path in the large scale city road network,this paper proposed an algorithm based on the Edge Clustering Tree and Minimal Closed Lattice to achieve the goal of quick searching.Firstly,the city road network is proprocessed,i.e. using the definition of the MCL to classify the road network.Then ETC is used to storage the MCL .Eventually,depending on the idea of the virtual path(the shortest distance between two points is the straight line distance),combining the attribute of MCL planarity of the road network and taking advantage of the ECT will dramatically reduce the visits to dud nodes.So this kind of algorithm really reduces the time complexity and achieves the purpose of quick searching.The theoretical analysis and the simulation experiment demonstrate that the storage space of ECT is 45.56% less than the PCDC algorithm and 24.35% less than TNR.In the aspect of storage,ECT is slightly better than SILC.Besides,the query efficiency of the MCL is 15.6% faster than that of the SPB.The results of the experiment suggest that the MCL algorithm based on ETC storage can improve the query efficiency.

Key words: Minimal closed lattice(MCL),Shortest path,Virtual path,Edge clustering tree(ECT),Preprocessing

顾明皓,徐明. 路网中基于地理位置和区域封闭性的最短路径的查询算法[J]. 计算机科学, 2016, 43(6): 188-193. https://doi.org/10.11896/j.issn.1002-137X.2016.06.038

GU Ming-hao and XU Ming. Shortest Path Searching Algorithm Based on Geographical Coordinates and Closed Attribute in Road Network[J]. Computer Science, 2016, 43(6): 188-193. https://doi.org/10.11896/j.issn.1002-137X.2016.06.038

参考文献

[1] Dijkstra E W.A note on two Problems in connectionwithgraphs[J].Numerische Mathematik,1959,1(1):269-271
[2] Samet H,Sankaranarayanan J,Alborzi H.Sealable network distance browsing in spatial databases[C]∥The 8th SIGMOD ACM Conference.2008:43-54
[3] Klein P N,Mozes S,Weimann O.Shortest Paths in direeted Planar graphs with negative lengths:Aline-space time algorithm[J].ACM Transactions on Algorithms,2010,6(2):1-13
[4] Papadias D,Zhang J,Mamoulis N,et al.Query processing inspatial network databases [C]∥The 3rd VLDB.2003:802-813
[5] Cho H J,Chung C W.An efficient and scalable approach to CNN queries in a road network[C]∥The 5th VLDB.2005:865-876
[6] Sanders P,Sehultes D.Highway hierarchieshasten exact shortest path queries[C]∥13th Annual European Symposium2005 .Palma de Mallorca,Spain,October 2005:568-579
[7] Geisberger R,Sanders P,Sehultes D,et al.Con-Traction hierarchies[C]∥Faster and Simpler Hierarchical Routing in Road Networks.WEA,2008:319-333
[8] Bast H,Funke S,Matijevie D.Transit:ultrafast shortest-Path queries with linear-time Preprocessing[C]∥The 9th DIMACS Implementation Challenge.2006:175-192
[9] Deng Ding-xiong.Shortest Path Queries on Road Networksbased on Pre-Computation Techniques [D].Shanghai:FuDan University,2011
[10] Lee K C K,Lee W C,Zheng Bai-hua,et al.ROAD:A New Spatial Object Search Framework for Road Networks[J].IEEE Transactions Onknowledge and Data Engineering,2012,4(3):547-560
[11] Wang Shi-ming.Research and Realization of the Shortest Path Algorithm within Topical Urban Road Network[D].Shandong:Shandong University,2012
[12] Lu Zhao,Shi Jun.Design and Implementation of parallel shortest path search algorithm[J].Computer Engineering and applications,2010,6(3):69-71(in Chinese) 卢照,师军.并行最短路径搜所算法的设计与实现[J].计算机工程与应用,2010,6(3):69-71
[13] Deng Ding-xiong.Shortest Path Query for Road Network Based on SPB Tree[J].Computer Engineering,2011,37(22):56-63
[14] Gargantini I.An Effective Way to Represent Quadtrees[J].Com-munication of ACM,1982,25(12):905-910
[15] Sankaranarayanan J,Alborzi H,Samet H.Efficient query Processing on spatial networks[C]∥GIS’05.2005:200-209
[16] Sankaranarayanan J,Samet H.Distance oracles for spatial network[J].IEEE Computer Society,2009,9:652-663
[17] Sankaranarayanan J,Samet H,Alborzi H.Path oracles for Spatial networks[J].PVLDB,2009,2:1210-1221
[18] Goldberg A V,Harrelson C.Computing the shortest Path:A*search meets graph theory[C]∥ Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.2005:156-165

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed