基于路网分层的多级搜索算法的研究与实现

【作者】 任金胜；

【导师】 朱清新；

【作者基本信息】 电子科技大学 ， 计算机应用技术， 2008， 硕士

【摘要】 近年来,智能交通系统(ITS)、车载GPS定位系统、城市交通诱导系统等相关地理信息系统(GIS)技术的广泛应用对电子地图搜索服务提出了更高的要求。因此,对电子地图搜索及其相关领域的研究已变得炙手可热。本文研究了电子地图搜索服务中的一个核心议题:最短路径问题求解。拥有海量数据是GIS系统的一个显著特点,合理地提取、组织、分析和处理电子地图数据是提高寻径效率的关键。传统最短路径问题的研究更多地注重算法的改进和优化,或者是基于少量地图数据的寻径系统的实现;本文则侧重于海量数据下的寻径及其性能优化,提出基于路网分层的多级搜索算法,实现了全美国的Door2Door(门牌号到门牌号)寻径系统。其主要研究工作如下:1.提出基于路网分层的多级搜索算法,并比较几种传统寻径算法的优劣,选择了适合GIS中大数据量寻径的A~*算法作为其通用最短寻径算法;2.将分层思想引入路网数据组织,从地图数据中提取出需要的数据通过分层、合并、简化等方式组织成特定的道路数据文件,并建立路网数据库;3.通过实验得出了适用于全美寻径系统的A~*算法的估价函数的加权模型;以此为基础提出了基于海量数据下的各种寻径策略,并讨论其具体实现的细节问题;4.讨论寻径中的必备工具——RTree模块,研究TIGER数据和Shape文件的组织格式;5.基于前面的研究实现了一个实用高效的寻径系统。全文主要对GIS寻径问题中海量数据的处理进行了较为深入的探索并提出相应的算法,并且初步实现了全美国的Door2Door寻径系统,证明了理论研究的价值和可行性。目前国内关于大数据量下的最短路径问题的研究还比较薄弱,实用性的资料较少,因此本文的研究有较大的理论意义,而且本文已经初步实现了一个寻径系统,因此有着更大的现实意义。更多还原

【Abstract】 In recent years, the widespread application of the Intelligent Transportation system (ITS), automotive GPS positioning system, Urban Transport system and so on related geographic information system (GIS) technology has set a higher request to the electronic map search service. It is very important to give a research in the electronic map searching and other related fields.Finding the shortest Path that is one of the key problems in this field has been reasearched in the thesis. Huge Data is a special character of GIS. Extracting, organizing, analyzing and processing the huge data in a good way are the key point of improving the efficiency. Most of the traditional researches focus on the improvement and optimization of routing algorithm, or developing a routing system based on less map data, while this thesis concentrates on another aspect: how to find shortest path on a huge map data, and optimize its performance. Multi-level search algorithm based on hierarchy of road network (MSA-HR) was proposesed. Moreover, a door2door routing system of US was developped as an example based on the algorithm. The thesis mainly does the following work:1. Put forward MSA-HR, and choose the A~* algorithm available for routing among huge data in GIS by comparing with other traditional routing algorithm as the current algorithm to find shortest route.2. According to the idea of hierarchy of road network, pick up required information from Map Data through subdivision, combination, simplification, etc. to organization specific road data document to establish a database of road.3. Obtain weighted model of appraisal function of A~* algorithm available for US routing system through experiment; based on which we put forward various strategies for routing under huge data and discuss details to make it come true.4. Discuss the RTree module, which is necessary in the routing system, and investigate about the organization manner of TIGER data and document configuration of Shape file.5. Fulfill a practical and high-efficiency routing system. The routing in huge data is the mainly sought in the thesis, and some relative algorithm has been proposed, and a US Door2Door routing system has been realized, which can convince the value and feasibility. Research over shortest route under huge data seldom introduced in China, so there is little useful information about routing in huge data. Therefore, this thesis has some theoretical meaning; a routing system has fulfilled, so the thesis has practical meaning also.更多还原