Adaptive transit routing in stochastic time-dependent networks

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Tarun Rambha - , University of Texas at Austin (Author)
  • Stephen D. Boyles - , University of Texas at Austin (Author)
  • S. Travis Waller - , University of New South Wales (Author)

Abstract

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.

Details

Original languageEnglish
Pages (from-to)1043-1059
Number of pages17
JournalTransportation Science
Volume50
Issue number3
Publication statusPublished - 2016
Peer-reviewedYes
Externally publishedYes

External IDs

ORCID /0000-0002-2939-2090/work/141543796

Keywords

Keywords

  • Curse of dimensionality, Markov decision process, State space reduction, Stochastic shortest paths, Transit routing