Turn costs cause race condition in Routing algorithm

[cmhodgson]

In cases where there is more than one path to an intersection which are of similar cost, the best path to use depends on which direction you are travelling out of the intersection and what the costs of the turns are. This isn't correctly accounted for presently, it is assumed that the first segment to arrive at an intersection must have been the shortest path, not accounting for the turn costs out of the intersection. The effect of this would be very subtle as the differences in turn costs are quite small, however it may be amplified in divided cases where the intersection has a short internal segment, because the router can easily arrive at the longer segment first, and one path may involve turn costs onto or off of the internal segment. The resulting effect of taking a route with an excessive travel time can also be amplified in situations where the likely routing paths travel through multiple intersections with this property, eg. travelling diagonally across a grid of streets.

The routing algorithm (Dijkstra-based) keeps a queue of the lowest-cost places it has traveled to so far, and in each step it travels one edge further out from the the lowest cost place it has reached. Previously it was tracking edges, that was updated to track which end of which edge, and traveling in which direction. This needs to be improved to also take into account the cost of turning onto the destination edge.

[gleeming]

Example 1: 48.44558,-123.36614 to 48.43872,-123.36460 takes Finlayson/Quadra/Hillside. Then change the 5th digit in the longitude of the destination coordinate (slight west shift) so it ends at 48.43874,-123.36461 and the route is completely different. Then change to request the shortest path and observe that the result reverts to the original route with a 3 second faster duration.

Example 2: 48.43836,-123.36683 to 48.44282,-123.37923 goes straight along Hillside/Gorge. Again a tiny change in the last coordinate to 48.44282,-123.37924 results in a complete reroute up Douglas, Burnside and Jutland, adding 6 seconds for such an small perturbation. Then switch to request the shortest path -- once again it reverts to the original route and yields a faster result than the "fastest" algorithm.

[cmhodgson]

The initial approach to solving this problem, of including the future turn cost and direction in the current cost, for each possible future turn, has proven to cause excessive slowness due to increasing the size of the Dijkstra queue. A simpler solution is to get rid of variable turn costs, and have only intersection costs. These costs can still take relative road class into consideration, but there cannot be different costs depending on the outgoing direction. This will require changes to the turn cost generation algorithm in the Routeable BC Maker.

[mraross]

Please proceed

[mraross]

Intersection crossing cost is better but not sufficient. We need to bite the bullet and solve turn costs. Please estimate for another approach.

[cmhodgson]

Note that #213 has removed turn costs and replaced them with crossing costs. This removes the race condition issue. Re-estimating and moving back to icebox for future handling of turn costs.