Research On The Optimal Path Algorithm And Web Service In Distributed Multi-level Large Road Network

With the expansion of city and the development of transportation, the road network of urban is getting huger and huger. The optimal path of road network has been discussed thoroughly in graph theory, computation geometry, and artificial intelligence, but most of them limit in the certain region scope and analyze the data in established database. The optimal path computation on wide range road network will process large amount of data and spend very long time. So as to the wide range data, which one road network can't hold enough, is unable to obtain satisfied result. Moreover it costs too much time and money to maintain respective database, and the change of road can't be modified database in time generally. Therefore, processing the optimal path on wide range road network is a crucial question to resolve urgently and provides the effective driving route for the driver becomes one of the most important tasks of the intelligent transportation system.In order to resolve the question, the thesis put forward the optimal path algorithm in distributed multi-level road network. In the large data quantity situation, the distribute multi-level road network is integrated to construct the data model which pyramid resembles. The whole sketchy data in the overall scope are placed at low level and the detail data are placed at high level, so as to reduce the data quantity and computing time. Otherwise, the data model is made of multi-level, and the optimal path is changed by different road level. Main road has a higher priority in road selection, because the drivers prefer to convenient main road rather than the inconvenient.With the development of the web service and Internet technology, more and more data information can be obtained on Internet. It provides the massive data for the optimal path on wide range road networks and creates the essential condition for integrating the distributed multi-level road network. Since the Open Geospatial Consortium (OGC) and the geography information standardization work team ISO/TC211 established by the International Standardization Organization, two organization have done a lot of research work for the data sharing and interoperability, solved a great deal of technical question and formulated a series of standards. The distributed road network data coming from different data source, different district, and different GIS software on Internet are integrated by the standards. It provides the good technique support to set up the multi-level road network. However, the International Standardization Organization has not formulated standards for function sharing. Therefore, discussing the web service for the optimal path on wide range road network and realizing the suitable function service is the question that needs to solve.The optimal path question on wide range road network based on the data coming fromInternet has to deal with a series of questions, such as algorithm, multi-level network data model constructs, multi-level network data logical uniformity, topological uniformity, multiple data source sharing and interoperability, data transmission interface uniformity, web service for data sharing and function sharing, and web services integration etc. The thesis discusses the questions above, and the main research contents include below:1) Research on the data model of distributed multi-level road network. The metadata information of the road network, the expression of the road network's spatial information and attribute information are studied. The data models on wide range road network at present are discussed and each algorithm is compared. The method using multi-level road network is proposed to make up the deficiency of existing algorithms. In the situation of large area which need lots of map data, multi-scale information are used as road graduated standard, while it comes to small area needs fewer map, road attribution information are used as road graduate standard. Pyramid-like multi-level road network model are constructed based on the two standards. And essential technical question, such as the multi-level network constructs, the logical uniform question in the multi-level road network data, and the topological uniform question, are discussed in detail.2) Research on the optimal path algorithm of distributed multi-level road network. Classics optimal path algorithms are reviewed and existed problems are discussed. In order to make up insufficiency of existed optimal path algorithm, the thesis proposes optimal path algorithm based on the distributed multi-level road network. The algorithm's design, mathematics expression, as well as algorithm implementation are narrated.3) Research on the essential technical question about the optimal path algorithm of distributed multi-level road network. Essential technical questions are discussed detailed, such as the multi-level network data matching, the multi-level network weight value definition, and the algorithm efficiency and rationality. Firstly, spatial data matching method are analyzed based the on the existing spatial data map merge technology. Considering the multi-level road network's characteristic, the thesis proposes the matching algorithm of estimating distance between the nodes in line objects based on the grid spatial index. And the feasibility and the validity of the matching algorithm are proved by the experiment. Secondly, Discussing the existing computation method of the weight value in network, the thesis proposes weight value determination algorithm based on the fuzzy mathematics before a careful analyzing of factors that affect road weight value in the dynamic change transportation. Finally, two application examples are implemented to prove the efficiency and the rationality of this algorithm.4) Research on the web service of the optimal path algorithm. The web service's registration and finding technology are used to search the distributed road network in different database server. Distributed road network data are obtained based on multiple data source sharing andinteroperability methods. And the distributed multi-level road network data are integrated and fused to create multi-level road network. The web function services of the optimal path algorithm are studied on the aspect of the function service's design, structure, and interface definition. The function service workflow of the multi-level road network is put forward on the base of function service sharing and interoperability.5) Research on the application system of the optimal path web service. An application system based on multi-level road network is designed and implemented. The experiment results show that the web services of the optimal path are feasible and efficient in the processing of multi-level road network in wide area.