Research On Shortest Path Algorithms In Dynamic And Stochastic Traffic Networks

Advanced Traveler Information Systems (ATIS) and Advanced Driver’s Route Guidance System (ADRGS) are the subsystems of Intelligent Transportation Systems (ITS) which are designed to deliver the traffic and route information directly to travelers. Based on such information, travelers can make better decisions about route and departure time. One of the key issues of providing route guidance information is how to effectively generate reliable route information.The dynamic and stochastic shortest path problem (DSSPP) is defined as finding the expected shortest path in a traffic network where the link travel times are modeled as a continuous-time stochastic process. The objective of this paper is to to examine the properties of the problem and identifies what effects different spatial and temporal distribution of traffic have towards vehicle arrival time, link travel time and travel paths on these time-dependent networks, and to use it as a consultation for travelers’route planning. When it comes to the design of dynamic and stochastic traffic information, time range and the corresponding probability are proposed to present dynamic and stochastic network.This paper proposes two procedures to determine possible travel routes and their associated probabilities in a time-dependent and stochastic road network. The first algorithm generates the range of possible travel time of the suggested path based on the algorithm proposed by Miller-Hooks and Mahmassani (1998).When vehicles are traveling in a dynamic and stochastic road network, the travel cost could be divided into two parts, link travel time and intersection delay. Most of the shortest path algorithms assume that there is no costs or prohibitions associated with intersection delays, but the intersection delays might be the dominant factor when calculating the shortest paths in a congested urban road network. The second algorithm aims at developing time-dependent shortest path algorithms with intersection delays. The method of calculating intersection delays are average delays considering drivers’turn selection under signal control .The delay under signal control could reflect the impact of signal and variations of flow. This algorithms could reflect the dynamic characteristics of traffic and application to the environment of ITS in the future.