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
Seongmoon.Kim@FIU.edu, 305-348-6912
Chelsea C. White III
Industrial and Systems Engineering
Georgia Institute of Technology
765 Ferst Drive, Atlanta, GA 30332
cwhite@isye.gatech.edu, 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 Michigan.