Adaptive Transit Routing in Stochastic Time-Dependent Networks

We define an adaptive routing problem in a stochastic time‐dependent transit network in which transit arc travel times are discrete random variables with known probability distributions. We formulate it as a finite horizon Markov decision process. Routing strategies are conditioned on the arrival time of the traveler at intermediate nodes and real‐time information on arrival times of buses at stops along their routes. The objective is to find a strategy that minimizes the expected travel time, subject to a constraint that guarantees that the destination is reached within a certain threshold. Although this framework proves to be advantageous over a priori routing, it inherits the curse of dimensionality, and state space reduction through preprocessing is achieved by solving variants of the time‐dependent shortest path problem. Numerical results on a network representing a part of the Austin, Texas, transit system indicate a promising reduction in the state space size and improved tractability of the dynamic program.