Optimal vehicle routing and scheduling with real -time traffic information.

Abstract

We model the dynamic route determination problem as a Markov decision process (MDP) and examine the value of real-time traffic information to optimal vehicle routing in a non-stationary stochastic network. We present a systematic approach to aid in the implementation of transportation systems integrated with real time information technology (IT). In particular, we develop decision-making procedures and algorithms for determining the optimal driver attendance time, optimal departure times and optimal routing policies under stochastically changing traffic flows in a non-stationary network. This leads to the computational challenge of taking real-time traffic data and transforming them into optimal route decisions. The difficulty is due, in large part, to the amount of data available that possibly contains value for optimal route selection. We present mathematical 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 is achieved by a two-step process. The first is an a priori reduction that may be performed using 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 non-stationary stochastic road network as the trip optimally progresses. We illustrate this reduction process with a numerical example. Lastly, we demonstrate significant advantages when using real-time traffic information by measuring total cost savings and vehicle usage reduction with a numerical evaluation carried out on an urban road network in Southeast Michigan.