N-nearest stops for pre/post/transfers

[traines-source]

To avoid weird routing results and reduce the number of relations where we return "no itineraries found", in addition to the fixed maximum duration for pre/post/transfers (from API parameters or config) we want to optionally include the n nearest stops. I.e. if within the set duration less than n locations are reached, extend it to the n nearest locations.

First step: Just for pre/post. There should be api params for n similar to the duration params.
Second step: transfers. There should be a config option next to max_footpath_length. Additional footpaths are added in a fixed way during import.

Since OSR doesn't discover timetable locations on its own, we still need to get the surrounding locations from the rtree in routing.cc. I think exponentially increasing the rtree bbox until a sufficient number of locations is found should be good enough for the time being. Some factor more than n locations need to be discovered since there might be other locations that are physically closer than the locations found according to the beeline/bbox. This is a heuristic but n is a heuristic anyways.

In OSR there is astar which supports early stopping based on the number of discovered locations I think. But since we still want to discover all locations within the configured walking duration, maybe it's easier to stick to normal dijkstra and pick an upper bound for the walking duration needed to reach the n locations, based on the bbox of the rtree (another heuristic, i.e. max(configured_walking_duration, upper_bound_walking_duration_to_find_n)). Then after OSR routing filter the obtained offsets by configured walking duration and n.

The maximum discovered distance should still be limited by the server limits given in the config. Since the main reason for the server limits is GBFS in dense areas and/or long range car journeys, maybe we should have a separate higher limit (or separately limit GBFS)? I would like to find an itinerary with 5 hours of walking if the next stop is 5 hours away.

Testing needed how often this creates unnecessarily long walking connections depending on n. I would hope a low default value like 5 would work nicely. Once we have multi-criteria routing that optimizes walking duration, we can increase the default value to more like 100+.

[mority]

Could we give osr a callback function with which it can ask motis if there is a relevant station at a certain location?

Then, we don't need radius estimates. Osr can start and every time it comes across a public transit stop it uses the callback to figure out if the station is relevant.

[felixguendling]

Could we give osr a callback function with which it can ask motis if there is a relevant station at a certain location?

Then, we don't need radius estimates. Osr can start and every time it comes across a public transit stop it uses the callback to figure out if the station is relevant.

If this is about making osr faster in case no stop was reached within the initial maximum pre/post transit time, I think it would make more sense to keep the Dijkstra search state (priority queue, distance map) so the search can be resumed. However, this is already an optimization. For the first version, we should keep it simple and not think much about any optimizations whatsoever. I think it's better to implement the naive version, then benchmark+profile and then we can think targeted how to improve it.

[mority]

I agree. It was more of a theoretical because I felt like we always discussed this as if radius estimation and possible expansion is the only approach.

But let's start that way and see how it works out.