How to request / force more alternative routes?

[apfz]

I am trying to provide the end-user of more alternative routes even if OSRM only provides one route between points.

I read an interesting thread here: https://github.com/Project-OSRM/osrm-backend/pull/4047

but I am unsure how I can actually implement this in OSRM. With alternatives=true I am often getting only one route. Is there a way I can adjust this and I am allways getting 5 alternatives in some way?

Thanks

[danpat]

Unfortunately, there's no simple way to solve this. The reason OSRM doesn't return many alternatives in some situations is because finding "reasonable" alternatives is computationally difficult, or impossible with the graph structure we have available.

The speedup algorithms that OSRM implements have the unfortunate side effect of reducing the number of viable alternatives that can be found.

The best reference I know of to get started researching this topic is Chapter 5 of this paper:

http://algo2.iti.kit.edu/documents/Dissertation_Kobitzsch_Moritz.pdf

You can try playing around with some of the constants defined in the various "alternatives*" code files, but generally changing those will lead to more low-quality alternatives (i.e. alternatives that are very similar), or even fewer alternatives than we already return.

[apfz]

Thanks for your explanation. I am still unsure why it is not easy to replicate the example from the thread in #4047 as it seems to be working quite well. I will try to dig into it more.

I am specifically looking to create an alternative route by avoiding a part of a currently active route.

Thanks again for your suggestions

[danpat]

The current code implements the logic you're describing - this is called the "overlap" factor - you can adjust that to change how it works. The other two factors are "stretch" - how much longer/shorter is the alternative to the main route, and "local optimiality" - do all the sub-parts of the alternative represent optimal paths in their own right. I highly recommend reading the paper I linked for more details on why finding alternative paths algorithmically is difficult.

There are two different speedup graph shapes in OSRM - CH and MLD. Each requires a different implementation of alternative route finding.

The factors that affect the returned routes can be found in these two bits of code:

https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/routing_algorithms/alternative_path_mld.cpp#L37-L57

and

https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/routing_algorithms/alternative_path_ch.cpp#L27-L29

You should also be able to pass alternatives=5 to the API - however, the algorithm is not guaranteed to return any alternatives - this parameter means it will return up to 5, if it can find some that meet the filter function. I don't think I've ever seen 5 returned for CH.

[AlexKaravaev]

@danpat Hi there! I have same need for generating a lot of alternive routes, but even with tuning the parameters you said, I can not get the result of @daniel-j-h in https://github.com/Project-OSRM/osrm-backend/pull/4047#issuecomment-303123687_ .

Maybe you know, what I should change in source code to get as much routes as possible(For example this many roots, as mentioned comment has)

[danpat]

@AlexKaravaev Are you using the CH or MLD algorithm? If you're using CH, then there simply won't be many alternatives - they do not exist in the graph. You must use MLD, and possibly mess around with the options in https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/routing_algorithms/alternative_path_mld.cpp#L37-L57

But again, acceleration graphs (like MLD and CH) essentially eliminate many possible alternatives, so sometimes there are none to be found.

You may like to read about https://en.wikipedia.org/wiki/K_shortest_path_routing - this will return the K shortest paths between two points. However, note that these algorithms depend on the shape of the graph, and the seach graph in OSRM does not exactly match what the road network looks like (we use shortcuts to speed up searches, and this runs counter to many standard algorithms).

[AlexKaravaev]

@danpat I am using MLD, I tried with CH, but it returned almost none(as you have clarified for me now - why). I do get around 5-6 routes with those parameters changed, but I need them as much as possible. Do you know the exact parameters I must choose? Or 5-6 route is best case scenario for MLD?

Thank you for this wiki article, I will check it out, however, I want something to work out of box with osrm, and this is not the case here, but anyway thanks on giving me this algorithm!

[danpat]

@AlexKaravaev You probably won't get many more - they simply can't be found by the current implementation, it's not designed to work like you want.

Between any two given points on a large graph, there are billions of alternative route options. Most of them are terrible, or are very similar to each other (only very tiny differences). The fundamental problem of alternative route finding is sorting through all the billions of options, and picking the "good" ones. It's not an easy problem to solve. OSRM probably doesn't have what you want.

[AlexKaravaev]

@danpat Okay, got you. Still OSRM is the best one out there for this purpose. Thanks for explanaiton!

[sebgir]

The current code implements the logic you're describing - this is called the "overlap" factor - you can adjust that to change how it works. The other two factors are "stretch" - how much longer/shorter is the alternative to the main route, and "local optimiality" - do all the sub-parts of the alternative represent optimal paths in their own right. I highly recommend reading the paper I linked for more details on why finding alternative paths algorithmically is difficult.

There are two different speedup graph shapes in OSRM - CH and MLD. Each requires a different implementation of alternative route finding.

The factors that affect the returned routes can be found in these two bits of code:

https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/routing_algorithms/alternative_path_mld.cpp#L37-L57

and

https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/routing_algorithms/alternative_path_ch.cpp#L27-L29

You should also be able to pass alternatives=5 to the API - however, the algorithm is not guaranteed to return any alternatives - this parameter means it will return up to 5, if it can find some that meet the filter function. I don't think I've ever seen 5 returned for CH.

Hi, I'm running a vanilla OSRM Backend server on Docker. What is the procedure to "play" with these parameters. Are they accessible in any way from the outside or it is mandatory to compile a new version and execute it outside Docker ?

[danpat]

You need to recompile the code after making a change. You can to this in three steps:

1) Clone the git repository with git clone https://github.com/Project-OSRM/osrm-backend.git 2) Modify the files listed above 3) Run docker build -t osrm/osrm-backend:LOCAL -f docker/Dockerfile . to build local docker images

It'll take a while. You should now be able to do docker run -t osrm/osrm-backend:LOCAL instead of -t osrm/osrm-backend:v5.22.0

Re-run steps 2 and 3 to make more changes.

[sebgir]

Thank you @danpat for that very comprehensive and simple procedure. I'm sure it will help others too.

Regards

[waldobeest]

@danpat docker build -t osrm/osrm-backend:LOCAL -f docker/Docker . the dot at the end had me running around for a bit.

[danpat]

@waldobeest ah, thanks - I fixed my comment for future people who find this thread.

[sebgir]

If it could help others here's my parameters to generate a maximum number of alternatives (like 10+) :

    double kSearchSpaceOverlapFactor = 1.8;

     unsigned kAlternativesToUnpackFactor = 4000;

     double kAtMostLongerBy = 0.3;

     double kAtMostSameBy = .7;

     double kAtLeastOptimalAroundViaBy = .025;

      double kCellsAtMostSameBy = 1.0;

Don't forget to use : &alternatives=[big number] at each query and set --max-alternative to a proper value when starting container. When using &alternatives=true only one alternative will be choosen, everytime.

This is an issue I struggled a moment on (I consider starting an issue thread on that topic to discuss it). One would expect &alternatives=true output [--max-alternatives] alternatives ?

[danpat]

It's --alternatives=true for backward compatibility reasons - the [big number] variant was only added later.

[waldobeest]

In my case, I am generating alternative routes to find a route between A and B which avoids a specific area (polygon/ multi-polygon). The check if the route is going through an area is currently done outside of the osrm-backend, which means I have to request alternatives and test each one. This is not an exhaustive approach, since whatever values for the above parameters are selected, there could be a case where: A) there is a feasible route just outside of the parameters. kAtMostLongerBy and kAtMostSameBy have been the parameters that I have changed to get this to work in most cases. B) The number of alternatives I requested was not high enough to iterate and get to a route which avoided the region. Simply, my approach is a bit of guesswork for the edge cases. Is there an approach that I can take that is more consistently going to return a route which avoids a / an array of polygons?

[danpat]

The speedup techniques of CH and MLD, plus alternative routes, plus "avoid polygon" - these all have contradictory goals. I do not think you'll find a good solution by trying to combine all this stuff.

If what you really want is "avoid polygon" behaviour, you may want to look at another routing engine that doesn't employ the speedup graph that OSRM does - it's in fundamental conflict with querytime graph adjustments like you want. https://github.com/valhalla/valhalla/ and https://github.com/GIScience/openrouteservice both support "avoid polygon" interfaces.

You could also resurrect the A* implementation for OSRM at https://github.com/Project-OSRM/osrm-backend/tree/algorihm/astar and add support for "avoid polygon" there - but it would be a lot more work.

[caleb87]

I built from source. After modifying the cpp files, which parts do I have to reprocess for MLD? osrm-extract osrm-partition osrm-customize

[github-actions[bot]]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.