This post is a brief follow up to the original RAPTOR transit routing blog post I wrote a few days ago. Again, the post and this one are based on this paper, by MSR. This post is in response to the various optimizations that were listed in the paper under section “3.1 Improvements.”
This post covers the optimizations as they are implemented in my code. It then remarks on the results, which I found to be disappointing. Basically, because each iteration causes a great deal of fan out, caching does not really help. Early iterations do not have a large number of qualifying stops but later iterations due, so cached stops only represent a small fraction of an every-growing number of qualifying stops to evaluate.
I hope my documenting this will help expose my methods in such a way that someone might see if there’s something else I am missing from the paper that might be used to increase the performance of this method. I do note that each iteration could easily be parallelized and that this would speed up each iterations runtime linearly. I can explore that, perhaps, in a later post.
Suggested optimizations summary
The improvements mentioned were the following:
- skip trips/routes that can’t be reached from a given stop on a
kth round (a round being a transfer count step)
- keep track of what stops have recently been updated (in the last
kth round) and only check those for new trips
- do not look at all stops in a trip; just look at the one with the earliest arrival
- prune stops for just the earliest arrival
Updates to code
I updated the original notebook with this version, hosted as a Gist. This version introduces those key optimizations by introducing an object that does a more complete job of managing the state of each stop, instead of just the earliest arrival time to each.
The code, shown below, allows for some simple put/get actions, as well as checks for when to overwrite a stop. The stop preceding trips are also tracked, so you can see what path it took to get to the destination node.
Each iteration of the transfer count step now looks only for the stops that have been recently updated (so the stops that were newly accessible as a result of the full traversal of a paired stop’s trips).
Similarly, the footpath connection logic now needs to track the new stops that are identified:
Another optimization is introduced, that you might notice, is that stops that have already been geo-processed with near pairs found are also tracked. This helps save some time performing intersections. Using a spatial r-tree index would help speed this up further. Again, the point still stands that the number of new qualifying stops in later rounds are so great as to far exceed those in earlier transfer counts. The result of this is that the caching/skipping does not produce significant performance speedups.
Discussion of results
As mentioned above, the performance speed up is rather marginal because of the high level of fan-out that occurs on later iterations of transfers. A summary is presented below:
Original runtime increased with each iteration. This was due to repetitive identification and processing of stop and trips that were already handled, as well as expensive geo-operations on stops done repeatedly. By leveraging some simple caching patterns, we can avoid those and shift the cost of increased transfers to become have a more linear cost increase. That is, each subsequence transfer/iteration would only be calculating the new stops identified, not all of the prior ones, plus the new ones, cumulatively.
Analyzing possibilities with 0 transfers initial qualifying stop ids count: 1 stop times calculated in 0.9308 seconds 28 stop ids added footpath transfers calculated in 0.6707 seconds 103 stop ids added Analyzing possibilities with 1 transfers initial qualifying stop ids count: 132 stop times calculated in 24.1655 seconds 782 stop ids added footpath transfers calculated in 20.1302 seconds 1077 stop ids added Analyzing possibilities with 2 transfers initial qualifying stop ids count: 1991 stop times calculated in 60.4546 seconds 406 stop ids added footpath transfers calculated in 52.8831 seconds 517 stop ids added Time to destination: 35.5 minutes
Unfortunately, the impact of caching is fairly limited because there is a great deal of “fan-out.” That is, with each iteration (each additional set of transfers allowed), the number of possible stops to consider increases significantly, producing ever greater numbers of possible routes and trips to consider, that were inaccessible in the prior step (or transfer-iteration). Below is an example demonstrating how the caching effort produces marginal improvements in runtime of the algorithm.
Analyzing possibilities with 0 transfers initial qualifying stop ids count: 1 stop times calculated in 0.9049 seconds 28 stop ids added footpath transfers calculated in 0.7186 seconds 103 stop ids added already processed count increased from 0 to 1 new stops to process: 103 Analyzing possibilities with 1 transfers initial qualifying stop ids count: 132 stop times calculated in 22.9711 seconds 782 stop ids added footpath transfers calculated in 20.6031 seconds 1077 stop ids added already processed count increased from 1 to 104 new stops to process: 1547 Analyzing possibilities with 2 transfers initial qualifying stop ids count: 1991 stop times calculated in 52.9557 seconds 407 stop ids added footpath transfers calculated in 50.7413 seconds 517 stop ids added already processed count increased from 104 to 1651 new stops to process: 940 Time to destination: 35.5 minutes
As you can see from these logs, the introduction of the caching logic produced negligible runtime speedups. I am hoping I am missing some greater performance speedups but I think I might not. It is likely that this algorithm really leans on parallelization for achieving performance gains.