Optimizing OTP for large scale operations - Reduce the search space

[t2gran]

Observed behavior

For large deployments of OTP the travel search can be slow. For deployments of the size of Germany or the combined Nordic countries(Finland, Sweden, Denmark and Norway) it takes up to 7-10 seconds in some cases on a high compute server.

One of the reasons is that OTP will search local transit networks even fare from the origin and destination, even if we with high probability could exclude the local stops or local routes in these areas from the search. For example, if we search from Oslo to Stockholm, there should be no reason to explore local transit in other cities like Malmo or Trondheim.

Solution outline

We can divide the routes into to bags:

• local routes - Used to get from the origin to all places nearby where you can board all relevant long distance route. And like wise get from a long-distance-route to the destination.
• long distance routes - All routes used to travel fare, plus local traffic routes regularly used to connect between long distance routes.

To find the local routes we use a bounding box around the origin and destination. Then we use the bounding box for each route to find all routes overlapping with either the origin or destination. This can be optimized to be very fast.

Now we can merge the set of local routes and long distance routes and do the search with these routes as input.

Variations

Finding a good set of "long-distance-routes" by letting the algorithm learn

If we run a normal search with all routes in parallel in the background we can update the set of long-distance-routes if we find paths containing routes not in the set of routes used by the optimized search. The set of long-distance-routes should be shared between OTP instances (distributed cache or db).

A disruption in the traffic forces the traveler to use local transit network .

For example when a long distance transit hub is closed temporarily it might become important to use local transit to travel around the hub. By letting the algorithm learn (se above) it quickly will learn witch routes to use.

Tuning the search and serve all optimal paths

If we can switch to an asynchronous routing call, then we can restrict the routes in the fast search to target a few results, then when the "full" search return we can send all additional paths to the client.

Using stops as well

This can be implemented using stops instead of routes, but it is not likely to perform as good. One benefit however, is that by including not only the long distance stops, but the stops you can transfer too as well, is that we automatically would include all transfers with local traffic between to long-distance-routes.

We can also strip away all stops from a long-distance-route witch do not have a connection to another long-distance-route.

We can filter on only routes or stops or both.

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

OTP2.1

[leonardehrenfried]

I've actually experimented with a similar approach: I filtered by a bounding box around start and destination. This was meant to make searches over short distances faster - and it suceeded in doing that.

In my Germany instance it dropped the search time for short distance searches from 5 seconds to < 1 second.

Example: https://tinyurl.com/2ofsoe23

The code is at dev-2.x...leonardehrenfried:OpenTripPlanner:geometric-route-filtering

[slvlirnoff]

Instead of bounding box which will not work in many corner cases, would the hyper raptor approach work for this case?

https://i11www.iti.kit.edu/_media/members/tobias_zuendorf/fastertransitroutingbyhyperpartitioning.pdf

https://drops.dagstuhl.de/opus/volltexte/2017/7896/

Also another relevant partitioning and goal oriented traversal of partitions approach :
https://www.scitepress.org/Papers/2021/102353/102353.pdf

[slvlirnoff]

Another approach could be to run the forward and reverse heuristic together and stopping when they visit the same stop (with the additional rounds divided by 2). This would help by reducing the number of round of the heuristic by half the number of additional round (5 per default), which could already be a significant improvement for large graph.

I'm not sure if anything has been done also with a hierarchy of patterns and expanding rules such as expand into a higher level anywhere (i.e. local to national) and only to a lower level (i.e. national to local) when the local pattern overlaps/connects with destination. Could also be worthwhile to see if anything has been explored on that front? You could apply a similar idea by identifying hubs stations and pre computing trips/score as edges between these. You would then expand all patterns until you connect to a hub from the origin and from the destination and then only expand edges between hubs.

Also for your proposal, the set of relevant long distance patterns in addition to learning these could be precomputed to some extent. Consider breaking the graph in bags that are small enough to perform well you could compute some kind of heuristic between each pair of bags and update these with RT/disruption. It would be relatively easy to maintain a list of bags (and/or edges) that are relevant for a pair of origin and destination bag.

[t2gran]

Another approach could be to run the forward and reverse heuristic together and stopping when
they visit the same stop (with the additional rounds divided by 2). This would help by reducing the
number of round of the heuristic by half the number of additional round (5 per default), which could
already be a significant improvement for large graph. (@slvlirnoff)

I am sorry this does not work because it is not possible to merge the two sets, even if you kept the paths. Simply because in practices there can be many paths between to stop-pairs, and you would need to merge all paths, not just the best path found. But, there is a variant that might work. I will try to describe it in a separate issue.

For the papers, I did read through some of it today. It is interesting and some of the ideas are the same as I mentioned above.

For OTP there is a few fundamental requirements:

• We need to support real-time
• We need to support major disruption in the network
• We support pareto optimal search with time, number-of-transfers and generalized-cost. We want to add at least one more criteria. We do prune the result with max limits for each critera relative to the optimal value.

If there is a connection scan variant that can give us this, then we should consider it.

[slvlirnoff]

Unfortunately I'm not savy enough on CSA to say if it would support these requirements...

Looking forward to see your variant for the heuristic.