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

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

作　　者：顾明皓[1] 徐明[1,2] 

机构地区：[1]上海海事大学信息工程学院,上海201306 [2]同济大学电子与信息工程学院,上海201804

出　　处：《计算机科学》2016年第6期188-193,247,共7页Computer Science

基　　金：国家自然科学基金项目(61202370);上海市教委科研创新项目(14YZ110);中国博士后科学基金资助项目(2014M561512)资助

摘　　要：针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。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 proproeessed,i, e. using the definition of the MCL to classify the road network. Then ErIC 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 ad- vantage 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 demon- strate that the storage space of ECT is 45.56% less than the PCI）C 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.60/0 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.

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]