Based On Road Network Hierarchical Multi-level Search Algorithm

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.