News for hackers. Stuff that matters.
Re:How UPS trucks saved millions of dollars by eliminating l... by amelius on Friday February 10, 2017 @09:50AM (#13615707)
Does typical navigation software assign the same cost to a left turn as a right turn?
Re:How UPS trucks saved millions of dollars by eliminating l... by lorenzhs on Friday February 10, 2017 @11:43AM (#13616712)
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

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.

Re:How UPS trucks saved millions of dollars by eliminating l... by toomanybeersies on Friday February 10, 2017 @10:46AM (#13616126)
I believe that Telogis does, from what one of the engineers was saying to me.

Most software will weight on rules like how long it will take to turn left rather than right at an intersection, and other average case rules at decision points.

Re:How UPS trucks saved millions of dollars by eliminating l... by snrplfth on Friday February 10, 2017 @10:04AM (#13615813)
If your navigation software doesn't permit weighting different turns, it's not really worth using for a business/organization of any substantial size. Usually there's also cost assignment/weighting for things like traffic time, stoplights-vs-all-way-stops, effective speed limits, time-vs-distance balancing, and all the zonal assignments that come up when breaking up a bunch of stops into different vehicles' routes for the day.
Re:How UPS trucks saved millions of dollars by eliminating l... by pc86 on Friday February 10, 2017 @10:06AM (#13615833)
They're asking about typical nav software, not large business logistics software.
Re:How UPS trucks saved millions of dollars by eliminating l... by snrplfth on Friday February 10, 2017 @10:12AM (#13615883)
Okay, I assumed the implication was software "typical" for commercial/delivery/collection vehicle routing. Even a business with a dozen vehicles would generally have this sort of software.

Google Maps does not, the last time I checked, preferentially weight left turns beyond expected stoplight delay time. However, Waze does, apparently. (But this is just a comparative observation, the algorithms are not public.)