Adaptive transit routing in stochastic time-dependent networks

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

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

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

OriginalspracheEnglisch
Seiten (von - bis)1043-1059
Seitenumfang17
FachzeitschriftTransportation Science
Jahrgang50
Ausgabenummer3
PublikationsstatusVeröffentlicht - 2016
Peer-Review-StatusJa
Extern publiziertJa

Externe IDs

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

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

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