search

opentripplanner / OpenTripPlanner

An open source multi-modal trip planner
http://www.opentripplanner.org
Other
2.22k stars 1.03k forks source link

Dynamic search parameters #2931

Closed t2gran closed 4 years ago

t2gran commented 4 years ago

Raptor, unlike AStar(OTP1), MUST have a search-window. Raptor will search and find all optimal travels within that window. OTP1 is searching until it times-out or a speccified number of itineraries is found. The search-window is for a normal DEPART_AFTER search the time from the earliest-departure-time to the latest-departure-time. For a ARRIVE_BY search it is the time window from earliest-arrival-time to the latest-arrival-time. For a client/traveller it is inconvenient to supply 2 times for this (or a time and a window size).

The solution is to use some statistics to guess a good window size for the given search. If the search is short in a high frequency area we set the time-window short, and in the opposite case we set the window long. A short window would be down to 30 minute with maybe 3-10 different options/trips to choose from. While a long window could be 2 days.

Expected behavior

Version of OTP used (exact commit hash or JAR name)

dev-2.x

t2gran commented 4 years ago

This is related the #2885 arriveBy search.

t2gran commented 4 years ago

A first take on this is implemented. The implementation find a valid trip and calculate the search-window using the duration without wait-time of the trip found. The trip is the one with the earlieat-arrival-time possible (in the case of a depart-after-search).

This seems to work surprisingly well for Norway.

More on this in the JavaDoc: https://github.com/opentripplanner/OpenTripPlanner/blob/dev-2.x/src/main/java/org/opentripplanner/transit/raptor/api/request/DynamicSearchWindowCoefficients.java