TransferIndexGenerator ConstrainedTransfer and TransitLayerUpdater performance issue

[slvlirnoff]

The TransitLayerUpdater trigger the generation of transfers on each call to TransitLayerUpdater.update as a result it might eats up memory and this slows down the graph update process. This is intended because realtime updater might generate new routing patterns.

While not a blocking issue, in case of frequent transit layer update with a large amount of constrained transfer this can cause a performance issue. In one of our deployment, with ~60k constrained transfers and ~40k patterns the TransitLayerUpdater can take up to 5-6s to update the routing graph and very quickly stress the garbage collector to discard all previously generated transfers.

Expected behavior

I'd expect the TransferIndexGenerator to incrementally generate new transfers or newly created RoutingPattern. Or only trigger when new patterns have been generated by the realtime processes.

Observed behavior

The transfers for the whole transit graph are generated every time.

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

latest

[slvlirnoff]

Investigating this issue further within switzerland data context, we see that a relatively small set of the transfers are causing the bulk of the performance issue. There is around 8'000 station to station transfers (that we use to model the minimum transfer time between stations) that are causing up to 40'000'000 transfers points in raptor.

We have many variations of trips on the same route with different stop platforms over the yearly timetable, this cause several patterns to be created with some stations having a few hundreds patterns. The combination factor of patterns to patterns between these stations seems to generate a huge amount of object,

[slvlirnoff]

Ideally the stop to stop constraints should be indexed by stop instead of by patterns to avoid this expansion, i.e. like the regular transfers.

Already some of the constraints could potentially be included in the regular transfers if existing (and creating a new one if not), these would facilitate or constrain the regular transfer with guaranteed, minimum time or cost factor.

Raptor algorithm would still try first to board with the help of a constrained transfer using the existing approach (transfer pattern index), to handle constraints related to previous pattern or trip and would then fallback to stop to stop transfers.

When boarding with regular transfers, the additional transfer constraints would be considered in the transfer cost (for instance minimum transfer time) and potentially trip search (with guaranteed transfer).

This would have the beneficial effect that the overall information for transferring between stops both physical from the street network/pathway information and the additional constraints would be within the same transfer object increasing consistency. What do you think @t2gran ?

Going further: storing all constrained transfers within existing regular transfers could be considered, removing the double index and transfer search process (constrained then fallback to regular) the regular transfers would keep track of all constraints, between the from/to stops as well as between specific patterns of these stops and apply the relevant logic.

[slvlirnoff]

Also a separate related limitation of the current implementation is that a constrained transfer will only be considered if there's an existing regular transfer between the same stops in the system.

Raptor algorithm expands to stops for the next round using regular transfers then conditions boarding by using constrained transfers. If there're no regular transfers matching the constrained one, it'll potentially not expand to the relevant stop.

(This could happen if the street network isn't properly connected between the relevant stops or if the regular transfer has been discarded (only one transfer is kept for each pair of patterns).)