State Space Reduction for Non-stationary Stochastic Shortest Path Problems with Real-Time Traffic Information

Mark E. Lewis
Industrial and Operations Engineering Department
University of Michigan
1205 Beal Avenue
Ann Arbor, MI 48109-2117

Seongmoon Kim

Department of Industrial and Systems Engineering

Florida International University

10555 W. Flagler Street / (EC 3100), Miami, FL 33174, 305-348-6912


Chelsea C. White III

Industrial and Systems Engineering

Georgia Institute of Technology

765 Ferst Drive, Atlanta, GA 30332, 404-894-0235


Routing vehicles based on real-time traffic information has been shown to significantly reduce travel
time, and hence cost, in high-volume traffic situations. However, taking real-time traffic data
and transforming them into optimal route decisions is a computational challenge. We model the
dynamic route determination problem as a Markov decision process (MDP) and present procedures
for identifying traffic data having no decision-making value. Such identification can be used to
reduce the state space of the MDP, improving its computational tractability. This reduction can
be achieved by a two-step process. The first is an a priori reduction that may be performed using
a stationary, deterministic network with upper and lower bounds on the cost functions before the
trip begins. The second part of the process dynamically reduces the state space further on the nonstationary
stochastic road network as the trip optimally progresses. We demonstrate the significant
computational advantages of the introduced methods based on an actual road network in southeast