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.
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