detailed_itineraries with shortest_path = FALSE won't return a best solution

[luyuliu]

Hi all,

We were testing on the sample data in Porto Alegre on using detailed_itineraries to get multiple shortest paths. We selected the route 654 as our route, and we selected a trip (654-1@1#1240) and used its start station as the origin (stop_id = "3450", the start of the route) and one of the station in the middle as the destination (stop_id = "3809"). The start time is set as "2019-06-18 12:30:00", and we changed the time point from 30 to 50 to see the changes.

The issue is threefold:

1. In the solutions provided, the route 654 won't show, which is weird. We design the origin and destination and start time per the trip we selected in the timetable. We found the trip in the timetable so I was pretty sure it should be there. So, theoretically, it should pop up in the solution. However, we tested multiple times and the results are all very confusing.

When changing shortest_path = True:

Changing the date would also be different, even if they have the same service_id

2. When we change the time slightly and found that the solution very unstable.

3. The time window parameter is not helping too. We used 1 since we want to find the exact solution.

We want to control the solution (to some degree) and reduce the uncertainties. Is this intentional or a feature of the routing algorithm? Thank you for any advice!

Thanks,
Luyu

[rafapereirabr]

Hi @luyuliu , could you please paste the code to reproduce your results ?

[Zhitao-Li-csu]

Hello @rafapereirabr,

I am currently exploring r5r using the built-in Porto Alegre sample dataset. My goal is to understand how detailed_itineraries handles specific departure times and time windows when trying to match a known trip from the GTFS data.

I have isolated a specific trip (route_id: 654, trip_id: 654-1@1#1240) which operates on 2019-06-18 starting at 12:40:00.

I am attempting to route from the first stop to the 40th stop of this trip. I have observed some behavior regarding time_window and departure_datetime that I would like to clarify.

Here is the reproducible code:

# Allocate memory, load R packages, set paths
options(java.parameters = "-Xmx4G")

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

library(tidytransit)
library(dplyr)

# Locate data path
data_path = system.file("extdata/poa", package = "r5r") 
gtfs = read_gtfs( file.path(data_path, 'poa_eptc.zip'))

# Select a specific route
routes_data = gtfs$routes
stops_data = gtfs$stops
stop_times_data = gtfs$stop_times
trips_data = gtfs$trips
calendar_dates_data = gtfs$calendar_dates
SELECTED_ROUTE_ID = routes_data$route_id[5]  # Result is route_id ="654"

# Select an available trip as an example
stop_sequence_for_trip = trips_data %>% 
  filter(route_id == SELECTED_ROUTE_ID) %>%
  slice(1) %>%
  left_join(stop_times_data, by = "trip_id") %>%
  left_join(stops_data, by = "stop_id") %>%
  arrange(stop_sequence) %>%
  select(stop_sequence, stop_id, stop_name, stop_lat, stop_lon, 
         arrival_time, departure_time)

# Query information for the selected trip
temp1_record_selected_trip = trips_data %>% filter(route_id == SELECTED_ROUTE_ID) %>%  slice(1)   # Result is trip_id = 654-1@1#1240
temp2_record_selected_trip_stops = stop_times_data[stop_times_data$trip_id == temp1_record_selected_trip$trip_id,]  # Operation time: 12:40:00 - 13:25:00

# Rename columns
names(stop_sequence_for_trip)[2] = 'id' # stop_id
names(stop_sequence_for_trip)[4] = 'lat' # stop_lat
names(stop_sequence_for_trip)[5] = 'lon' # stop_lon

# Select Stop No.1 → No.40 as the OD pair
A_origin = stop_sequence_for_trip[1,]
A_stop_id = A_origin$id
B_destination = stop_sequence_for_trip[40,]
B_stop_id = B_destination$id

r5r_network = build_network(data_path = data_path)

# Service schedule
calendar_date_654 = gtfs$calendar_dates[calendar_dates_data$service_id %in% temp1_record_selected_trip$service_id,]

# Set assumed departure time and search for feasible routes
T1 = as.POSIXct("2019-06-18 12:35:00",tz = 'America/Sao_Paulo') 
    # Q1: Route 654 cannot be found when setting time between 12:35:00 - 12:39:00
    # Q2: Why can Route 654 be found when setting time between 12:40:00 - 12:50:00? Why do we get different departure times?
        # Known trip duration is 12:40:00 - 13:25:00
    # Q3: Route 654 can be found when setting time between 12:30:00 - 12:34:00, but the departure time is sometimes unstable

A_B_trip = detailed_itineraries(r5r_network, origins = A_origin,destinations = B_destination,
                                mode = c("WALK", "TRANSIT"),
                                departure_datetime = T1,
                                max_walk_time = 60,
                                max_trip_duration = 120,
                                time_window = 5,
                                shortest_path = FALSE)   # Set to FALSE to find Route 654

[alexmgns]

@luyuliu I don't quite understand the examples you show in your original comment. With shortest_path = false the best trip is 38m and with shortest_path = true the time is 56m? Is the problem that shortest_path = true isnt finding the optimal trip? Or is the problem that shortest_path = false is generating an impossible trip that arrives too fast?

detailed itineraries uses a different algorithm compared to all the other methods in r5r. But shortest = true/false should be using the same algorithm so this is quite strange.

[luyuliu]

@alexmgns Sorry for the late response! I was saying that R5R seems to not be able to find the best solution, since there is a bus (route 654) that is theoretically faster than all the proposed routes given by R5R, which we checked in the schedule manually. We "reverse-engineered" or specifically designed the parameter setting so that route 654 should be the best solution for the OD pair at that timestamp. But the results say otherwise. I was wondering if this is a feature or a limitation of the engine?

[alexmgns]

@luyuliu it's possible that bus route 654 didn't get parsed correctly or didn't get parsed at all due to some error. Matt who built most of these algorithms in the first place has been working on these silent failures recently, see #516. If it is an algorithm error and not gtfs error Matt is definitely the guy to ask.

Try extracting the transit network and see if the route exists and is in the proper location https://ipeagit.github.io/r5r/reference/transit_network_to_sf.html

[rafapereirabr]

Hi guys, apologies for my slow response. I'm currently overcommitted and unfortunately I would only be able to look into this issue more carefuly in the next few months due to travel commitments.

[mattwigway]

Hi all, apologies I didn't get notified for this. I just took a quick look - I don't have a complete answer but I suspect it has something to do with the origin being off the edge of the OSM data. Here I have plotted the stops on the 654 (red/teal for the 1st/40th), the path found at 12:30 (black), and the OSM network (gray):

The route starts at and boards several stops into the route, because the earlier stops are not snapped to the street network - that stop will have different timing, so the bus will pass it at a different/later time, and I suspect that at 12:40 from that point the 654 is just not the fastest option (though I have not done any testing to confirm this - the thing to do would be to make a Marey plot of all the options found at different times to see).

The found route at 12:35 is kinda weird:

I'm not sure why it loops back on itself like that. Potentially an issue parsing shapes.txt.

[luyuliu]

Hi all,

Thank you very much for the answers! Matt - thank you for testing. That makes more sense now. I don't really have enough time to test the result with complete OSM network now, since we decided to write our own algorithm for more robust results for this specific project we are doing. Thank you again for all the works!

Thanks,
Luyu

[mattwigway]

You're welcome! Let's leave this issue open for now, I'd like to confirm that this isn't an issue with the underlying algorithms or code - I can take a look in a few weeks when the semester wraps up.