2 ms·
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,
by lorenzhs 10y ago
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.
See my other comment in this thread on the challenges associated with incorporating turn costs and restrictions in gerenal: https://news.ycombinator.com/item?id=13616676 https://news.ycombinator.com/item?id=13616676
- euyyn 10y ago> 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?
- lorenzhs 10y agoNah, 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.