Two Papers Just Made Public Transit Routing Algorithms Dramatically Faster

The buffer time problem nobody talks about

But the more interesting finding involves buffer times. In real transit systems, stations often have minimum transfer times. You can't sprint off a train and immediately board another on a different platform. There's a buffer, usually 2-5 minutes depending on the station.

Efficient TD-Dijkstra implementations rely on filtering out dominated connections during preprocessing. If connection A gets you somewhere faster than connection B, you can ignore B. Simple enough. Except this logic breaks when buffer times exist.

Why? Because a passenger already seated on a train doesn't need to respect the buffer. They can continue without waiting. But a transferring passenger must wait. The preprocessing can't distinguish between these two cases, so it sometimes filters out connections that would actually be optimal for seated passengers.

Look, this is the kind of bug that's easy to miss in testing but matters in production. I've seen enough spec sheets to know that edge cases like this are where systems actually fail.

The researchers introduce Transfer Aware Dijkstra (TAD), which scans entire trip sequences rather than individual edges. It's a subtle modification, but it correctly handles buffer times while maintaining the performance advantages over McRAPTOR. Their experiments on London and Switzerland networks show a greater than 2x speedup while producing optimal results on networks with and without buffer times.

Early Pruning: a simple trick with big payoffs

The second paper attacks a different bottleneck. RAPTOR and its variants struggle during the transfer relaxation phase, especially on dense transfer graphs. When you allow unlimited transfers (walking, bikes, e-scooters, whatever), the algorithm has to iterate over many potential inter-stop connections. This gets expensive fast.

In practice, most transit apps deal with this by limiting transfer distances or excluding certain options. That's a pragmatic choice, but it reduces path optimality. You might miss the actually-fastest route because it involved a 12-minute walk the algorithm refused to consider.

The proposed solution is called Early Pruning, and it's almost embarrassingly simple. Pre-sort transfer connections by duration. Then, within the transfer loop, discard longer transfers at a stop once they can't possibly yield an earlier arrival than the current best solution.

That's it. One-time preprocessing, minimal code changes to existing implementations.

The results are substantial:

The exact figures vary by algorithm and network, but the trend is clear. The technique also preserves Pareto-optimality in extended-criteria settings, as long as the additional optimization criteria are monotonically non-decreasing in transfer duration. Which, in plain English, means it works for multi-objective routing (fastest, fewest transfers, cheapest) without breaking anything.

Why this matters beyond academia

Transit routing might seem like a solved problem. Your phone gives you directions. They're usually good enough. Why care about algorithmic improvements?

A few reasons.

First, query time matters at scale. A 57% reduction in routing time means you can serve more users with the same hardware, or provide faster responses on the same infrastructure. For a transit agency running millions of queries daily, that's real money.

Second, the limitation workarounds have real costs. When apps restrict transfer options to maintain performance, they're hiding potentially optimal routes from users. Maybe the fastest way home involves a 15-minute bike share ride that the algorithm never considered. Early Pruning means you can include more options without tanking performance.

Third, multimodal transit is getting more complex, not less. E-scooters, bike shares, on-demand shuttles, autonomous vehicles (eventually). The transfer graphs are only going to get denser. Techniques that scale better matter more over time.

What we still don't know

It's worth noting what these papers don't address. The experiments use London and Switzerland networks, which are well-documented and relatively clean datasets. How these techniques perform on messier real-world data (incomplete schedules, real-time delays, missing stop information) remains unclear.

The buffer time paper also assumes buffer times are known and consistent. In practice, they vary by time of day, by passenger mobility, by how crowded the station is. Whether TAD handles dynamic buffer times is something I couldn't find addressed in the paper.

And while Early Pruning is described as easy to integrate, "minimal code changes" is a relative term. For teams running heavily customized RAPTOR implementations, the integration effort might be non-trivial. The real test is whether transit agencies actually adopt these techniques, and that's a production question, not a research one.

The bigger picture

From my time building hardware, I learned to be skeptical of claims that old approaches are definitively worse than new ones. Sometimes they are. Sometimes the old approach just needed better implementation, or the comparison wasn't fair, or the use case shifted.

These papers are a good reminder that revisiting fundamentals can pay off. Dijkstra's algorithm is from 1956. RAPTOR is from 2012. The assumption that newer means better isn't always true, and the routing research community may have moved on from classical approaches too quickly.

Whether these techniques see widespread adoption depends on factors beyond algorithmic elegance: ease of integration, maintenance burden, compatibility with existing systems. But the performance numbers are hard to ignore. A 2x speedup and 57% query time reduction, while maintaining optimality, is the kind of improvement that actually changes deployment decisions.

The London Underground map on my old office wall showed a system that moves 5 million passengers daily. Somewhere in the infrastructure serving those passengers, routing algorithms are grinding through transfer graphs millions of times. Making that process faster, while finding better routes, is the kind of unsexy improvement that matters more than most people realize.

Sarah Williams · 19 Jun · 3 min