Hi,
I just wondered if it’s possible to worsen the weight of an edge if it’s already used in the same route.
Writing the functionality shouldn’t be too hard, but maybe something like this is already existing?
See the custom weighting docs where a set of edge IDs is just blocked or see the PR 420 for better alternative routes and therefor better round trips. Or did you mean something else?
Hi Peter,
yes exactly, if you want to create a roundtrip or add a waypoint, it may happen that edges are taken twice. Sometimes it is probably necessary to use the same edge twice (because the alternatives are not actual alternatives).
I first thought that using the approach as described in the docs would be a good idea. I do not think that adding an edge to the visited set on calcWeight is correct and probably there is no other possibility in the Weighting class to get the Set of already visited edges.
Maybe extending the DijkstraBi might be a solution. But you create one path for each waypoint-to-waypoint and just merge these shortest paths. So probably this will not help.
Actually I am interested in calculating round trips. As far as I can see from skimming your code, you do a Dijkstra up to a given distance and search for the best round trip in that network.
I wanted to pursue a simpler approach: Add waypoints to create a roundtrip that is reasonable good (FirstWaypoint = LastWaypoint). This is definitely not a really good approach but I think it could provide quite good roundtrips.
What do you think? Is your PR runnable? I would like to test your approach and maybe finishing that PR, if the results are promising. I saw that you extended the MiniUI, is that the best way to run and test it right now?
It is runnable und used from a client but I also will merge it back to master in the next couple days.
Exactly, that is the solution. But finding good alternative paths (or a round trip) is then still not solved. Therefor I’ve implemented the alternative path search via a plateau method making it useable (and a bit added of this so called ‘penalty’ approach for the round trip). But still there are possible improvements I plan to integrate soon.
Not sure what you mean. You can start the web UI and provide some URL parameters to visualize the round trip. Visualizing the alternatives is currently not that simple as the Java API needs adoption to return multiple paths.
I wanted to pursue a simpler approach: Add waypoints to create a roundtrip that is reasonable good (FirstWaypoint = LastWaypoint).
What do you mean here?
Hi Peter,
It is runnable und used from a client but I also will merge it back to master in the next couple days.
these are great news. I’d love to work with roundtrips.
I wanted to pursue a simpler approach: Add waypoints to create a roundtrip that is reasonable good (FirstWaypoint = LastWaypoint).
What do you mean here?
Well I thought about generating round-trips independent from your PR. I thought it would be nice to create a roundtrip by finding a number of nodes. Then find shortest path through all these waypoints and end at the start. This would be a cheap way of calculating roundtrips. If you select the nodes clever I think that the roundtrip could be quite good. But it won’t be the best possible roundtrip with approximately that distance.
How do you want to find these points and why is NP-complete (TSP) cheap 
? See eg. here
The whole thing is rather approximative, there is no optimal solution like for A-B routing.
Hi Peter,
links are still not clickable 
However, I know that TSP is NP hard (even though there are good heuristics). But I don’t want to solve a TSP. I want to find a way from A-B-C-D-A. No permutation of nodes.
I wanted to solve the following problem: Find a reasonable good round trip that is approximately X km long. Therefore, you could pick 3 nodes. One node is start/finish. For a first version the nodes B,C could be on a circle around A with a given radius.
As I said, no magic, no optimal solution, but the calculations are rather cheap, I guess.
The whole thing is rather approximative, there is no optimal solution like for A-B routing.
Well I am no CS genius, but I think there is an optimal solution. Just discussed this with some algorithm experts. The problem could probably be formalized as constrained shortest path, with upper and lower bound (which is, suprise - NP). Due to the two bounds the problem is also a special form of the longest path problem (which is again, suprise NP). So I think solving this problem optimally is not possible for graphs larger than Monaco (or something really small).
Best,
Robin
Yeah, that is a discourse bug if you just paste a link&save. Please try again: Visiting every pub in Dublin - GraphHopper Directions API
For a first version the nodes B,C could be on a circle around A with a given radius.
That is the version I have implemented except that I just use A and B and make sure that the reverse tour is different enough via the alternative path search
Well I am no CS genius, but I think there is an optimal solution.
Sure, for three points it can be easily calculated but the question is how to pick these nodes to achieve the desired length and what if the are awkward positions so that you don’t get a circle? … just start implementing and you’ll see that this looks simple but needs a lot tuning to avoid artificial results.
That is the version I have implemented except that I just use A and B and make sure that the reverse tour is different enough via the alternative path search
Really? 
Well so I am obviously not the first one to come up with that idea.
Sure, for three points it can be easily calculated but the question is how to pick these nodes to achieve the desired length and what if the are awkward positions so that you don’t get a circle? … just start implementing and you’ll see that this looks simple but needs a lot tuning to avoid artificial results.
Well I never said that finding good points will be easy. In my special case (you know I am the motorcycle guy), thought that I would want to find nodes that have a high number of bendy roads near by. I think this can be calculated in reasonable time for any graph. Visit every node and start counting (finding a good number and whats near by is something that can be found experimental). Probably you want to find a reasonable number of nodes, to be able to calculate a number of alternatives.
just start implementing and you’ll see that this looks simple but needs a lot tuning to avoid artificial results.
Just started with implementing an EdgeFilter that allows only unique edges. So I start with the easy stuff