Groupe d’études et de recherche en analyse des décisions

Application of Time-Dependent, Stochastic Shortest Paths for Improved Transit Itinerary Planning

Mark D. Hickman Université de la Colombie-Britannique, Canada

The shortest path problem is rich in both applications and efficient solution algorithms. However, the traditional approach, using deterministic arc costs or times, may be only a simplified model of the true underlying costs or times. In this discussion, we examine the field of public transportation in which the underlying travel times in the network behave in both stochastic and time-dependent ways. For this type of problem, many of the traditional shortest path techniques are no longer valid. We will give a brief introduction to the stochastic and time-dependent shortest path problem and describe some of the recent research in this area.

We will also discuss a specific application to generate passenger itineraries. In this problem, a transit passenger seeks a single path from their origin to their destination, before taking a trip. Rather than using the schedule, one might instead make use of historical data on the actual travel times of vehicles in the network, to better capture the inherent uncertainty in itinerary planning. This leads to one instance of the stochastic and time-dependent shortest path problem. We describe this application and propose a solution technique using the notion of stochastic dominance. The potential advantages of this problem formulation, when compared with traditional shortest path methods, are outlined. An example using data from SunTran, the transit agency in Tucson, Arizona, is used to illustrate this technique.