News for hackers. Stuff that matters.
Re:How UPS trucks saved millions of dollars by eliminating l... by euyyn on Friday February 10, 2017 @03:31PM (#13618616)
> 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?

Re:How UPS trucks saved millions of dollars by eliminating l... by lorenzhs on Friday February 10, 2017 @04:15PM (#13618962)
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.