The Research On Routing Planning Problem For Vehicle Navigation System That Consider Node Attributes

With the rapid development of China’s economy and living standard of people,carownership is also constantly increasing,it is convenient for people to travel,but brings greatpressure to the traffic at the same time.Especially in big cities,traffic congestion as well asthe increase of traffic accidents and the automobile exhaust pollution caused by the enginewaste is one of the most serious city diseases at present.Intelligent Transportation Systems(ITS) has been widely used to solve the looming problem,and the vehicle navigation systemis the most widely used technique in ITS.But the path planning of the existing vehiclenavigation system as below:At first,it takes the shortest distance from the origin to thedestination as the goal,in fact,the shortest distance path is not necessarily the minimumtravel time path,so it can not meet the requirements of the travel time;Secondly,it onlyconsiders the driving time between intersections on the road ignoring the waiting time and thedifferent consuming time for different turning at intersection,which is not appropriate for theactually situation of city traffic.In this paper,we take the minimum driving time of the citytraffic as the goal and study the network shortest path problem that considers the nodeattributes(weight or cost),the main work includes:Based on the assumptions that network diagram is time invariant and the value of eachedge and node in the network graph are deterministic,we establish the mathematical modelfor Time Invariant and Deterministic Network shortest path problem that considers nodeattributes(weight or cost),through the analysis of the problem we proved that the solution ofthe problem has optimal sub structured;Based on dynamic programming method,weproposed the optimal path search algorithms-Reverse Order Labeling Algorithm,then provedthat the algorithm can provide the optimal solution for the problem in polynomial timetheoretically,and the time complexity of the algorithm is O(N.|E|+|V|).Based on the assumptions that network diagram is time-varying and the weight of eachedge and node in the network graph are deterministic numerical during any time period,weestablish the mathematical model for Time-varying and Deterministic Network shortest pathproblem that considers node attributes(weight or cost),in order to clearly indicate thecharacteristic that nodes and edges have different weights in the network in different period oftime,we proposed the vector label method.In terms of the search algorithm, we extend theReverse Order Labeling Algorithm to Time-varying and Deterministic Network to solve theshortest path problem which considers node attributes (weight or cost),and points out thatthe time complexity of the algorithm is O(I.(N.|E|+|V|)).Based on the assumptions that network diagram is time invariant and the weight of eachedge and node in the network graph are finite number of discrete random variables,weestablish the mathematical model for the Time Invariant and Stochastic Network shortest path problem that considers node attributes(weight or cost).Firstly,for the shortest path problemdoes not consider the changes in real-time data,we extend the Reverse Order LabelingAlgorithm to Time Invariant and Stochastic Network to design the optimal path searchalgorithm,and the time complexity of the algorithm is O (N.(M+K).|E|+|V|).Inaddition,we also provide the improved Q-method to solve this problem,and proved the timecomplexity of the improved Q-method algorithm isO ((K+M+N). N.|E|2).According tothe needs of dynamic vehicle navigation in the process of travel,we also provide the optimalpath search algorithm for the shortest path problem that considers the real-time data,thesimulation result also verifies the effectiveness of the algorithm.