Early Pruning for Public Transport Routing

This paper introduces "Early Pruning," a low-overhead technique that significantly accelerates public transport routing algorithms like RAPTOR by pre-sorting and discarding suboptimal transfer connections, thereby reducing query times by up to 57% without compromising path optimality and enabling more comprehensive multimodal journey planning.

The Gist

Imagine you are trying to find the fastest way to get from your home to a friend's house in a busy city. You have a map app that shows you buses, trains, walking paths, bike lanes, and even e-scooter routes.

In the past, these apps had a hard time handling all these options. If you wanted to see every possible way to get there (including walking to a different bus stop, taking a bike, then hopping on a train), the app would get overwhelmed. It would try to check every single path, even the ones that were obviously too slow, causing the app to freeze or take too long to give you an answer.

This paper introduces a clever trick called Early Pruning to fix that. Here is how it works, explained simply:

The Problem: The "Endless Hallway" of Options

Think of a bus stop as a hallway with many doors leading to other stops.

• Door A leads to a stop 2 minutes away.
• Door B leads to a stop 5 minutes away.
• Door C leads to a stop 9 minutes away.

When the computer is trying to find the best route, it usually walks through every single door to see where it leads, even if it already found a path that gets you to your destination in 10 minutes. If it checks Door C (9 minutes) and realizes that adding that time makes the total trip too long, it's too late—it wasted time checking that door in the first place.

The Solution: The "Sorted List" Trick

The authors realized that if you organize the doors by how long they take (shortest time first), you can stop checking as soon as you know it's pointless.

Imagine you are a detective looking for a suspect. You have a list of suspects sorted by height, from shortest to tallest.

1. You know the suspect is taller than 6 feet.
2. You check the first person (5 feet). Too short.
3. You check the second person (5'5"). Too short.
4. You check the third person (6'1"). Bingo! You found a match.

But here is the magic of Early Pruning:
If you are looking for someone shorter than 5 feet, and you check the first person (5 feet) and realize they are already too tall, you don't need to check the rest of the line. Since the list is sorted, everyone else is even taller! You can just close the list and move on.

How It Works in the App

1. Preparation (One-time setup): Before you even ask the app for directions, it sorts all the walking and transfer paths at every stop from "fastest" to "slowest." This takes less than a second and only needs to be done once.
2. The Search: When you ask for a route, the app checks the fastest paths first.
3. The Cut-off: As soon as the app sees a path that is slower than the best route it has already found, it says, "Okay, I don't need to check any more paths from this stop because they will all be even slower!" It cuts off the rest of the search immediately.

Why This Matters

• Speed: The paper tested this on real transit networks in London and Switzerland. It made the apps up to 57% faster. That means a 4-second wait becomes a 2-second wait.
• More Options: Because the app is faster, city planners can finally include more options without making the app slow. They can let you see routes that involve walking further, taking an e-scooter, or transferring in more complex ways.
• Better for Everyone: This is especially helpful for people living in suburbs or small towns where direct buses are rare. Instead of just saying "No bus here," the app can quickly figure out, "Walk 10 minutes to the next town, take a bike, then catch a train."

The Bottom Line

Early Pruning is like teaching a GPS to stop looking at dead ends the moment it realizes they are dead ends. It doesn't change the destination or the route; it just stops the computer from wasting time on paths that are guaranteed to be too slow. This makes your journey planner faster, smarter, and able to show you more creative ways to get around your city.

Technical Summary

1. Problem Statement

Public transport routing algorithms, particularly those based on RAPTOR (Round-Based Public Transit Routing), face significant performance bottlenecks during the transfer relaxation phase.

• The Bottleneck: As transit planners incorporate diverse mobility modes (walking, cycling, e-scooters) to support Mobility-as-a-Service (MaaS), the transfer graph becomes increasingly dense. The algorithm must iterate over a vast number of potential inter-stop connections.
• Current Limitations: To maintain sub-second response times, practitioners often artificially limit transfer distances or exclude certain modes. This compromises path optimality and restricts the multimodal options available to travelers, particularly in areas with sparse direct transit coverage.
• The Gap: Existing pruning techniques (like target pruning) check if a specific label is dominated but do not exploit the ordering of transfer edges to terminate the iteration loop early.

2. Methodology: Early Pruning

The authors propose Early Pruning, a low-overhead technique designed to accelerate the transfer relaxation phase without sacrificing solution optimality.

• Core Mechanism:

  1. Pre-sorting: Before query execution, all outgoing transfer edges at every stop are pre-sorted by their duration (transfer time) in non-decreasing order.
  2. Pruning Rule: During the routing process, when the algorithm iterates through outgoing transfers from a stop $s$ to a target $t$:
     • Let $\tau_k(s)$ be the arrival time at $s$ in the current round.
     • Let $\tau^*(t)$ be the current best known arrival time at the target.
     • If the arrival time via the current transfer edge $e_i$ (i.e., $\tau_k(s) + \tau(e_i)$) equals or exceeds $\tau^*(t)$, the iteration stops immediately.
  3. Guarantee: Because edges are sorted by duration, all subsequent edges $e_j$ (where $j > i$) will have $\tau(e_j) \ge \tau(e_i)$. Therefore, they cannot yield an earlier arrival at the target, making further computation futile.

• Extension to Multi-Criteria:

  • For algorithms optimizing multiple criteria (e.g., McRAPTOR, BM-RAPTOR), the method uses Pareto dominance rather than scalar comparison.
  • If a new partial path is already dominated by an existing path to the target in the Pareto sense, and the transfers are sorted by walking duration, the algorithm prunes that path and all subsequent longer transfers, as they cannot improve the criteria vector.

• Preprocessing Overhead:

  • The sorting is a one-time preprocessing step.
  • It is delay-robust: It does not need to be recomputed when timetables change (unlike ULTRA shortcuts), only when the transfer graph topology changes.
  • Sorting time is negligible (under 600 ms for large networks).

3. Key Contributions

1. Novel Pruning Technique: Introduction of Early Pruning, which exploits edge ordering to terminate transfer loops early, distinct from standard label-based pruning.
2. Theoretical Correctness: Proof of correctness for both single-criterion (earliest arrival) and extended-criterion (multi-objective) settings.
3. Broad Applicability: Demonstration that the technique integrates seamlessly with six major RAPTOR variants:
   • RAPTOR, ULTRA-RAPTOR
   • McRAPTOR, ULTRA-McRAPTOR
   • BM-RAPTOR, UBM-RAPTOR
4. Policy Implications: Analysis of how algorithmic speedups translate to practical transport planning benefits, such as enabling larger transfer radii and richer multimodal options without additional hardware.

4. Experimental Results

The authors evaluated the method on two real-world transit networks: Switzerland and London. They tested against the Karlsruhe Institute of Technology (KIT) implementations of the algorithms.

• Performance Gains:
  • RAPTOR: Query time reduced by 21.7% (Switzerland) and 33.9% (London).
  • McRAPTOR: Query time reduced by 45.1% (Switzerland) and 56.9% (London).
  • BM-RAPTOR: Query time reduced by 6.6% to 16.0%.
  • ULTRA Variants: Smaller gains (1.6% – 13.6%) because ULTRA precomputes shortcuts, resulting in fewer edges to prune compared to dense transitive graphs.
• Correlation with Density: A statistically significant positive correlation ($r \approx 0.62$) was found between graph density and speedup. Denser graphs (more transfer options) benefit more from Early Pruning.
• Preprocessing Cost: Sorting edges took between 24 ms and 567 ms, a negligible cost compared to the query time savings.
• CSA Algorithm: The technique was tested on the Connection Scan Algorithm (CSA) but yielded no practical improvement due to CSA's smaller memory cache and different access patterns.

5. Significance and Implications

• Operational Efficiency: A 10–30% reduction in query time allows transit agencies to handle millions of daily queries with existing server infrastructure, reducing energy costs and latency.
• Enhanced User Experience: Faster algorithms enable planners to:
  • Increase transfer distance thresholds (e.g., from 4 to 9 minutes) to capture more realistic walking/cycling connections.
  • Include complex multimodal options (e-scooters, shared bikes) in real-time without slowing down the planner.
  • Provide multi-criteria results (e.g., balancing cost vs. time) within interactive response times (<2 seconds).
• Equity and Accessibility: By making complex routing computationally feasible, the technique helps passengers in outer suburbs and smaller towns discover viable multimodal alternatives to private cars, supporting sustainability goals.
• Robustness: Unlike shortcut-based methods (ULTRA), Early Pruning is robust to real-time schedule changes (delays/cancellations) because it relies on static edge sorting rather than timetable-dependent precomputation.

Conclusion

Early Pruning offers a generalizable, low-overhead optimization for public transport routing. By simply sorting transfer edges, it significantly accelerates pathfinding in dense, multimodal networks, enabling more sophisticated, equitable, and sustainable transport planning without requiring new hardware.