Adaptive routing in schedule based stochastic time-dependent transit networks

In this thesis, an adaptive transit routing (ATR) problem in a schedule based stochastic time-dependent transit network is defined and formulated as a finite horizon Markov Decision Process (MDP). The transit link travel times are assumed to be random with known probability distributions. Routing strategies are defined to be conditional on the arrival times at intermediate nodes, and the location and arrival times of other buses in the network. In other words, a traveler in the network decides to walk, wait or board a bus based on the real time information of all buses in the network. The objective is to find a strategy that minimizes the expected travel time, subject to constraints that guarantee that the destination is reached within a certain threshold. The value of the threshold was chosen to reflect the risk averse attitude of travelers and is computed based on the earliest time by which the destination can be reached with probability 1. The problem inherits the curse of dimensionality and state space reduction through pre-processing is achieved by solving variants of the time dependent shortest path problem. An interesting analogy between the state space reduction techniques and the concept of light cones is discussed. A dynamic program framework to solve the problem is developed by defining the state space, decision space and transition functions. Numerical results on a small instance of the Austin transit network are presented to investigate the extent of reduction in state space using the proposed methods.