The task of finding the shortest path between two nodes in a graph is well-studied in computer science literature. The well-known Dijkstra algorithm finds the shortest path from a source to all other destinations. In this post, we explain how did we handle routing in the public transportation network for one of our clients at Communere.

Public transit network

Public transportation differs from other networks. The main reason is that the edges are available only at certain times. For example, consider a bus that leaves stop X at 08:00. The edge between stop X and the next stop is available only at 08:00. This proves to make routing much more difficult. The following questions must be considered in this scenario.

• How long should we wait at a stop?
• How to handle the dynamic nature of the network?
• Will there be any path from my next stop?

These problems make traditional routing algorithms inefficient in this case.

RAPTOR algorithm

Round-Based Public Transit Routing (RAPTOR) is a temporal pathfinding algorithm developed by Microsoft. The original publication of the algorithm by Delling, et al. is available here. This algorithm was developed to address the mentioned problems. It is widely different from Dijkstra. It doesn't even need a Min-Heap to prioritize the shortest paths!

Algorithm Intuition

In public transit network, each means of transportation moves along its predefined route. Unlike general-purpose routing algorithms like Dijkstra, RAPTOR utilizes this property to find the optimal path. To illustrate the difference, consider the following scenario.

The graph below depicts a public transit network and its availability times. Each colored line represents a path that a bus takes. The red line starts from stop 1 at 08:00 and arrives at stop 7 at 10:30. Stops 2, 3, 4, and 5 are the intermediate stops in this route. Each intermediate stop is 30 minutes away from its neighboring stops in the route.

Assume that we want to find the earliest arrival time for stop 7 given that we are at stop 1 at 7:45. The first thing would be to find the earliest leaving bus (or other means of transportation). In this case, there is only one bus leaving at 08:00 so we have a total waiting time of 15 minutes at stop 1.

Once we catch a bus, the algorithm will traverse that route to the end. Put simply, once you hop on the bus at stop 1, the algorithm will sequentially traverse all the stops that are on that route. And, it will record the arrival time for each stop. So, after traversing the first route, the algorithm will have the following records.

• Best arrival time for stop 1: 08:00
• Best arrival time for stop 2: 08:30
• Best arrival time for stop 3: 09:00
• Best arrival time for stop 4: 09:30
• Best arrival time for stop 5: 10:00
• Best arrival time for stop 7: 10:30

With this information, the algorithm can stop and report the earliest arrival time for the desired location is 10:30. This is a valid answer if the desired number of interchanges is 0. However, there may be a better path by changing lines.

The algorithm works iteratively. Routes with 0 interchange are considered in the first iteration. The second iteration builds upon the knowledge obtained from the first iteration and considers routes with 1 interchange. More specifically, from the first iteration, the algorithm knows that the earliest arrival time of stop 2 is 08:30. Therefore, it starts the pathfinding routing the same way as before. The only exception is that it starts from stop 2 at time 08:30.

To clarify things a little more let's trace the second iteration of the algorithm. In the first iteration, the algorithm marks any stop that has been improved in terms of arrival time. Since each stop's arrival time is initially set to infinity, all stops in the first iteration are improved. In the second iteration, the algorithm considers the available trips from stops 2, 3, 4, 5, and 7. Let's trace the blue trip from stop 2. Given that we arrive at stop 2 at 08:30, we can board the blue route and reach stops 6 and 5. The respective time for arrival is 08:40 and 09:00. As you can see, the arrival time for stop 5 improves. After the second iteration, the best arrival time for each stop is as follows.

• Best arrival time for stop 1: 08:00
• Best arrival time for stop 2: 08:30
• Best arrival time for stop 3: 09:00
• Best arrival time for stop 4: 09:30
• Best arrival time for stop 5: 09:00 (follow the red line to stop 2, then switch to the blue line)
• Best arrival time for stop 6: 08:40 (follow the red line to stop 2, then switch to the blue line)
• Best arrival time for stop 7: 09:30 (follow the red line to stop 3, then switch to the green line)

The iteration continues until no improvement can be made or the algorithm hits the maximum number of iterations.

Another important aspect is the ability to walk between stops. RAPTOR does not compute the walking time between stops. This is a brilliant abstraction as any routing algorithm can be used to find the walking times.

Performance

RAPTOR has become the de-facto algorithm for public transit routing. Most of the other algorithms need preprocessing stage to have an acceptable performance; this is not the case for RAPTOR. Most of the queries are almost instant in small networks. This algorithm proved to be more than three times faster than the modified versions of Dijkstra.

Footnotes

• The original paper is vague in some aspects. And, it also has minor bugs in its pseudo code. If you are stuck, this link provides a better explanation.
• There is a python implementation available here.