I was playing around with a transit trip planning algorithm to estimate travel times on public transit in Ottawa when the algorithm gave me an interesting result: a 16-hour journey for a trip that should only take about an hour. At first I thought I had made a mistake when implementing the algorithm, but it turned about to be an interesting edge case instead.

The Algorithm

The algorithm that I implemented is the Round-Based Public Transit Optimized Routing algorithm, or RAPTOR for short. The algorithm is described in a paper published by Microsoft Research¹, however to help give some background on the problem I’ll give a simplified explanation of how the algorithm works.

Given the schedule for a public transit system, RAPTOR can generate a set of travel plans between an origin and destination stop. When coming up with the set of travel plans, the algorithm tries to balance between the number of transfers that need to be made and the total duration of the journey.

The resulting set of travel plans is called “pareto-optimal”, meaning that the parameters in each result can not be improved without making at least one of the other parameters worse. In this case that means the first travel plan will require the fewest transfers, but each plan that follows will have a shorter travel time at the cost of needing to make additional transfers.

As the name suggests, RAPTOR operates in what the paper calls “rounds”. In oversimplified terms: RAPTOR starts with the origin stop and in each round it tries to find an earlier arrival time at every stop that was visited in the previous round. This repeats until the arrival time at every stop can not be improved any further, meaning that the algorithm has found the fastest possible way to reach every stop.

These rounds are where the pareto-optimal property of the results comes from. Each round essentially counts as a transfer between routes or between stops, but it leads to faster ways to get to the destination stop.

The Edge Case

Ottawa has a somewhat unique rapid transit network that has historically been focused on buses and only recently has the central part of the network been upgraded to a light rail line. This means that many of the rapid transit bus routes that used to run directly from the outer suburbs into the Downtown core now feed into the light rail system and a transfer must be made.

When a rail line closes overnight in most cities, the trains are replaced by a night bus that acts as a direct replacement for the trains. In Ottawa, this isn’t the case because the light rail line is still fairly short. Rather than run a short replacement night bus, those feeder rapid transit routes are instead extended directly into the Downtown just like they did before the light rail system opened.

For example: leaving at 10:00AM on a weekday to get from the suburb of Barrhaven to the Downtown core requires taking three different routes (i.e. making two transfers). (1) A local bus to get to a rapid transit station, (2) the rapid transit feeder route, and finally (3) the light rail line to get into the Downtown core. Overnight though, this changes as the light rail system closes and the feeder bus is extended to provide a direct ride into the Downtown.

Thinking back to the way RAPTOR generates trip plans, notice that the extended overnight route means that one less transfer is required to complete the trip. This means that you can complete the entire journey with a single transfer if you were to wait until 1:00AM for the more direct bus. Because there is no faster way to reach the destination while only making a single transfer, this still satisfies the pareto-optimal property of the algorithm and makes this a valid result.

What does this mean, actually?

RAPTOR is a very clever algorithm, but it isn’t very “smart” per se. It does a very good job of finding the fastest way to get from stop A to stop B given the constraints of transfers and travel time, but it clearly doesn’t understand that waiting 15 hours for a bus isn’t something people do.

In practice this just means that these kinds of edge cases would need to be taken into account when building a trip planning app that uses RAPTOR. A user might be very confused if an app suggested a travel plan that takes so long to complete.

More interestingly though, I think the interaction between RAPTOR and Ottawa’s transit network gave a unique glimpse into the inner workings of the algorithm. I first learned about this algorithm two years ago, but I had always struggled to form an intuition about its workings until exploring this edge case. I think that made this worth sharing.