> Incorporating turn costs into route planning is actually not that easy! [I]t doesn't play well with many speed-up techniques.
+
> Since you need turn restrictions if you want to compute routes that users can actually follow, adding different costs for different kinds of turns (left, right, U-turn) is easy.
Does this mean all those speed-up techniques don't produce routes that are actually allowed? What's the point of developing them?
Nah, it's just that it took work to integrate turn restrictions, and that that results in a bit of a slowdown.
It's easier to do research on a more limited version of the problem (shortest path in a road graph with a suitably chosen edge weight function) and then generalise than start out with the most general formulation. The results are wild: these techniques are millions of times faster than Dijkstra's algorithms and provably produce the exact same result. It's what makes Google Maps possible.
+
> Since you need turn restrictions if you want to compute routes that users can actually follow, adding different costs for different kinds of turns (left, right, U-turn) is easy.
Does this mean all those speed-up techniques don't produce routes that are actually allowed? What's the point of developing them?