Study On Shortest Path Query On Road Networks Using Graph Partitioning Methods

With the development of mobile Internet, the demand for navigation has been in-creasing, and people need more diversified location based service. Due to moving ter-minal, real-time navigation based on people’s location has a more strict requirement of algorithm performance. With the development of transport, the activities of people get biger, which lead to navigation map data growing. The larger road map data often need longer computation time, contrary to people’s demand.Graph partitioning is a method to process graph data, widely used in parallel com-puting, large scale integrated circuit design and other fields. Shortest path computing in road network is also a query processing on graph data, there are natural correlation between them. This thesis focuses on shortest path query on road networks using graph partitioning methods, and proposes a new shortest path query algorithm based on rep-resentative, which can meet the demand of diversified service while obtaining better online query speed.The main work involved in this thesis includes:Study on the effect of graph partitioning for Arc-flags algorthm. Arc-flags is a classical algorithm that uses graph partitioning techniques to find the shortest path, the algorithm uses pre-processing technology to improve the online query speed. Previous work mainly focused on the performance optimiza-tion of pre-process and comparison of different graph partitioning methods, the influence of the graph partitioning for Arc-flags algorithm did not done in-depth analysis. We analyzes the effect of graph partitioning for Arc-flags algorithm in real road networks in many aspects, including the pre-processing time, memory consumption and online query efficiency, etc, and we put forward some graph partitioning suggestions for the computing of shortest path using Arc-flags algo-rithm under different situation.Define representative in directed graph, propose a new representatvie selection algorithm, and propose a shortest path query algorithm based on representative. Representative is a non-standard graph partitioning strategy, used in approximate shortest distance query. In the past, the approximate shortest path query algorithm based on representative only focus on undirected graph, but due to the existence of the one-way street, the real road network are usualy abstracted into a directed graph. In this thesis, we define representative in directed graph, and propose two new representative selection algorithms, which can reduce the number of rep-resentative effectively. Then we propose a new shortest path query algorithm based on representative in directed graph, which can provide efficient shortest path query function, while retaining the function of original approximate short-est distance query, the algrothim meet the demand of diversity. We test the new algorithm on the real road network, verify the effectiveness of the algorithm.