THOR algorithm for OsmAnd

[Norbert80]

OsmAnd needs a new routing algorithm for car mode because of bad performance. Graphhopper and OSRM do not fulfill the requirements because they don't support conditional edge-weights at query-time. This is necessary to support options like avoid highways and so on without the need for a separate CH-graph for each combination of options.

It should be investigated if THOR algorithm (Tiled Hierarchical Open Routing) which supports multi-modal routing can be implemented in OsmAnd to replace the current routing engine.

Issue on OSRM limitations:
Project-OSRM/osrm-backend#2377

THOR links:
https://github.com/valhalla/thor
https://mapzen.com/blog/valhalla-intro/

Please also note discussion at:
https://groups.google.com/forum/#!topic/osmand/RavNh1aMbR8

[njohnston]

In general, OsmAnd's current routing works fine for me but I mostly use it for walking and cycling, and typically on distances under 20 km. However, multi-modal routing (including public transport) would be extremely useful.

THOR is part of Mapzen's Valhalla routing engine, which is written in C++ and is open source.

As @Norbert80 points out, Valhalla supports multi-modal routing. A demo is available.

OsmAnd recently added support for showing transport stops and their associated routes. This is really useful. I've used it in several places already. Full multi-modal routing (e.g. walk from your hotel to bus stop or station XYZ, then walk, then take a ferry, ...) would be extremely useful.

Mapzen also provides transit.land, a project to collect open public transit data from around the world. This data could be integrated into OsmAnd maps or made available as separate downloads. (For some areas the data is large.)

Having multi-modal routing in OsmAnd would be great. Perhaps it could be implemented in a separate paid-for plugin to help fund the development :)

[vshcherb]

It will be a quite radical switch and definitely will take a lot of time, we would like to make sure that THOR will stabilize first and support all features currently present in OsmAnd.

[njohnston]

@vshcherb: thanks for the response. Initially I would propose using Valhalla as an alternative routing engine and leaving the existing one unchanged. I realise this adds complexity though.

What routing features does OsmAnd support which Valhalla currently doesn't? On the other hand, Valhalla supports elevation-aware routing and multi-modal routing, both of which would be extremely useful.

[vshcherb]

Valhalla supports elevation-aware routing and multi-modal routing, both of which would be extremely useful.

This is useless if data is not present, if we are talking about online routing, that's possible to add but it doesn't have much priority. For offline routing, lots of preparation needs to be done in the map files.

[njohnston]

This is useless if data is not present, if we are talking about online routing, that's possible to add but it doesn't have much priority. For offline routing, lots of preparation needs to be done in the map files.

Offline support would be much better. I realise it's a lot of work but it would be extremely useful, and as I said in my first comment, I'd be happy if this functionality was in a paid-for plugin.

I think it would probably be best to provide the data (transport at least) in separate downloads (in the same way as contours and hillshades, for example), as it's quite big and might not be useful for all users.

[vshcherb]

The routing itself is not that bad and we can't compare it directly with others. The problem of the slow routing engine, we actually plan to introduce CH as a primary routing engine and keep osmand routing as a secondary. Though i'm not sure THOR is mature enough.

[utack]

Sorry to hijack the THOR issue:
But what about going the OSRM way, now that it has lane guidance?
Or do you prefer to keep a fully flexible routing that can avoid arbitrary roads or road-properties?

[vshcherb]

@utack we already have these options, it would be bad if we just drop it. I feel that more people use that options, then people who calculate > 1500km routes. Slowness of course effects everyone but for 30-50 km routes it is negligible.

[utack]

Certainly, plus you can usualy fall back to OSRM online

[Norbert80]

@vshcherb I totally agree that the actual implemented routing options should not be dropped. Performance shall be improved as good as possible while at least maintaining the implemented options.

Regarding your CH plans... it would be interesting to get a bit more information what you mean with "primary" and "secondary"...

[sonora]

No immediate plans.