Least Travel Time Paths In Stochastic And Time-Varying Transportation Networks Considering The Time Consumption Of Nodes

In recent years,along with the development of our country economy and the improvement of people's living standard,the number of national cars escalates and the traffic in some Chinese cities becomes more and more crowded.The atmosphere pollution for the automobile emission become very serious day by day because of the waste of the gas caused by automobiles' moving slow in the streets.People strongly desire that Intelligent Transportation System and Car Navigation System can plan a shortest path as quickly as possible so that they can get to the destination as early as possible.So traffic managers and the industry researchers pay close attention to the route planning and real time navigation for driving automobile.However,there are still some problems in the usual route planning which is provided by the existed car navigation system.Firstly,the existed route planning aims to find the shortest physical distance between two nodes,rather than the least travel time.Secondly,it does not attach importance to the time consumed at the intersections by automobiles.The time vehicles spend to pass through the intersections in different ways is different.In other words,when vehicles arrive at a intersections,vehicles choose to go straight,turn left,turn right or turn around,the time consumed at the intersections are diverse.Therefore,we can not attribute it to the corresponding arcs.Thirdly,for network is time-varying and stochastic,the exited route planning does not take it seriously enough.For all the above reasons and more,this thesis studies the least expected travel time path problem in stochastic and time-varying networks considering the time consuming of nodes,the main work is as follows:Based on the assumptions that the road network is time-varying and the time consumed by a vehicle on any an arc or at any a node at different time is a discrete random variable which takes finite values,the thesis establishes the mathematical models of the problems such as the general least expected travel time path planning problem,certain departure time least expected travel time path planning problem with the certain departure time and the least expected travel time path planning problem with the latest arrival time constraint.And a new algorithm,Reverse Order Labeling Algorithm,based on the dynamic programming method,is put forward to solve the above problems.In order to facilitate storing data and computing,the thesis introduces the vector label to describe time consumed by the car passing through the arcs and intersections at different time.By analyzing the thought and process of the algorithm,the thesis concludes that the time complexity of the algorithm is O(I·(N·(M+K)~2·|E|+|V|)).In view of time-varying road condition in the driving process,the thesis studies the real-time route guidance problem and proposes an optimal path search algorithm to solve the problem,and give example to testify the validity of the algorithm.Based on the assumptions that the road network is and the time consumed by a vehicle on any an arc or at any a node at different time is a continuous random variable which obey triangular distribution,the thesis establishes the mathematical models of the problems such as the general least expected travel time path planning problem,certain departure time least expected travel time path planning problem with the certain departure time and the least expected travel time path planning problem with the latest arrival time constraint in the time-varying and stochastic road network.Then the thesis promotes the Reverse Order Labeling Algorithm to the continuous time-varying random networks,getting the optimal path search algorithm to solve the above problems.