gdt
commented
6 years ago <standard rant about "penalty"> (It may seem like I'm arguing about word definitions, but getting definitions right is a key part of reaching clarity and correctness.)
The job of routing is to choose a way to travel that a human would agree is best. Generally, that's a minimum of some metric which weights travel time and distance. For example, few would want to drive 10 km more to save 30s, or to drive 10 min more to save 2km. The exact blend of time/distance is not the issue here. But, pleasing routes have other characteristics beyond the predicted time and distance. (One might be minimum fuel use, but this is mostly similar.) People might downweight a route because it is more likely to result in a crash, or because it involves maneuvers that are particularly stressful or unpleasant -- even if they are faster/shorter.
Routing can be viewed as being divided into two pieces. One is evaluating the time/distance/other metric of a candidate path, and the other is search to find a path which minimizes the metric. We are only concerned with evaluating one path for a metric here.
I assert that the primary function of metric evaluation should be to produce a time and distance estimate that accurately reflects how long it would take if one tried to follow the path in question. Some things, like lights and left turns, really take time, and those time estimates are just part of "if I do X, how long will it take". The problem description above is I think concerned with changing how these estimates are done to make them more accurate. I'm writing this comment mostly to ground the adjustment of parameters in the goal of making accurate time estimates.
Then, there is a separate question of penalizing certain maneuvers because they are unpleasant or risky, even though they are not expected to take extra time. This is what "penalty" should be used for, with a 2-minute penalty meaning that someone would rather drive 1m59s out of the way than do that particular thing, but to save 2m1s they would rather do it. These penalties can result in routes that actually take longer to drive being chosen, even in "minimize time". But that's good, because actual humans prefer to avoid some things.
The real point of separating "penalty" for the time one is willing to spend to avoid something with the time that it is expected to do something is focusing on the primary job of evaluating a path, which is to accurately predict the outcome. It should be easy to output a chosen route in terms of expected waypoints and times (this is displayable once calculated) and then compare that to the actual track. Of course many things, like traffic_signals, cross-traffic turns, and stops, have variable times. But, things should at least line up roughly, without any systematic biases.
To estimate costs of turns (given enough spare time), I would examine GPX tracks for various combinations of road speeds and turn geometry. This is tricky due to varying fidelity of turn representations; the real questions are the min turning radius the car reaches, and how fast the turning radius changes.
My own intuition is that turns over about 20 degrees require slowing down (or should :-) but that's not so different from the proposed 45. And 70 is not so different from 110 - you have to reach maybe 20 km/hr for both. And certainly 150 requires really slowing down. However, it's not just the angle, but if one is turning across trafffic or in the non-conflicting directio (left/right US, right/left UK). And, making a turn that other drivers don't think is reasonable, at a speed below the prevailing speed, is likely to require a longer wait.
So I would suggest to write code that matches GPX to maps and evaluates time lost (vs full speed traverse) for each angle, with cross and non-cross directions separated, and plot time vs angle and then fit curves. Once this is done, I suspect that there will be little need for penalties (in my sense of the word).
All that said, the proposed function to estimate time based on angle seems very likely to produce better routes than the current situation.
tobydickenson
sonora
vshcherb
cgogolin
gjedeer
aceman444
I have previously raised this on #5332, but that issue got closed after a map change fixed that specific mis-routing. I am raising this as a general routing issue. In many places I have seen osmand planning routes which include acute angles.
I first spotted this when expecting Osmand to take this route: https://www.openstreetmap.org/directions?engine=graphhopper_car&route=50.90460%2C-1.33822%3B50.90543%2C-1.33930#map=19/50.90518/-1.33908 but instead of taking the right turn onto the service road, Osmand preferred to carry on for 50m, make a u-turn (160° turn) onto the other carriageway, then take a left turn onto the service road. I guess Osmand thought 100m of highway=secondary was better than 10m of service road. In other circumstances skipping a tiny service road segment would be a good choice, but in this case the 160° turn makes it silly.
Arguably this case was a map bug, and I fixed it (ages ago) by adding a turn restriction. But I have seen the same thing in other cases where Osmand picked an acute turn which was technically legitimate. Legitimate, but in practice slower than alternatives. Osmand simply doesnt realise that sharp turns are slow.
4896 is the background to my investigation into this issue. Osmand //does// have some logic checking turn angle, but the code is misleading, the angle thresholds seem wrong, and the penalties are counterproductive for (I understand) compatibility reasons.
Since January I have been experimenting with a modified routing.xml which seems to have fixed this for me. I have set:
rightTurn="0". #4896 tells us that this field is nothing to do with right turns, but rather a penalty that gets applied for turns which are between 90° and 120° (in either direction). Many roads join at nominal right angles, so it seems irrational to have a penalty conditionally applied depending whether the angle is slightly above, or slightly below 90°.leftTurn="600". This is a penalty applied to turns above 120° (in either direction).That's all with standard code and modified routing.xml. My next step (which I havent yet had free time for) would be modify the code with a softer turn penalty profile. Something like:
(My apologies for the duplication from other tickets)