Adaptive Transit Routing in Stochastic Time-Dependent Networks

Tarun Rambha (), Stephen D. Boyles () and S. Travis Waller ()
Additional contact information
Tarun Rambha: Department of Civil, Architectural and Environmental Engineering, University of Texas at Austin, Austin, Texas 78712
Stephen D. Boyles: Department of Civil, Architectural and Environmental Engineering, University of Texas at Austin, Austin, Texas 78712
S. Travis Waller: School of Civil and Environmental Engineering, University of New South Wales, Sydney, NSW 2052, Australia

Transportation Science, 2016, vol. 50, issue 3, 1043-1059

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.

Keywords: transit routing; stochastic shortest paths; curse of dimensionality; state space reduction; Markov decision process (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2015.0613 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:50:y:2016:i:3:p:1043-1059

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().