How we sped up Public Transit Routing around the globe

When you search for the fastest way across town in a local transit app, the answer is often computed by OpenTripPlanner (OTP), the open-source engine powering everything from Portland's transit app to Norway's national journey planner. Because it excels at combining public transit schedules with walking, cycling, and ridesharing, its users span public transit agencies, national governments, and private mobility companies.

We found a change that makes OTP's transit search up to two times faster, and we got it merged into the engine itself, enabled by default, so every one of those deployments benefits.

A planner the world relies on

OTP is production infrastructure, not a research prototype. It provides route planning for the agencies and operators below.

The architecture, and its bottleneck

OpenTripPlanner, in its second version, uses the RAPTOR algorithm to find the fastest journey from A to B. RAPTOR is the most popular open-source transit algorithm: besides OTP, it powers Bing Maps, R5, Solari, and many other production services.

The idea behind it mirrors how people plan their daily travel. Each time we go somewhere, we try to avoid switching between vehicles, and the fastest route is usually a direct trip. RAPTOR follows the same instinct and works in rounds, where each round adds one more trip to the journey. The first round finds everywhere you can reach on a single direct ride, with no transfers at all. The second round allows one transfer, so it now knows every stop you can reach by changing once. The third allows two, and so on. Each round only looks at routes that touch the stops that improved in the previous round.

Elegant as it is with vehicles, RAPTOR is naive about the transfers between stops: it simply loops over every one of them. A decade ago that was fine, because most transfers were on foot and people don't like walking far, so developers often capped the transfer radius to keep that loop small. But new urban mobility changes the picture. With e-scooters and bicycles now filling the gaps between stops, there is no longer a good reason to shrink transfer distances, and the loop explodes.

The catch is that most of those connections are useless in practice. But we can't simply ignore them, because any one of them might turn out to be part of the optimal journey.

Early Pruning

We proposed a method to speed up the RAPTOR architecture without significant changes to the codebase of the engines that use it. The method, which we call Early Pruning, is simple: keep each stop's transfer connections sorted from shortest to longest. During the search, stop checking the moment a connection would arrive at or after the best arrival time already known for the destination. Because the list is sorted, every remaining connection is even longer and is guaranteed to miss too, so the whole tail can be skipped without being examined.

The idea is simple, but it gives a real boost in practice.

How it affects OpenTripPlanner

We added Early Pruning to the OpenTripPlanner codebase on 1 June 2026. It is enabled by default and ships in the 2.10 release. Remarkably, the whole change took just 467 lines of code (PR #7665).

OTP runs a continuous performance benchmark across a varied set of networks, from a single metropolitan agency up to country-scale instances. After the change landed, routing times dropped across the board.

The drop was large: in many places, the targeted routing phase became up to two times faster. Everywhere except one demand-responsive network, sorting a list and adding a single early-exit test made one of the world's most-deployed journey planners meaningfully faster.

The research behind it

Early Pruning came out of the ongoing PhD research of our founder, Andrii Rohovyi, at UNSW Sydney under the supervision of Professor Toby Walsh, with co-author Abdallah Abuaisha (Monash University). The work has been accepted for the World Conference on Transport Research (WCTR) 2026; the full method and experiments are available on arXiv.

It is a good example of how we work at Postdata: rigorous, research-backed algorithm design that ships as a small, low-risk change to real production systems that millions of travellers depend on every day.

References

1. Rohovyi, Andrii, Abuaisha, Abdallah, Walsh, Toby. Early Pruning for Public Transport Routing. arXiv preprint arXiv:2603.12592, 2026.
2. Duc-Minh Phan, Laurent Viennot. Fast Public Transit Routing with Unrestricted Walking Through Hub Labeling. Analysis of Experimental Algorithms, Special Event, SEA² 2019, 2019.
3. Daniel Delling, Thomas Pajor, Renato F. Werneck. Round-Based Public Transit Routing. Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX), 2012.
4. Delling, Daniel, Dibbelt, Julian, Pajor, Thomas. Fast and Exact Public Transit Routing with Restricted Pareto Sets. Proceedings of the 21st Workshop on Algorithm Engineering and Experiments (ALENEX'19), 2019.
5. Julian Dibbelt, Thomas Pajor, Ben Strasser, Dorothea Wagner. Connection Scan Algorithm. ACM Journal of Experimental Algorithmics, 2018.
6. Hart, Peter E., Nilsson, Nils J., Raphael, Bertram. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 1968.
7. Tung, Chi Tung, Chew, Kim Lin. A multicriteria Pareto-optimal path algorithm. European Journal of Operational Research, 1992.
8. Sascha Witt. Trip-Based Public Transit Routing. Algorithms, ESA 2015, 2015.