Improve Raptor Heuristics performance - number of transfers

[t2gran]

Introduction

When Raptor do a transit search it first does a single criteria, one iteration search to compute the heuristics. This search is slow. So is there a way to improve it?

Related issues: #3748 and #4417
Related research: Fast and Exact Public Transit Routing with Restricted Pareto Sets by Delling, Dibbelt, Pajor.

Goal

The end goal is to support the optimization described in the paper above. OTP do support a variant of this that was developed before we was aware of the paper, but the heuristic we produce is not as "tight" as it could be, so we would like to improve it. This is also to important to be able to support more than one generalized-cost, like a cost emulating price.

To improve the current and future heuristics we can compute the number-of-transfers from origin to each stop, and use this in the reverse search. We could use this together with a max limit on transfers to drop paths.

Todays heuristics

Todays heuristics does a reverse search to compute the least-number-of-transfers and fastest-travel-time (excluding wait-time) for every stop. The time and nTransfers is the amount it takes to travel from that stop to the destination. To compute this we search in reverse - from destination toward the origin. This is then used to compute a minimum value for the cost for every stop to the destination. A single criteria(time) Raptor search is used t do this. The heuristics is then used by the Multi-Criteria Range Raptor for the final search.

Discussion

In #4417 there is a suggestion to do a bi-directional search to compute the heuristics/number-of-stops heuristics. For that to work you would need to keep all paths, witch is not possible. But there are variants that might work.

So this issue is about producing a heuristics witch can be used to limit the stops we need to consider in both the reverse-heuristic raptor search and the mc-multi-criteria range-raptor search. The goal is to produce a byte array containing the number of needed transfers from a stop to reach the origin. We will limit the search by allowing a path to have N extra transfers more than the optimal path(T transfers). We can do this in a simpler way than using raptor, so we will experiment by doing this in a new module inside Raptor. It should use the same input as Raptor does, there should be no need to change it. It might also be that we can modify Raptor to do this, because the only difference is that we do not need to do trip searches.

Outline

1. Phase 1 - Do a forward search to compute number-of-transfers heuristics for phase-2
2. Phase 2 - Compute heuristics
3. Phase 3 - Multi-criteria search

Possible solution

We do not need to compute a complete heuristic in phase 1, only enough data to optimise the phase 2. Then we can compute the number-of-transfers heuristics in phase 2 for phase 3.

I suggest starting with a simple implementation that does a fixed number-of-iterations(I). We should test the to find the optimal I, but I guess it would be around 5-7 rounds for Norway. If we reach the destination before that we can abort.

At this point we have computed the number-of-transfers needed for part of the graph. When this is used in phase 2, it will take effect as soon as the search reaches the first stop with a computed value. We can now calculate the limit. For every stop reached after this point we can drop the result if it is not below the limit.

Version of OTP used

OTP 2.2

Data sets in use

Big datasets like Norway, Nordic Countries or Germany

[slvlirnoff]

Hello @t2gran, chiming in even if still a draft, before going too far: are we confident that a limit based on the number of round is a. Effective and b. Not pruning optimal paths?

Currently the limit in place isn't limiting much, because it's not tight (hence the discussion for performance reasons) however as waiting time isn't taken into consideration it's easy to imagine a case even with current implementation where a direct unfrequent connection like a plane flight would have a theoretical best path of 0 transfer and would hide/reject a regular land itinerary running through the day with 6 transfers.

[I guess this rarely happens in practice partly because of long walking transfer path. The regular optimal path would be discarded but variations of it with long walking transfer but less transfers overall are not rejected, these stops are still explored by the heuristic and kept for the raptor profile search which compute the optimal paths.]

The goal of my suggestion for bi-directional heuristic would have been to detect patterns that would be used in a similar way in both directions to avoid "backtracking". If a forward search tree goes through stops Origin,...,A,B and a reverse search tree goes through stops Destination,...,A,B. The optimal journeys for all criteria will likely be Origin,...,A,...Destination. But indeed as the paths are not kept and as the waiting time isn't considered this would not work.

[t2gran]

There is a way to include wait-time in the heuristics, instead of just using one-pass Raptor (we do now), we can use Range Raptor instead. I have planned to test this, especially with 2 cost criteria this might prove to be faster. The heuristics will take more time but be tighter.

[github-actions]

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 30 days