Collecting situations in which routing is slow

[jbruechert]

I'll use this issue to collect examples of places with performance issues, in case someone has time to look at them / debug them.

• There is some bottleneck in the middle of the journey, were very little connections are available (Routing in areas with little data is very slow #443).
  Routing takes long because the time interval needs to be increased very much to find a connection.
• Lots of data is available. The actual routing step already takes long, before increasing the interval is even considered.
  This can be found for example in Paris.
  Example:
  • Paris Gare de Lyon -> Vincennes

[felixguendling]

Thank you! @mority is currently looking into this 🚀

[mlundblad]

Another example:

• Basel SBB → Milan C.Le

[vkrause]

Another example:

* Basel SBB → Milan C.Le

More observations on this one:

• Seems to affect anything on the south-bound Gotthard route, also shorter ones like e.g. Zürich -> Lugano.
• The opposite direction works.
• europe.motis-project.de is not affected despite having the same CH dataset, so this is possibly caused by some of the additional datasets in Transitous also covering that area?

[PureTryOut]

At which point is a route considered too long to care about? I've tried planning a route from Arnhem Centraal (the Netherlands) to Nürnberg Hbf (Germany) and it 504's.

[vkrause]

Lots of data is available. The actual routing step already takes long, before increasing the interval is even considered.
This can be found for example in Paris.
Example:

* Paris Gare de Lyon -> Vincennes

This also seems to be directional, e.g. Paris Montparnasse -> Toulouse Matabiau (direct TGV connection) fails outbound but works perfectly fine for the return trip.

[laem]

Hi, just wanted to report some more slow situations in Paris :

• two itinerary test cases :
  • A) Buzenval (metro) to École militaire (metro)
  • B) Coordinates close to Buzenval to coordinates close to École Militaire with a walking PPR connection set to 15 minutes both sides.

On europe.motis-project.de, A takes 3 seconds, B takes 5 seconds.
On routing.spline.de/motis A takes 8 seconds, B takes 15 seconds.
On my AMD ryzen 5 32go RAM with only the Île-de-France GTFS data loaded, A takes 2 seconds and B takes 20 seconds :/

On my laptop, setting the PPR time limit to 5 instead of 15 seems to reduce significantly the running time : from 20 seconds to 8 seconds.

Using the OSRM bike module with 5 minutes of ride limit bot sides, it takes forever.

[laem]

Question : considering that the multimodal mode seems to be the culprit in provoking unbearably long computing times, would it be possible to use a pseudo-multimodal mode that tells motis to use an imaginary mode that creates straight lines at a defined speed (e.g. walking speed) from origin to transit stations ?

[felixguendling]

Thank you for reporting. We'll look into it.

My guess is that interval extension goes a bit overboard with an overly large start interval. A ontrip query (earliest arrival) would probably be way faster.

On europe.motis-project.de, A takes 3 seconds, B takes 5 seconds.

Even if 3 seconds and 5 seconds are not particularly fast (taking into consideration that the locations are quite close), I would also not say that these timings overly problematic. But for the second query I could also produce query times around 20 seconds on europe.motis-project.de.

Can you try to limit the maximum walking time between stops (for transfers) to 20 minutes like it's done here in the transitous.org configuration?
https://github.com/public-transport/transitous/blob/71b55043cf8f8385b392463a252dc56f0896723e/motis/config.ini.j2#L37-L38

Maybe even less (15 could still be fine).

B takes 20 seconds

Can you check in the response where the time went?

You can check in the browser developer tools' network tab:

Here, for example street routing (mumo_edge_duration) was 729ms and total duration was 19 seconds. So in this case, skipping street routing with a pseudo direct line distance estimate would not even save 1 second from the 20 seconds total query time.

[laem]

Thanks for your prompt answer !

Here is the capture of the statistics data for each server (mine vs europe.motis) on the same request.

[laem]

Setting your recommended option to 15, the computing time for the query 48.851698;2.406223 to 48.850369;2.308668 is reduced to less than 1 second !

[nigiri] 
max_footpath_length=15

Looks magical. Do you have some documentation about this option ? How would it affect the quality of our results ?

Comparing the results to the official calculator, Motis's results look good, adding a good option (A regional train) that is not listed by the official website :)

[felixguendling]

Nice! 😄

Since the routing algorithm itself (RAPTOR, implemented in nigiri) can only do one footpath per round but not the combination of several footpaths (like A-B and then B-C), we have to pre-compute the combinations. So for example if the input timetable contains A-B, B-C, and C-D, then we pre-compute additionally A-C, A-D and B-D to enable the algorithm to find those combined footpaths. In a city (like Paris) where everything is quite close (a public transport stop at almost every corner), this leads to chains of 10+ footpaths with footpath durations of several hours. Those options are theoretically possible but not very useful for the user. Considering to walk from all stops to all other stops is also quite expensive in the algorithm. That's why the max_fooptath_length option exists to limit the length of combined footpaths. The preprocessing step will stop combing footpaths if the combined footpath reaches 15min in your case. I would not expect that the result quality suffers from this. There will definitely be extreme cases, where (mostly at night) those very long combined footpaths enable a better connection. But I'm not sure who would be really interested to walk so long at night.

[laem]

Thanks ! So if I understand well, this option should lead to good results in Paris, but could have bad consequences in poorly connected places, like rural places with only a few bus stops ?

[felixguendling]

It doesn't cut the original footpaths from the GTFS data short. So if the GTFS data contains A-C and not just A-B and B-C, it does not matter what value you set max_footpath_length to. This only refers to transitive footpaths.

In the future, we will have a mode where we compute footpaths up to max_footpath_length minutes with our own foot router (profile based). In this case, we would ignore GTFS footpaths and no footpaths longer than max_footpath_length can exist.

[laem]

A new observation comes from my testing of the French network : asking for long duration osrm bike connections in Paris is slow, e.g. 60 minutes bike duration. Which is understandable : Paris has lots of metros and buses, and Nigiri is faster than a long osrm simulation.

Why would I ask this long of a bike intermodal end ? My use case is to enable users of my app to find long range train connections even if there is no local transport network, using the bike mode as a good proxy because it's slower than a ~direct bus and a train, but faster than a overly complicated transport connection.

Then, it's up to the user, once she knows which is the closest train station, how to go there, maybe a friend or family can use their car to drop them.

Hence the 60 minutes (or more) bike start and end option. As far as my comprehension goes for now, the ideal option would be a flexible time : if the origin transport network is dense, use a ~15 minutes bike option which is very fast even for a destination in Paris. If the origin transport network is sparse, use a 1h bike option. I understand that this option can sound like magic, but it's an important limitation currently for me.

As I already compute metrics of transport density for my GTFS networks, it's far from impossible to go this way, but I wonder if other people have come across this complexity in intermodal transit calculation :)

[mority]

When proxying the transport mode like that, just keep in mind that there might be edge cases in which a closest station is missed. E.g., if the coordinates are close to a pedestrian bridge, the foot router might use that bridge and find a short route on foot. However, bikes and cars may not use the bridge, hence they might find a different closest station. In the majority of cases the routes for foot, bike and car do not differ that much, so the approach is probably fine for your use case.

I am interested to hear what transport density metrics you use and how they can be applied to the selection of the intermodal transport mode.

[felixguendling]

asking for long duration osrm bike connections in Paris is slow

It could be way faster if you use a IntermodalOnTripStart (which only uses a single departure time) instead of the IntermodalPreTripStart that takes an interval. Of course it also gives you way less results (not all optimal journeys departing in the departure interval - instead only the best journeys for this one point in time - considering waiting time until the first departure as travel time). But depending on your use case, this might be sufficient.

As @mority mentioned, using a different means of transport than the one you actually mean (e.g. bike instead of car) can lead to journeys that do not really make sense. Instead of using bike with 60 minutes, it could make sense to use car with 20-30 minutes to get correct results.

In general, to get a rough estimate of transit net density, it might be an option to make a LookupGeoStationRequest and determine the stop density (e.g. stops per square kilometer) at the starting location.

[laem]

Thanks for you answers. Yes, my approach is not rigorous, but I plan on letting the user choose the start and end modes after giving him hints about what the capable train stations are around him.

In the case of a user that is simulating a trip from his city to a city he knows, it's less useful : people in France know what's the right train station to choose. It's still appreciable to not have to input the train station, but an approximate clic on the map. However, for a discovery approach, Motis+bike is the best way I've found yet to direct his attention to the most pertinent station without asking him any question.

The aim is to produce a "recommended high order result" that can then be customized : "OK on arrival there's 15 km to Rennes train station, what about if I rent a car ? Or maybe a bike ? Mmmh no I need to find a bus there at walking distance. Oh, I can even ask for a path without stairs, cool [click !]".

I've conducted more tests after my message yesterday, and it appears that in France, only Paris breaks the running time with the OSRM bike 60 minutes option. Looks like I can just set the bike option to 10 dynamically when the destination is close to Paris where the density is crazy. Arguably, Lyon, the second densest city in terms of transit, handles 60 min bike well.

Instead of using bike with 60 minutes, it could make sense to use car with 20-30 minutes to get correct results.

Yes I could try that, but some problems could be worse : parts of the city where cars aren't open to cars. Among the three means walk bike car, all of them are forbidden in some places (motorways / pedestrian bridges / nocar neighborhoods or parks).

[felixguendling]

Regarding the Paris issue: with the bugfix contained in the latest release v0.12.10, MOTIS loads way less trips (and should also produce way less log output). I didn't have time to measure anything, but it feels like the routing in Paris (and overall) is now a bit faster.

[laem]

Thanks ! I just finished a new dedicated server with 64Go at https://serveur.cartes.app with the latest Motis. I'll try Paris again :)