Adaptive Transit Routing in Stochastic Time-Dependent Networks

The authors 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. The authors 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.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01630857
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Mar 28 2017 5:08PM