Large-scale transit itinerary planning under uncertainty

In this paper, we study the transit itinerary planning problem with incorporation of randomness that arises in transit vehicle arrival/departure and passenger transfer. We investigate two approaches to address the uncertainty: a minmax robust approach and an expectation-based probabilistic approach. We adapt a two-phase framework to mitigate computational challenges in large-scale planning problems. In phase I, we compute candidate route connections offline and store them into a database. Although expensive computation is required in phase I, it is typically performed only once over a period of time (e.g., half a year). Phase II takes place whenever a request is received, for which we query candidate route connections from the database, build a stochastic shortest-path model based on either approach listed above, and solve the model in real time. With phase I, computational requirement in phase II is substantially reduced so as to ensure real-time itinerary planning. To demonstrate the practical feasibility of our two-phase approach, we conduct extensive case studies and sensitivity analyses based on a large real-world transit network.