Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Using turn costs, not just turn restrictions #1590

Open
easbar opened this issue Apr 1, 2019 · 5 comments · May be fixed by #2957
Open

Using turn costs, not just turn restrictions #1590

easbar opened this issue Apr 1, 2019 · 5 comments · May be fixed by #2957

Comments

@easbar
Copy link
Member

easbar commented Apr 1, 2019

OSM data only contains turn restrictions like 'right only' etc., but graphhopper routing can also handle turn costs, for example to prefer routes with less turns, less left-turns or similar. However, there are some open questions how turn costs should be handled, especially for weightings other than FastestWeighting. See discussion in: #1586 and the same problem with headingPenalty for, e.g., ShortestWeighting: #485

@easbar
Copy link
Member Author

easbar commented Apr 1, 2019

But which use case do you have in mind where "time != weight"?

I could think of a weighting function that e.g. includes toll-road fees, gas consumption, distance and time. To combine these factors one has to use conversion factors, just like we do for ShortestFastestWeighting. Putting a penalty on turns when not using the fastest (purely time-based) weighting can also be achieved using such a conversion factor, so I agree it should be no problem to think of the turn costs as turn times and for some special weightings one has to use a conversion factor.

Hmmh, indeed. This is ugly and one reason more (for me) to remove ShortestWeighting :D

Ok, but I am not fully convinced the ShortestWeighting is the real problem here. The problem rather seems that the weightings cannot control how turn costs are applied, because this is done by the TurnWeighting without 'asking' its underlying weighting.
The ShortestWeighting is at least useful for testing sometimes :)

@easbar
Copy link
Member Author

easbar commented Apr 1, 2019

As the defaultUTurnCost is in seconds - is this correct?

Good question, it looks like the default u-turn costs are not included in TurnWeighting#calcMillis at all (but for calcWeight they are added as seconds (at least for the fastest weighting...). -> added this to #1585. (Update: fixed via #1635)

@easbar
Copy link
Member Author

easbar commented Jul 29, 2019

I think it would be a good idea to let all weightings return the weight in units of time (same for edge weights, turn costs etc., make everything based on time), and probably also use the same units everywhere as well (for example seconds) (so we can clearly communicate which range of values is supported). Of course not all weightings are based on time, but then they can just use some (weighting specific) conversion factors. Like we already do for shortest-fastest-weighting where there have to be such factors. Even for a pure distance-based weighting (shortest-weighting) its the same, just divide the distance by a constant 'speed'.

I think this makes it a lot easier to reason about 'weights' than the current approach where weights do not have a specified unit. Also I think it saves us a lot of confusion about turn-costs, turn-times and turn-time-costs ;)

Before this I think we should get rid of TurnWeighting, see #1520 #1820

@easbar
Copy link
Member Author

easbar commented Oct 18, 2022

OSM data only contains turn restrictions like 'right only' etc.

Just for reference: that is not entirely true. For example there are turn restrictions with implicit=yes which are not necessarily forbidden, but maybe should only be avoided by some penalty: https://labs.mapbox.com/mapping/mapping-for-navigation/implicit-restrictions/
Also the give_way tag (currently highway=give_way, but there is a proposal to include this as restriction instead), or traffic lights, stop signs etc. could be modeled by finite turn penalties, not strict restrictions.

@karussell
Copy link
Member

karussell commented Oct 18, 2022

btw: this branch determines turns based on the angle / orientation, which is stored in the edge. And then you can configure the turn costs for a right or left turn (in seconds) in the custom model. See these screenshots. In my previous work I tried to base the turn determination (if left/right/straight) purely on the topology but this led to subpar quality. Probably a combined approach is the best but for now using the orientation only seems to be a good enough start.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants