Random expensive intermodal routing requests

[vkrause]

Further investigation of the issue mentioned by me in #438 showed this is entirely unrelated, so adding a new ticket.

It's possible to trigger routing requests that lead to an excessive amount of intermediate routing queries (> 5000). This has been observed both with parking/ppr and valhalla.

• https://github.com/motis-project/motis/blob/master/modules/parking/src/parking_edges.cc#L140 is hit for the car/parking case, which each call taking on average 100ms. So while not an infinite loop as initially assumed this nevertheless then is busy for about 10 minutes.
• https://github.com/motis-project/motis/blob/master/modules/valhalla/src/valhalla.cc#L186 throws an exception for requests with more than 2500 targets. That makes the request abort but there is a substantial amount of memory (can be several GBs) consumed and not freed (but apparently cleaned up at shutdown, Heaptrack shows no leak). A couple such requests and we run out of memory.

I obviously haven't tried to reproduce on the demo instance, so this is all from testing with a local Switzerland setup (with GTFS-RT/GBFS/ParkenDD enabled, but also seems to happen without any of those). The problem seems to occur more likely the closer start and destination are together, the more intermodal start/destination modes are enabled, and the higher their range is (longer max duration or e.g. car over bike). That makes me think this might happen when the reachable areas of the first/last mile modes start to overlap, but I have nothing to back that up with.

Under those conditions it usually only needs a few tries with random locations not too close to stations/stops to trigger this.

[felixguendling]

I have to admit that the Valhalla integration is not really well tested. Looking back, just creating a routing-request to a Valhalla Docker container via HTTP would probably have been a better solution. Maybe it already helps to set the maximum number of sources/destinations to infinity in Valhalla so the exception is not thrown?

It's also possible that integrating Valhalla this way has been a bad idea and just using the official Docker container + using HTTP requests in MOTIS would work better.

[PartTimeDataScientist]

From my experience while playing around with a dockerized Valhalla instance calculating >=2500 one-to-many routes would often still be painfully slow even if using a dedicated external Docker container or the demo instance. The limitation in the calculation is not set arbitrarily.

We have discussed some other options for solving the underlying problem efficiently but so far these remained in the theoretical space and have not been implemented anywhere:

1. Simple undirected Dijkstra terminating at the desired target nodes
   Arndt Brenschede (@abrensch) has implemented such logic in BRouter for finding (and navigating) to the nearest BEV charging station (not publicly available). Should work well for somewhat static data (charging stations, public transport stations, other POIs) but would likely be a little more complex for (highly) dynamic "targets" like live positions of e-scooters or rental bikes
2. The SSMTA*-algorithm
   Could be more efficient for some cases but would need to touch roughly the same amount of edges in case of a mostly circular search for suitable public transport stations
   

[felixguendling]

I agree to @PartTimeDataScientist - the table routing approach is really not the best fit for what we try to achieve. A simple Dijkstra would be way better suited and is already implemented in Valhalla. The only problem is that it's not available via a one-to-many / many-to-one API. I guess implementing this would be manageable but I personally don't have capacity to look into this right now.

Still, using the Docker container would make it way easier to keep up-to-date with the latest developments in Valhalla. But of course statically linking everything into the MOTIS binary also has its advantages.

Another option that I would want to explore (even independently of this issue here) is to develop heuristics to ignore stops, so the number does not even come close to 2500. Especially when driving with the car, I can't imagine a scenario where I would use the car to drive 1h to a bus stop next to a big station where the big station has a clear superset of the routes that visit the bus stop. So I am sure we can develop heuristics that would not impact result quality but would significantly reduce the number of routing destinations for OSRM/Valhalla/etc.

[PartTimeDataScientist]

The smart selection of stops is definitively something that we also have on the agenda.

While it likely has the largest effect on the "car->public transport" case due to the comparatively large radius that is generally reachable by car the same holds for the "bike->public transport" case. You wouldn't typically bike to a bus stop if a tram or even train station is nearby (especially if you want to carry the bike with you) and there are many cases where you could trim down the list of relevant stations even further when multiple stations are served by the same trains within a few minutes like the four stations here in Düsseldorf:

[vkrause]

As we see the same problem with PPR (just with different but equally critical consequences), I'm not sure the Valhalla integration is the only problem here. Substantially cutting down on the number of stops to evaluate OTOH sounds very promising, in the cases where it works here the number is usually below 100 and rarely above 300, in the broken cases it can go above 5000 even.

(the main reason we are also testing with Valhalla at the moment is that we still fail on importing the full European OSM data into osrm/ppr)

[abrensch]

1. Simple undirected Dijkstra terminating at the desired target nodes

Not target nodes, but edges (=node pairs), and not terminating, but just remembering the current cost (linearily interpolated along that edge). The routing must be terminated by a cost-cutoff that is choosen sensible.

So the target points have to be prepared in advance by a waypoint-matching, transforming them to node-pairs plus the position of the closest match alonmg that edge. This matching procedure is faster when done collectivly, but even if done per target node individually it's in the milliseconds range. So it's no problem to do it for dynamic data.

   Arndt Brenschede (@abrensch) has implemented such logic in BRouter for finding (and navigating) to the nearest BEV charging station (not publicly available). Should work well for somewhat static data (charging stations, public transport stations, other POIs) but would likely be a little more complex for (highly) dynamic "targets" like live positions of e-scooters or rental bikes

The prototype I did for planning charging stations solves the next complex problem which is finding POIs along the planned route. And that's not a 2-step process (planning route -> matching POIs) but done as a whole, since the availablibity of a POIs influences the route planning. Here I used not undirected Dijkstra, but 2 A* runs, both with an extra cost range to continue after the A* target was hit.