Discussion about the new feature introduced here
Usage us simple: open the locally installed web UI and click to route somewhere then add &algorithm=alternative_route to the URL
Currently only works if ch.disable=true and performance is improvable.
Update: performance improvement can be achieved via landmarks.
So I can test or use this new feature with an own instance of graphhopper on an own server?
and it is not implemented yet on the public main server at https://graphhopper.com/maps/ ?
So I can test or use this new feature with an own instance of graphhopper on an own server?
Yes
and it is not implemented yet on the public main server at GraphHopper Maps | Route Planner ?
It is ‘implemented’ but not enabled, although we plan to do this for all (CH & none-CH) features soonish
Hi Peter
How does the alternative_route.max_weight_factor works?
I tried raising it, expecting to get more routes, but even when I raise it to a ridiculous number like 20 I do not get more routes (the alternative_route.max_paths is not the limit).
BTW, when I lower it (usually around 1.15) I start getting less routes
There are more factors involved. E.g. bad alternatives are filtered away with a too high alternative_route.max_share_factor (get more alternatives via increasing this) or a too low alternative_route.min_plateau_factor (get more alt. via decreasing it) another factor is the alternative_route.max_exploration_factor try increasing it to get more alternatives but this parameter affects performance a lot.
You should then being able to get more alternatives up to a certain extend. Keep in mind that the quality could decrease a lot when uncarefully changing the settings. Also note, that these parameters are specific to the current alternative search and could become obsolete (nothing planned for this or the next release and having an option to increase the alternative paths will be always present).
BTW: I’ll update the code with a faster search today or tomorrow (identical principle & parameters) and push out a release candidate thereafter
The big performance improvements for alternative routes are now pushed to master as well as further integration tests. Now I’m happy with this (although still not satisfied 
but the perf improvements are always time consuming and will get back later to it).
@karussell since the class was renamed to AlternativeBidirSearch, the Dijkstra suffix in naming could be removed from its uses (in code and tests) ?
Also now there are defined initial coordinates in MiniGraphUI:93-94 ?
That causes issues in running without modifying the coordinates to be inside the loaded graph.
AlternativeBidirSearch, the Dijkstra suffix in naming could be removed from its uses (in code and tests) ?
hmmh, not too important IMO, as the underlying algo is still a bidir dijkstra with goal 
Ups, will revert the code changes in the miniui
Hi
I wrote down the meaning of the alternative_route parameters, the possible values and the default values. I miss these information for two of the parameters, could you fill it up.
max_weight_factor – the maximum weight of the return routes, in compare to the best route.
Valid values >=1
Default value = 1.4
max_share_factor – The max overlap between returned routes
Valid values between 0 and 1
Default value = 0.6
max_paths – the maximum number of returned path
Valid values >=2
Default value = 2
min_plateau_factor - ???
Default value = 0.2
max_exploration_factor - ???
Default value = 1
Thanks, this can get indeed a better description. Let me try and ask if still unclear:
max_weight_factor – the maximum weight of the return routes, in comparison to the best route.
Valid values >=1
Default value = 1.4
Exactly, ie. how much larger can the alternatives be?
max_share_factor – The max overlap between returned routes
Valid values between 0 and 1
Default value = 0.6
max_share_factor is the maximum allowed distance (in reality it is the more generic ‘weight’) that alternative paths can share with the best route
max_paths – the maximum number of returned path
Valid values >=2
Default value = 2
Exactly. Valid >= 2 because if just 1 the user should not use alternative route calculation due to the overhead
min_plateau_factor - ???
Default value = 0.2
Similar to the max_share_factor this is also special to the algorithm and defines the minimum distance (again better: ‘weight’) that a branch from the source SPT must share with the destination SPT. See this image and the blog post with some more insights about ‘SPTs’ (shortest path trees)
max_exploration_factor - ???
Default value = 1
When the best path is found the algorithm could theoretically stop immediately but you can increase this value and more (but potentially worse) alternatives could be found
Also note that in the latest master (and since RC1) the default value has changed for this to 0.8, as we use bidirectional A* and alternatives of the same quality are found with less exploration
Hi Peter and others,
Does this feature work with low level API? I’m trying to construct a graph of my own and use this feature to find alternative routes between two nodes, but without success.
A piece of sample code is provided as below. I expect to get two paths from node 1 to node 3, i.e., both 1->2->3 and 1->3, but get only one.
Thanks a lot for your help in advance.
Best regards,
He
FlagEncoder encoder = new CarFlagEncoder();
EncodingManager em = new EncodingManager(encoder);
GraphBuilder gb = new GraphBuilder(em).setLocation("graphhopper").setStore(true);
GraphHopperStorage graph = gb.create();
graph.edge(1, 2, 10, false);
graph.edge(2, 3, 10, false);
graph.edge(1, 3, 20, false);
graph.flush();
graph = gb.load();
AlternativeRoute alternativeRoute = new AlternativeRoute(graph, encoder, new ShortestWeighting(encoder), TraversalMode.NODE_BASED);
// trying to tweak the parameters here
// alternativeRoute.setMaxPaths(5);
// alternativeRoute.setMaxExplorationFactor(5);
// alternativeRoute.setMaxWeightFactor(5);
// alternativeRoute.setMaxShareFactor(1);
// alternativeRoute.setMinPlateauFactor(0);
List<Path> paths = alternativeRoute.calcPaths(1, 3);
for (Path path : paths) {
System.out.println(path.toDetailsString());
System.out.println(path.calcNodes());
System.out.println(path.calcEdges());
}Sure, this works with the low level API. (If it works high level it works low level too ;))
See the AlternativeRoute unit tests. I’m not 100% sure but the problem here might be that the real lat/lon and distances are necessary for A* to work. So after you created the edges you should update the distance and lat/lon via e.g. updateDistancesFor(graph, 5, 0.00, 0.05);
Hi Peter,
Thanks for your response.
It seems the updateDistancesFor() calls are not necessary. For example, when I replace the graph.edge() calls in my code with those in your AlternativeRoute unit test (without the updateDistancesFor() calls), it can return the expected results (with the edge distance set in the graph.edge() calls of course).
It seems the feature manages to return multiple paths in some cases but not in some others.
case (1): the case I provided earlier is one example that it fails (only one path is returned).
case (2): below is an example when it successfully return two paths from node 1 to node 3:
graph.edge(1, 2, 10, false);
graph.edge(2, 3, 20, false);
graph.edge(1, 4, 20, false);
graph.edge(4, 3, 10, false);
case (3): and I am having trouble to get more than two alternative paths, for example, if I add two more edges to case 2:
graph.edge(1, 5, 15, false);
graph.edge(5, 3, 15, false);
and set
alternativeRoute.setMaxPaths(3);
I still get two paths, rather than three.
case (4): if I make a few changes to the edge distance in case 2, like below:
graph.edge(1, 2, 10, false);
graph.edge(2, 3, 10, false);
graph.edge(1, 4, 5, false);
graph.edge(4, 3, 15, false);
The returned path list contains two paths but they are the same: 1->4->3.
case (5): if I increase the edge distance of the last edge in case 2 by 1, that is:
graph.edge(4, 3, 11, false);
Then I will get only one path: 1->2->3.
I am just trying to test and understand when the feature works, when it does not, and why. 
Best regards,
He
Keep in mind that bad alternatives are excluded (see parameters above). So you would have to tweak the algorithm a bit to force returning some alternatives still a few possible tuning parameters are not made accessible as they are too low level. I think the first example should then produce the intended results.
It would be important to let me know if you have real world cases where some good alternatives are not returned.
Hi Peter,
Thanks for your reply.
Apparently changing the traverse mode to TraversalMode.EDGE_BASED_2DIR solves most of the cases I listed above (all expect case 1).
For case 1, it will work (i.e., returns both 1->3 and 1->2->3) if I reduce the distance for the last edge to a value in [14.286, 20) - 14.286 here is the round-up of 20/1.4, e.g.,
graph.edge(1, 3, 15, false);
smaller value will also work if I increase maxWeightFactor and maxExplorationFactor, e.g.,
graph.edge(1, 3, 10, false);
and
alternativeRoute.setMaxExplorationFactor(5);
alternativeRoute.setMaxWeightFactor(5);
Path containing loop will be returned if I make the following changes to case 1: a) make the edges bi-directional, b) keep the distance of the last edge no smaller than 20 (this is to be noted, because for a value smaller than 20, it will return the same “good” result as in bullet 2), and c) increase maxWeightFactor and maxExplorationFactor. For example,
graph.edge(1, 2, 10, true);
graph.edge(2, 3, 10, true);
graph.edge(1, 3, 20, true);
and
alternativeRoute.setMaxExplorationFactor(5);
alternativeRoute.setMaxWeightFactor(5);
then besides path 1->2->3, it also returns 1->3->2->1->3, but it does not return 1->3. 
It would be important to let me know if you have real world cases where some good alternatives are not returned.
Currently I am trying to work with a graph created by my own. I will certainly report if I come across anything wrong or missing for any real world cases.
Best regards,
He
Yes, this is expected as 5 times more exploration as required will lead to two ‘separate paths’ and then you connect them at some point. This is relative unrealistic scenario as nobody would say 5 times longer trip then the best is a viable alternative.
but it does not return 1->3.
Sorry, I fear you have to debug into the algorithm to find the reason
Hi Peter,
Thanks for your reply.
I guess the first thing I need to find out is that why path 1->3 is not returned when the distance of edge (1, 3) is no smaller than 20.
The interesting thing about the path 1->3->2->1->3 in the last case is that it reaches the destination node 3 already but does not stop there.
Anyway I will take a good look at the code (is there a documentation about this btw?). Thanks.
Best regards,
He
Hello GraphHopper community!
I am a bit new here , so I would like to know how things work.I ve heard you are a welcoming community so I will give it a try 
.
I would like to get into alternative routing, so it would be great if you could help me with some documentation or some research that I could read.
One thing is I would like to contribute if it is possible.
Another thing is I am more interested in the algorithmic part of the alternative routing.
Do you people think that something like this is feasible ?
Best regards,
Paschalidis Christos
See the pull request: https://github.com/graphhopper/graphhopper/pull/640 and in the class AlternativeRoute lots of papers are referenced.