ArriveBy implementation and optimization

Discussion

We have discussed implementing the arriveBy search by inverting time and do the search from the destination towards the origin. This does not work due to shifting the trips in the middel of a journey toward the beginning of the trip. RangeRaptor by its nature solve this problem, but only when searching from the origin.

Another way to do this, is to do a normal forward (origin to destination) search, but first do a reversed (destination to origin) Raptor search to find the search time window.

Optimization

The reversed Raptor search can be used to find information which we use to prune the following forward multi-criteria search. Each stop can be labeled with an upper bound arrival time used to prune the forward search.

Solution outline

First we do: For a arrivaBy search we can use a reversed Raptor search to insert max arrival time into all stops in the graph until we reach the origin. For all stops not reached we can use the origin max arrival time. This will be an very effective Goal direction pruning of the graph.
Then: We can now do a normal McRangeRaptor search using the max arrival time as an absolute cut-off for each stop. toTime can be calculated from the egress stops max arrival time and fromTime will be current time or toTime - max search window.

Overhead

Since the Raptor search uses less than 60 ms on average, the overhead is very small. Currently the McRR Search uses more than 3000 ms. Depending on the search time window size (< hour), this will be a very effective optimization.

entur / r5