OSM routing solution

[vkrause]

There's multiple different OSM-based routing modules in MOTIS:

• osrm (with foot, bike and car profile)
• ppr
• parking (does that actually route itself or delegate to osrm-foot/ppr?)
• Valhalla (experimental, not used by default, meant as an alternative for some of the other)

Those are used from other modules:

• nigiri can use either one of those for enabling intermodal routing
• gbfs depends on osrm-foot explicitly (as that's faster than ppr, although ppr would produce equally usable results)
• parking depends on ???

And there's issues with those:

• osrm, ppr and parking fail to import the full European dataset, running out of memory.
• osrm-foot is significantly faster than ppr (therefore used by gbfs) but ppr has the better results due to supporting profiles (and thus preferred for walking routes), but both use distinct databases and thus having both significantly increase the data import cost.
• parking is even more expensive to import
• Valhalla has a bit of missing API to be a viable full replacement for osrm and ppr, see Random expensive intermodal routing requests motis-project/motis#439 (comment).
• Valhalla integration needs work due to significant memory leaks (see also Random expensive intermodal routing requests motis-project/motis#439).

How do we resolve this?

Possible options:

(1) No intermodal routing, disable all of this.

Worst possible outcome IMHO, but can be a useful temporary step to unblock work on the GTFS pipeline while this issue is investigated.

(2) Make OSRM/PPR import work

At this point this would likely mean obtaining large high speed SSD storage and enable swapping. OSRM documentation suggests with a total of 350G a full planet file is importable. We have to consider that this isn't a one-time thing though, there is no support for incremental update. Whether ppr and parking also work with this then is unknown, at least parking seemed 3x more RAM-expensive in the local CH test.

When done all MOTIS features would become available.

(3) Make Valhalla work as a replacement to OSRM/PPR

This would likely mean development efforts on Valhalla and/or MOTIS. Valhalla seems able to import the full EU dataset with less than 24G RAM (although I/O heavy), so even a full planet import is not unthinkable. Valhalla does have support for foot/bike/car routing and could thus in theory replace osrm and possibly ppr (profile support to be verified). gbfs doesn't work with Valhalla yet, how that will perform eventually is unknown. And how this impacts/relates to parking is also unknown.

Going this way would enable intermodal routing for foot/bike/car in a first step, while gbfs and parking would probably take longer to become available.

[1Maxnet1]

• parking (does that actually route itself or delegate to osrm-foot/ppr?)

What it seems to me from this dependency graph, it uses ppr for routing.

parking depends on ???

Therefore I would say parking depends on osrm-car, ppr and nigiri.

(1) No intermodal routing, disable all of this.

I think it would be nice to enable more people working on the GTFS-pipeline. However, wouldn't it also be an option to not completely disable the modules, but instead (for now) only import parts of Europe as OSM data? This would allow to gain further insights in the requirements for importing (e.g. how many countries could we already import with the current setup), unblock the work on the GTFS-pipeline and would still allow for intermodal routing in some areas (e.g. in those were there are already maintainers for feeds or where additional interesting data like GBFS is available) which is also nice to test the new client implementations.

(2) Make OSRM/PPR import work

This would also be a nice option, but in my opinion depends on which funding is available. Is there any currently?

(3) Make Valhalla work as a replacement to OSRM/PPR

This would be awesome due to the following:

so even a full planet import is not unthinkable.

OSM Data of the whole world is not even three times the amount of Europe and a look on the map of transit.land of available feeds indicates similarly for GTFS data. And this would enable a bunch of new interesting options.

I would go for what I described in regard to (1) and would see if we can find someone to work on (2) and (3) in the meantime.

[vkrause]

• parking (does that actually route itself or delegate to osrm-foot/ppr?)

What it seems to me from this dependency graph, it uses ppr for routing.

That's good in the sense that it's apparently not as performance-sensitive as gbfs then, as it doesn't explicitly hardcode osrm-foot for this, that gives us more options. One more unknown here for me is what kind of OSM-based import parking does on its own though, unrelated to routing then presumably, that also seemed very expensive.

(1) No intermodal routing, disable all of this.

I think it would be nice to enable more people working on the GTFS-pipeline. However, wouldn't it also be an option to not completely disable the modules, but instead (for now) only import parts of Europe as OSM data? This would allow to gain further insights in the requirements for importing (e.g. how many countries could we already import with the current setup), unblock the work on the GTFS-pipeline and would still allow for intermodal routing in some areas (e.g. in those were there are already maintainers for feeds or where additional interesting data like GBFS is available) which is also nice to test the new client implementations.

Right, a smaller subset is also an option, but that would be a temporary setup only then, not a viable final state IMHO.

(2) Make OSRM/PPR import work

This would also be a nice option, but in my opinion depends on which funding is available. Is there any currently?

For now everything we use is made available to us for free, there is no immediately available funding/budget. Knowing exactly what we'd need would probably help with finding some. Also useful would be finding ways to verify this will work at minimal cost, e.g. on suitable hardware somebody happens to have temporary access to, a short term rented VM (assuming those can be obtained with sufficient RAM/storage at reasonably low cost), or finding people maintaining such setups elsewhere (OSM seems to have global OSRM routing on their website for example).

(3) Make Valhalla work as a replacement to OSRM/PPR

This would be awesome due to the following:

so even a full planet import is not unthinkable.

OSM Data of the whole world is not even three times the amount of Europe and a look on the map of transit.land of available feeds indicates similarly for GTFS data. And this would enable a bunch of new interesting options.

Let's be careful to not raise the expectations even further ;-) I have no idea how MOTIS would behave when faced with hundreds of totally disconnected networks for example.

Valhalla does have a few other points that do look relevant besides the more efficient import (and thus update), like detailed configurable profiles without needing a database rebuild (to be verified if those reach the same quality as ppr for accessibility routing, I have a hard time judging that), as well as support for elevations and traffic data. FOSSGIS e.V. people seem to have operational experience with running this for the full planet, I'll try to gather some info from there as well.

[hbruch]

What requirements exist for the routing? I use Graphhopper in a few projects and am very happy with it, regarding performance, profiles and memory consumption.

[vkrause]

What requirements exist for the routing? I use Graphhopper in a few projects and am very happy with it, regarding performance, profiles and memory consumption.

That's basically option (4) then: Implement an entirely new OSM routing integration for MOTIS. That's more work but probably not prohibitively expensive either, following what's already there for OSRM/Valhalla. I haven't really looked deeply enough into the implementation to know the requirements from MOTIS on that level though.

[PartTimeDataScientist]

It could be an option to use a more generic routing API like https://github.com/gis-ops/routingpy as basis. Doing so would allow to switch the routing backend anytime later...

[felixguendling]

Is there any routing solution that can work with OSM delta updates like this?

---

Regarding the integration of new routing services, I was thinking a bit about since some months now. This is what I came up with. It also would solve a lot of nitpicks I currently have with MOTIS as it is now (like really old Flatbuffers version and the fact that there's no distinction between internal and external APIs hence no API versioning/stability).

I was also thinking about a more generic API or basically a new architecture for MOTIS:

In contrast to the monolithic architecture of MOTIS, this would be service based. So the orchestrator service could be written in any programming language (my favorite would be Rust). The other routing services (mainly for first mile + last mile) could be addressed via a load-balancer reverse-proxy or directly.

• To make a developer setup as simple as possible, a docker-compose.yml could be provided that already sets up the orchestrator, nigiri and some street routing services.
• For small production instances, docker-compose.yml would still be sufficient while larger setups have the option to use Kubernetes to scale each services separately. This is important for the following reason:

This way, the expensive OSRM part is needed only once (requests need maybe 10-20% CPU from OSRM and the rest is in nigiri - so having 5-10x more nigiri instances with less memory makes sense).

Basically, this architecture would eliminate MOTIS as it is now and would therefore be "MOTIS 2.0".

The communication protocol between the intermodal orchestrator and the street routing services could be standardized. Then:

• Those services can either implement this protocol directly
• You could have a proxy that converts requests (no need to touch any code in the orchestrator)
• Or inside the orchestrator there could be a RoutingService interface and if you want to add a new routing service, all you need to do is to implement this interface.

This would bring a lot more scalability, extensibility and flexibility.

[jbruechert]

Making the routing part swappable sounds great!

I would appreciate if the new architecture would still be simple enough to be able to run outside docker, since I basically can not use docker in the environment the current Transitous (development) instance is running in.

As far as I understand the current architecture, all communication between modules already goes through flatbuffers, which should in principle allow things like splitting out modules into a new process dynamically with a config option, since you can easily serialize / deserialize the communication between them already.

Whether the different modules are then implemented as shared libraries that can be either loaded in the main process or in a separate runner, or whether always the same executable is launched with different options is then an implementation detail.

You could still use different programming languages fairly easily, as pretty much all of them can call C, and when you are serializing everything already, you can easily pass data across this boundary.

[felixguendling]

should in principle allow things like splitting out modules into a new process dynamically with a config option,

Yes, we already have some code for remote operations, e.g. here:
https://github.com/motis-project/motis/blob/7af7b7402a3c469827fb7403bfe22ef5a4a6dcaa/base/module/src/registry.cc#L50-L79

That's also one reason why we have our own (stackful) coroutine library (written when C++ didn't have language support for coroutines):
https://github.com/motis-project/ctx

So MOTIS with its current architecture is prepared to scale to multiple servers. Add a websocket load balancer in between plus maybe an auto-scaling mechanism from one of the big cloud vendors, and you're almost there.

However, not having to maintain all this would also have some benefits :-)

I guess everything that can be started with Docker/Podman/etc. can also be run standalone. And if the orchestrator would be written in Rust, it would even be an option to statically link nigiri.

It's not urgent.. so no need to decide anything now. Just wanted to share some ideas :-)

[vkrause]

Recommendation from people at the OSM Hack Weekend in Karlruhe is GraphHopper. Incremental updates are not supported by any engine, GraphHopper is said to be able to do imports on <= 128G RAM and without SSDs for the full planet. Valhalla would be the second choice due to sub-optimal results over longer distances when crossing routing tile boundaries (as we mostly do short-distance routing that might be less of an issue for us though). OSRM is said to not be viable on realistic hardware (needs >=512G RAM).