Computation and implementation of dynamic route guidance algorithms

Regularly updated traffic information is increasingly available to the driver through advisory radios, dynamic message signs, cell phones and websites. However, traffic information through them is rarely used for driver's route guidance because, even after obtaining congestion information at several locations, the driver should still choose the good route with intuition. Recently, more and more vehicles install on-board navigation systems for route guidance. However, the current on-board navigation systems do not consider real-time traffic congestion information for dynamic route guidance and, assuming no congestion, they just provide static good route, which may not be desirable in high congestion situations. Therefore, on-board navigation systems need an efficient dynamic route guidance algorithm integrated with real-time traffic information. Routing vehicles based on real-time traffic information has been shown to significantly reduce travel time, and hence, cost, in high-volume traffic situations. A Markov decision process (MDP) model provides the optimal routing policies, which dynamically reroute the vehicle while en-route based on real-time traffic information. However, due to the "curse of dimensionality", taking real-time traffic data and transforming them into optimal route decision with an MDP model is a challenge in both computation and implementation. In this paper, we develop a heuristic dynamic route guidance algorithm, which provides good suboptimal solutions that can be computed quickly by on-board navigation systems. For this algorithm we incorporate deterministic A * algorithm with randomly changing real-time traffic information and obtain suboptimal routing policies in a non-stationary stochastic road network. With actual traffic data on an actual road network in southeast Michigan, we compare performance measures such as solution quality and computation time between our new model and an MDP model.