Adaptive transit routing in stochastic time-dependent networks
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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 language | English |
---|---|
Pages (from-to) | 1043-1059 |
Number of pages | 17 |
Journal | Transportation Science |
Volume | 50 |
Issue number | 3 |
Publication status | Published - 2016 |
Peer-reviewed | Yes |
Externally published | Yes |
External IDs
ORCID | /0000-0002-2939-2090/work/141543796 |
---|
Keywords
ASJC Scopus subject areas
Keywords
- Curse of dimensionality, Markov decision process, State space reduction, Stochastic shortest paths, Transit routing