detailed_itineraries and travel_time_matrix return different total travel times

[FlxPo]

Hi,

First of all I'd like to thank all the developpers of this package, it makes a lot of the gruntwork disappear (preparing osm files, ingesting GTFS...) and opens a lot of new possibilities directly in R (multi modal routing !).

I'm not sure if this is a bug or a misunderstanding on my part, but I was surprised to find that the travel_time_matrix and detailed_itineraries return quite different travel times between the same origin/destination points.

Am I missing something ?

Here is a short reproducible example :

library(r5r)
library(sf)
library(data.table)

data_path <- system.file("extdata/poa", package = "r5r")

poi <- fread(file.path(data_path, "poa_points_of_interest.csv"))
points <- fread(file.path(data_path, "poa_hexgrid.csv"))
sampled_rows <-  sample(1:nrow(points), 200, replace=TRUE)
points <- points[ sampled_rows, ]

r5r_core <- setup_r5(data_path = data_path, verbose = TRUE)

# calculate a travel time matrix
ttm <- travel_time_matrix(r5r_core = r5r_core,
                          origins = points[1],
                          destinations = points[2],
                          mode = "CAR")

# calculate detailed itineraries
det <- detailed_itineraries(r5r_core = r5r_core,
                            origins = points[1],
                            destinations = points[2],
                            mode = "CAR",
                            shortest_path = TRUE)

print(ttm$travel_time)
print(det$total_duration)

stop_r5(r5r_core)
rJava::.jgc(R.gc = TRUE)

[rafapereirabr]

Hi @FlxPo . Thank you for the kinds words. These two function use different routing algorithms. As explained in the documentation:

travel_time_matrix

The travel_time_matrix() and accessibility() functions use an R5-specific extension to the RAPTOR routing algorithm (see Conway et al., 2017). This RAPTOR extension uses a systematic sample of one departure per minute over the time window set by the user in the 'time_window' parameter. A detailed description of base RAPTOR can be found in Delling et al (2015).

Conway, M. W., Byrd, A., & van der Linden, M. (2017). Evidence-based transit and land use sketch planning using interactive accessibility methods on combined schedule and headway-based networks. Transportation Research Record, 2653(1), 45-53. doi: 10.3141/2653-06

Delling, D., Pajor, T., & Werneck, R. F. (2015). Round-based public transit routing. Transportation Science, 49(3), 591-604. doi: 10.1287/trsc.2014.0534

detailed_itineraries

The detailed_itineraries() and pareto_frontier() functions use an R5-specific extension to the McRAPTOR routing algorithm. The implementation used in detailed_itineraries() allows the router to find paths that are optimal and less than optimal in terms of travel time, with some heuristics around multiple access modes, riding the same patterns, etc. The specific extension to McRAPTOR to do suboptimal path routing is not documented yet, but a detailed description of base McRAPTOR can be found in Delling et al (2015). The implementation used in pareto_frontier(), on the other hand, returns only the fastest trip within a given monetary cutoff, ignoring slower trips that cost the same. A detailed discussion on the algorithm can be found in Conway and Stewart (2019).

Delling, D., Pajor, T., & Werneck, R. F. (2015). Round-based public transit routing. Transportation Science, 49(3), 591-604. doi: 10.1287/trsc.2014.0534

Conway, M. W., & Stewart, A. F. (2019). Getting Charlie off the MTA: a multiobjective optimization method to account for cost constraints in public transit accessibility metrics. International Journal of Geographical Information Science, 33(9), 1759–1787. doi: 10.1080/13658816.2019.1605075

[FlxPo]

OK, but shouldn't detailed_itineraries return the optimal (fastest) path along suboptimal ones ? Or do the heuristics change the results ?

[mvpsaraiva]

Hi @FlxPo

The main difference between travel_time_matrix() and detailed_itineraries() is that they use different features of R5, with different algorithms and ideas behind.

detailed_itineraries() uses R5's PointToPointQuery feature that was developed specifically for end-user facing applications... its main use was a mobile phone app that helped people find their way in cities. travel_time_matrix(), on the other hand, is built on top of R5's main analytical capabilities and a more mature code base. All this is to say that one is not simply a more detailed version of the other, they are two different animals. While they share a lot of code between them, they also differ in significant ways and results are not always directly comparable.

This is my current understanding of this issue, and obviously people at Conveyal will know the exact details.

In your specific example, I believe the time difference is due to the way both functions 'snap' the origin and destination points to the street network. If you look at the map below, you'll see that the trip doesn't start exactly at the origin point but a few meters away. The same happens at the destination points. I suppose travel_time_matrix() handles this differently, and probably on a better way.

[FlxPo]

OK, I get it, I'll stick to travel_time_matrix for now. Thanks for taking the time to explain and illustrate the differences !

It would be great if travel_time_matrix could return distances also (as asked here : https://github.com/ipeaGIT/r5r/issues/261). I tried to dig into the java code, but I don't know enough about R5 for now to see if it's possible.

[mvpsaraiva]

It would be great if travel_time_matrix could return distances also (as asked here : #261). I tried to dig into the java code, but I don't know enough about R5 for now to see if it's possible.

As i've mentioned in #261, R5 is mostly built around minimising travel times, not distances. But the functionality for calculating travel distances is kind of there, deeply buried. For example, the StreetRouter class, that does the walk/cycle/car routing, has an option to choose between minimising times or distances here. However, the TravelTimeComputer class, that does the heavy lifting of calculating travel times in multimodal networks, hardwires StreetRouter into evaluating travel times instead of distances here.

So, technically, it is possible to fork R5 and create a sort of TravelDistanceComputer to do the job. Or at least use StreetRouter directly to calculate travel distances by walk/bike/car, without the public transport component.

[mvpsaraiva]

Anyways, if you really need to operate on distances for non-transit transport modes, I suggest using dodgr.

[FlxPo]

Yes I'm already using dodgr for unimodal routing ! I got really excited when I saw r5r could handle uni AND multi modal calculations...

I think I'll use r5r for multi modal routing only, with the detailed_itineraries function to get both time and distance travelled by mode.

Thanks !

[rafapereirabr]

closing this issue for now.