Computing Multi-Modal Journey Plans under Uncertainty

Adi Botea, Akihiro Kishimoto, Evdokia Nikolova, Stefano Braghin, Michele Berlingerio, Elizabeth DalyJAIR 2019 · DOI

Abstract

Traditional navigation systems typically assume deterministic transit schedules, leading to fragile journey plans that collapse when connections are missed. This paper, originally published in the Journal of Artificial Intelligence Research, introduces a framework for computing optimal "contingent" journey plans—decision trees that account for the inherent uncertainty of urban transit. By combining a hybrid A/AO search with aggressive state-dominance pruning, the authors demonstrate that reliable multi-modal planning is computationally feasible. Evaluation on real-world data from three European cities shows that contingent plans significantly improve worst-case arrival times while maintaining high computational efficiency.

Introduction

Most navigation applications operate under the assumption of a deterministic world. However, in reality, traffic congestion and operational delays make transit networks stochastic. A "sequential" plan—a single fixed path—is highly susceptible to failure; missing a single tight connection can lead to a total plan collapse.

The challenge lies in multi-modal planning (combining walking, buses, trams, and bikes) under uncertainty. While travelers desire plans that minimize worst-case arrival times, finding these contingent plans (e.g., "Take bus A; if it's late, walk to stop B and take bus C") is computationally expensive. Furthermore, the authors prove that the problem becomes NP-hard when travel time distributions vary over time, such as during the transition from midday to rush hour.

Example of a multi-modal journey network with uncertain arrival and departure times.

Methodology

The authors model the journey as a search within an And/Or state space. In this model, OR nodes represent points of traveler choice (e.g., which bus to board), while AND nodes represent environmental outcomes (e.g., whether a bus was caught or missed). To navigate this space efficiently, the system, named DIJA, employs several novel techniques:

  1. AO* Search Enhancements: The search is guided by "admissible heuristics"—mathematical lower bounds on travel time—to prune suboptimal branches early.
  2. State-Dominance Pruning: If two paths reach the same location, the system discards the inferior one (e.g., later arrival or less remaining walking quota).
  3. Hybrid A/AO Search: This "secret sauce" first runs a fast, deterministic A search. If the resulting plan is sufficiently robust, the search terminates. Otherwise, the A results "warm up" a more complex AO* search.
  4. Lexicographic Optimization: The planner prioritizes minimizing the worst-case arrival time, using expected arrival time as a tie-breaker.

Experimental Results

The DIJA system was evaluated using real-world GTFS (General Transit Feed Specification) data from Montpellier (France), Rome (Italy), and Dublin (Ireland). Stochastic noise was added to simulate realistic delays.

The results indicate that the hybrid search approach outperformed standalone AO by up to 100x on difficult queries. More importantly, contingent plans offered better worst-case arrival times in 15% to 41% of cases compared to standard sequential plans. When these differences occurred, travelers saved an average of 17 to 28 minutes* in worst-case scenarios.

Comparison of sequential and contingent plans, highlighting the superior worst-case arrival times of contingent strategies.

Discussion and Conclusion

A key insight from this research is the "Power of Maybe." A contingent plan can afford to attempt a risky, fast connection because it has a pre-calculated backup, whereas a sequential plan must be conservative to guarantee arrival. The hybrid approach also demonstrates that deterministic search is a powerful heuristic generator for probabilistic problems.

While the system is effective at the city level, future work will focus on scaling to national networks and integrating real-time GPS data for live updates. Ultimately, this work proves that robust, branching journey plans are not only more reliable for travelers but also computationally practical for modern navigation systems.

Summary updated

BibTeX
@article{botea2019computing,
  author = {Adi Botea and Akihiro Kishimoto and Evdokia Nikolova and Stefano Braghin and Michele Berlingerio and Elizabeth Daly},
  title = {{Computing Multi-Modal Journey Plans under Uncertainty}},
  journal = {J. Artif. Intell. Res.},
  year = {2019},
  doi = {10.1613/jair.1.11422},
}
Figure