Differences between r5/r5r and gtfsrouter

@rafapereirabr @mvpsaraiva This issue arose in gtfsrouter which seemed to show r5r giving different results to gtfsrouter for travel times, and in particular the graph in the opening comment that seems to show r5r generating occasional travel times which are anomalously longer than those generated by new gtfsrouter algorithm.

@ansoncfit @abyrd and I had a chat about this yesterday, from which we concluded that it was because of fundamental differences in the underlying routing algorithms. The new gtfsrouter algorithm extracts fastest journey times, whereas r5 uses the (range-)RAPTOR algoirthm to extract earilest arrival times, rather than fastest journeys. My understanding of the differences follows below, in response to which I suspect that at least some updating of r5r documentation might be appropriate, in order to clarify exactly what a travel_time_matrix() is.

`gfsrouter`

The algorithm finds shortest overall journey times (potentially constrained by numbers of transfers), and traces all trips which depart from specified origin stations between the two values given as start_time_limits - that is, later than the the first time, and prior to the second. The result is a value for each station within a system of fastest possible time to that station for any trip leaving the specified origin station(s) between those time limits.

`r5` and `r5r`

The first sweep of the range RAPTOR algorithm finds the earliest possible arrival time at each station, the second (backwards) sweep finds the latest possible departure time matching that arrival time. The result is the shortest journey time for the first service departing the nominated station(s) which arrives at that earliest arrival time. This is different to gtfsrouter, and i now strongly suspect it is this difference which underlies the observed discrepancies. The few stations for which gtfsrouter finds faster travel times are ones with arrival times later than earliest possible arrival time, and so which by definition are excluded by a RAPTOR/r5/r5r search. NOTE that i have not empirically confirmed this, and merely offer it as my statement of what i currently believe to be the cause of the differences.

Your problem is then that the result of r5r::travel_time_matrix is a little more difficult to explain that that of gtfsrouter. The travel times are the difference between latest possible departure on the services which arrive at each destination at the earliest possible arrival time. Or, alternatively, values are shortest journey times subject to the constraint that journeys arrive at each station at the earliest possible arrival time. The equivalent constraint for gtfsrouter is that journeys depart within the specified start_time_limits, with no constraint on arrival times.

I don't want to misrepresent r5 or r5r, so will update gtfsrouter documentation accordingly to clearly explain that algorithmic differences mean that the two do not necessarily generate the same results, and suggest the same is done here. @ansoncfit @abyrd please clarify anything you think i may have misunderstood here. Thanks!

Hello, here's a little more input from our side at Conveyal.

Based on our discussion with @mpadge, I think the confusion is just due to different expectations and usage patterns. Someone might be looking for the shortest end-to-end travel time leaving anytime after a specified departure time (movable departure time), or they might be looking for the earliest possible arrival time given a single fixed departure time. At its lowest level R5 finds the latter, but it also finds the former by iteratively applying the latter.

It sounds like gtfsrouter is attempting to directly (non-iteratively) find the shortest end-to-end travel time. We've experimented with such methods but found it prohibitively complex to maintain compared to the efficient iterative approach of range-raptor: R5 tries each departure time in the window and retains a result for every departure time. This includes not only the shortest end-to-end time but also the longest and everything in-between. We extract the percentiles we're interested in or present the entire distribution. By using the range-raptor optimization (starting at the end of the window and reusing the unchanged portion of the state at each successive departure minute) R5 can check each departure time much more quickly than if each time were each analyzed with a separate routing call.

Note that from Conveyal's point of view, it is beneficial to examine so many different paths that include varying amounts of transit waiting time (initial and transfers) because we're building a statistical distribution to capture the magnitude of variance in end-to-end travel time depending on when you leave.

@mpadge, your comment contrasts the output of gtfsrouter with that of r5, but I think there may still be some misunderstanding. In fact the output of r5 is exactly what you described for gtfsrouter. The question then is just whether r5r exploits this time window capability of the r5 library to get the results you're looking for. I don't yet know if this is the case.

R5 does not perform the forward-then-backward sweep described above. That is a strategy that we used in OTP and was "conventional wisdom" among developers of several other open source routing projects, but when working on R5 we determined this was unnecessary: when examining a full departure time window, range-raptor naturally finds the shortest and longest end-to-end travel time and everything in between, which is how we get our full travel time distributions.

The times we report are not "subject to the constraint that journeys arrive at each station at the earliest possible arrival time". They are simply all the end-to-end travel times, for every departure time in the window. The constraint is exactly the same as that described for gtfsrouter: "journeys depart within the specified start_time_limits, with no constraint on arrival times".

One possible source of confusion that comes to mind is that in some uses R5 does impose a 2-hour limit on end-to-end travel time. If you are searching for trips longer than 2 hours then you may not find them.

@mpadge please let me know if you update any of your documentation highlighting differences with R5, and I can provide feedback on any descriptions of R5's methods.

@rafapereirabr, as @mpadge suggested, to avoid confusion we may want to update some r5r documentation to more fully describe what the outputs are. We should also check where in r5r single departure times are used as opposed to time windows, and make it clear to end users what kind of results they will receive in each case. I will take another look at R5R and see if I can determine exactly how R5 is called and whether time windows are used as intended in each case. Any links to code from the R5R team would be appreciated.

I just posted some observations and clarifications on ATFutures/gtfs-router#73 which may be of interest to the R5R developers. It's great to see people interested in these tools, and I'm looking forward to better understanding how they're applied. I'll just need a little more time to understand how exactly R5R calls R5 and processes its output.

Hi @mpadge and @abyrd. Thank you very much for your inputs. One of our goals with r5r is to minimize the number of 'black boxes' in routing tasks, so researchers can know more accurately what the results they're getting mean. We also do not want to misrepresent r5 or hinder any of its capabilities, so your input here is very much appreciated.

@mpadge, your comment contrasts the output of gtfsrouter with that of r5, but I think there may still be some misunderstanding. In fact the output of r5 is exactly what you described for gtfsrouter. The question then is just whether r5r exploits this time window capability of the r5 library to get the results you're looking for. I don't yet know if this is the case.

Indeed, r5r uses the time window capability of r5, just not by default. The r5r::travel_time_matrix() function has a time_window parameter with a default value of 1 minute, so it's up to the user to decide wether to use the time window or not.

I will take another look at R5R and see if I can determine exactly how R5 is called and whether time windows are used as intended in each case. Any links to code from the R5R team would be appreciated.

Recently I've carried out a huge clean up of r5r's Java codebase, so it should be much easier to understand what's going on now than on the first time you looked. There are some oddities in the code structure due to the very nature of r5r: it's a bridge between Java's OOP and R's functional programming styles. So, basically, the R5RCore class is just a collection of public functions that can be accessed by R, and those functions instantiate Java objects that do the actual work.

r5r uses the TravelTimeComputer class from r5 to calculate travel times for each origin point, and then aggregates everything into a full travel time matrix at the end. The TravelTimeMatrixComputer class is the one that does that, by instantiating one TravelTimeComputer object from r5 per origin and computing it's travel times to all destinations. The R5Process super class is the one that handles all origin points and manages the parallelisation. The time window is set here.

Please, let us know if you have any questions or if you find out that we are doing something the wrong way. We'll also keep working on the documentation to make it more clear what exactly each function does and what the results mean. We'll update this issue once we have some proposals, so you can take a look before we submit to CRAN.

Thanks again for the feedback.

Hi all. I guess this discussion has been clarified for now. I'll be closing this issue, but I'm glad to reopen it in the feature if new questions arise.

ipeaGIT / r5r