Basically the input would only be one point, and I’m hoping to find the shortest path that would return to that same point
There is a round_trip algorithm but it is not really a shortest circuit algorithm and instead just a suggestion where the heading and length can be indicated (but they might differ a lot in the result).
Do you know how dependable/optimal the length suggestion is? For example, if I set round_trip.distance to 0, will Graphhopper effectively return something within the realm of optimality or is it a case where I could get something that’s 1km when the optimal is 100m?
I ask because the documentation makes round_trip mostly sound like a fun experiment, and not necessarily something design for operational efficiency.
It is definitely not reliable as it is just a heuristic with a lot of guesswork. Just try it out to see how it behaves.
not necessarily something design for operational efficiency.
I don’t understand what you mean. It is a hard problem to calculate the “shortest circuit”. It is definitely not as simple as calculating from A to B and we try to give a good enough result in a meaningful response time.
Yeah, I was actually just going to update this with my tests. For those who stumble upon this in the future:
- Setting
distanceto 0 does seem to try and minimize the final distance, but it will give you some pretty funky and unrealistic results that aren’t actually usable. -
250mseems to be a good value for producing realistic results (though I suspect this would depend on the city)
I meant mostly whether it could be useful in practice. I was worried that the engine would route vehicles on wildly incorrect paths because the algorithm might not be designed to be operationally efficient (in the sense of physical/field operations)
Usually it works better for longer trips. 250m seems to be very short. What is your use case?
The use case for round_trip is more to explore the area e.g. per bike.
Delivery trucks often have to circle around a parking spot while they wait for it to be open (since they can’t stand still in traffic)
I see, but why not just request a random point nearby and then go there forth and back? This is basically also what we do with round_trip internally (with more points) but you’ll have more control over the details.
That’s actually the implementation I’m currently using. I was hoping for a cleaner way of doing it. The other problem is that selecting a random nearby point isn’t always dependable because of road quirks (e.g. one-way traffic).
However, from what you’re saying, it sounds like using round_trip might have the exact same problems?
Yes
Ah, that’s too bad. I guess I’ll see if I can find an alternative way around this problem.
If you calculate a route from a point A to A and ask for the shortest route the result is very simple: It is an empty route with zero distance. But obviously this is not what you are looking for. Since you are talking about delivery trucks I assume you need the ‘shortest circuit’ from A to A, but given a current direction of driving. This changes the problem, because now you are no longer routing from point A to point A, but from a road (or an edge, or some certain direction) outgoing from point A to point A.
Did you try the curbside parameter, yet? I think it might solve your problem:
Try this route for example.
This forces the route to start in Northern direction (such that the first given coordinate is to the right of the road relative to the driving direction) and like wise to end going in Northern direction (again with the coordinate to the right of the road).
One gotcha here is that the points must not be exactly the same. I never thought about this use case, so this is something we need to reconsider maybe. But as a very easy workaround you can a slightly shifted destination coordinate (as I did for this example). Note that it is shifted slightly to the South. If it was shifted slightly to the North you would get a very short route (no circuit), but if you then use curbside=left instead you get another circuit, this time going South. So depending on the direction the truck is going you could select either of the two circuits.
There is even another parameter you can use to achieve similar results: heading, like this, but as you can see it requires you to disable CH. But since the resulting routes will typically be very short this shouldn’t matter much.
The other gotcha is that, as you might have noticed, these links use our old maps UI (Driving Directions - GraphHopper Maps), because using the new one there is no simple way of setting the curbside algorithm and sharing a link like this (see curbsides, point_hints etc. · Issue #297 · graphhopper/graphhopper-maps · GitHub)
These are not just any circuits or randomly chosen roundtrips, but they are shortest paths calculated for the given constraints.
Btw if you are trying to implement this on a lower level you can easily use GraphHopper’s (edge-based) routing algorithms and constrain the ‘sourceOutEdge’ (the road the route shall start with) and you will get similar results.
Another issue you might run into is that in some case instead of a ‘nice’ circuit route GraphHopper will suggest doing a u-turn at the next junction, c.f. this and the following comments. You should be able to avoid this by raising the u_turn_costs parameter and we are also looking at ways to prevent these kinds of u-turns in the future.
So this ended up being what I went with. It was actually what inspired the other post about using “heading” and “curbside” together.
The implementation is a bit tricky since you need to know what the heading of the “right side” of the road leading to the parking lot is- in order to shift the destination correctly. Otherwise, like you mentioned, you get a very short route.
For those who encounter this in the future, the one gotcha you should be aware of is that when you shift the coordinate, make sure it doesn’t get shifted to the other-side of the road. Sometimes, you will have a coordinate that appears to be on one side, when in fact, it’s actually on the other side. This messes up the curbside parameter, though if you use heading, it’ll still work as expected.
Ideally of course, hopefully you can consider implementing this feature natively.
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.