Research On Route Planning Module Of Vehicle Navigation System

Intelligent Transportation System (ITS) is one of the important ways of solving the antinomy of traffic demand and supply in the modern society. As one of the core component parts of ITS, Vehicle Navigation System (VNS) has its extensive application prospect, which leads it to be one of the hottest researching realms contended by the countries all over the world. In a VNS, the Route Planning Module (RPM) receives dynamic traffic information via Traffic Information Service Center, it also acquires the location of the vehicle via Positioning Module. With these information, it plans an optimal route for the travelers which makes the travel safer, less time consuming, more comfortable, and more economic. This paper conducts a research on RPM and its related realms from various aspects.In the paper, the research on the development of ITS is discussed first. The structure and function of each module of VNS are outlined. Status quo of research on VNS is reviewed. In the meanwhile, subjects that need to be studied are suggested. Based on the above discussion, the problems that need to be resolved in VNS are analyzed.Geographic Information System for Transportation (GIS-T) is the extented application of GIS in the field of transportation. As it provides geographical data needed by Route Planning Module, it is a foundational module in VNS. This paper carries out research on the storing scheme of the spatial data and attributive data in GIS-T. This paper also analyses the structure and function of GIS-T , and carries out the analysis of the spatial and attributive data structure. In the analysis of the spatial data structure, it researches on dynamic segmentation technology and its application in VNS. As a result, the paper developed a practical dynamic segmentation software. It proves that, by applying it in practical road network, the software efficiently carried out the dynamic segmentation function and it was stable and reliable.This paper introduced XML technique into VNS with regard to spatial data storage and management. It carries out the research on storing topological data of digital map with XML format, storing spatial data of digital map with SVG format, handling topological and spatial data using DOM technique respectively. It also exemplified some of the applications of these usages. The topological and spatial data stored in the format of XML, which is a standard format, can well be transmitted and exchanged via network. Moreover, it can ensure that the data would be renewed in good time via wireless communication.Based on the data of the investigation of the velocity and traffic volume of the typical roads, this paper discusses the ways and means of modeling a Travel Time Model for Road Section, which is applicable for VNS, and demarcates the model. As we know, in a real road network, a big proportion of the total travel time is attributed to the intersection delay. Especially when the crossroad is congested, the intersection delay might even exceed the travel time on road section. Therefore, in Route Planning Module, in order to meet the optimum objective of the minimum total travel time, intersection delay must be considered in route planning algorithm. Based on the data of the investigation of the traffic volume and delay of the typical crossroads, this paper discusses the ways and means of modeling an Intersection Delay Model for crossroads, which is also applicable for VNS, and demarcates the model with necessary theoretical analysis.Based on the analysis of the temporal complicacy and spatial complicacy of the commonly used algorithms, this paper adopts adjacency list as the data structure for Dijkstra and A* algorithms and successfully improved the performance of the algorithms compared to those which adopts adjacency matrix as the data structure. Afterwards, the paper concentrated on considering one-way road prohibitions and turn penalties as well as the nodal weight which is brought out by the intersection delays. Previous solutions to these problems, such as topology conversion methods and forward-pointed arcs methods, not only have deficiencies of having high temporal and spatial complicacies, but also have shortcomings for the topological data difficult to be formed and be renewed in good time. This paper comes up with an Arc Topology Algorithm to solve one-way road prohibitions and turn penalties problems, and puts forth Azimuth Algorithm and Turn-angle Algorithm to solve nodal weight problem. This paper makes tests in a typical road network in Beijing. Theoretical analysis and practical implementation prove that these algorithms effectively overcome the shortcomings of the previous solutions and greatly improve the computational efficiency. The tests also prove that the algorithms can provide valid route planning solutions under various traffic management conditions.