Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How UPS trucks saved millions of dollars by eliminating left turns

gadgets.ndtv.com

Post reply on HN
Print view View original

51–60 of 101 posts

Re: How UPS trucks saved millions of dollars by eliminating left turns

#51

Post by lorenzhs »

gjem97 wrote: post #17
leereeves wrote: post #6

> eliminating left turns wherever possible after it found that drivers have to sit idly in the trucks while waiting to take the left turn to pass through traffic. So, it created an algorithm that eliminated left turns from drivers’ routes even if meant a longer journey. Sounds reasonable. > In 2005 ... the total distance covered by its 96,000 trucks was reduced by 747,000km. In 2011, ... the company had reduced dista…

I think "created an algorithm" is probably overselling it a bit. Clearly they already had a route planner, didn't they just modify it to add extra cost to a left turn?

Incorporating turn costs into route planning is actually not that easy! For one it increases the amount of data you need (street layout, type of intersection, etc) and a lookup to add the appropriate penalty. But more importantly, it doesn't play well with many speed-up techniques.

Two papers on the subject, applying turn costs to the two most popular speed-up techniques (I don't know if UPS uses either of these, though):

https://algo2.iti.kit.edu/download/turn_ch.pdf

http://i11www.iti.uni-karlsruhe.de/extra/publications/dgpw-c...

The first author of the first paper now works at Google, and the authors of the second paper used to work at Microsoft Research and now are at Apple and Amazon. Make of that what you will :)

Re: How UPS trucks saved millions of dollars by eliminating left turns

#52

Post by lorenzhs »

amelius wrote: post #4

Does typical navigation software assign the same cost to a left turn as a right turn?

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 left turns

#54

Post by lorenzhs »

Theodores wrote: post #38

This optimisation must exist at a basic level in all satnav software because journey time must be longer for the route with more left turns, as fed back into the system from previous journeys by other users. It would be an interesting experiment to see how different consumer grade satnav systems compare on this pure travelling salesman problem.

It's not TSP. In TSP, you have a graph and want to visit every node exactly once. Here you have a (road) graph and want to visit some set of nodes (the delivery addresses) at least once (it's okay to drive past a house where you dropped off a parcel earlier if that somehow makes the journey shorter).

Also, consumer satnav systems don't support this kind of query. You can't plug in a list of dozens of destinations and ask for the shortest path to get you to all of them, in any order.

Re: How UPS trucks saved millions of dollars by eliminating left turns

#55

Post by snrplfth »

frandroid wrote: post #48
snrplfth wrote: post #28

Earlier quoted context omitted.

It's not as commonly done because it's considerably more expensive to build triple platforms, and the bends required to make it work slow the train down and cause wear. It's good for high-capacity stations though.

What bends?

When trains run in tunnels, or even when on aboveground rights-of-way, the rails are generally spaced very close together. A 3-platform station therefore requires the tracks to turn away from each other to make room for the central platform.

They don't usually have to be that sharp, but they tend to be noticeably sharper than the turns in the route.

Re: How UPS trucks saved millions of dollars by eliminating left turns

#56

Post by [deleted] »

frandroid wrote: post #48
snrplfth wrote: post #28

Earlier quoted context omitted.

It's not as commonly done because it's considerably more expensive to build triple platforms, and the bends required to make it work slow the train down and cause wear. It's good for high-capacity stations though.

What bends?

[deleted]

Re: How UPS trucks saved millions of dollars by eliminating left turns

#57

Post by lnanek2 »

dx034 wrote: post #24
Unbeliever69 wrote: post #2

It's funny because occasionally my wife will tell me to take a certain route to a destination because that is what her traffic app told her was the fastest route. I'll disagree on the basis of this experiment; that the "fastest route" has too many left turns and that my route is better because it has fewer. Needless to say, she is never amused. Maybe after this news I'll be vindicated!

Wasn't Waze known to prefer routes that consisted of an incredible amount of left turns and small roads? Haven't checked if they changed the algorithm. Found that Google Maps is hard to beat on their preferred route usually.

At least in NJ, Google Maps typically does a terrible job. When I go from my home to Costco, I take one small road to the highway, take the highway, get off, and take one small road to Costco. It's very fast and easy. Makes a big L on the map, basically.

Google Maps ignores the highway and has me make twenty alternating left and right turns on tiny backroads. It's grueling, a lot of work, and you can't even go fast on them. All because Google Maps is trying to cut the diagonal from one end of the L to the other for a shorter distance. In terms of trip duration, it fails horribly, though.

Re: How UPS trucks saved millions of dollars by eliminating left turns

#58

Post by lorenzhs »

JakeTheAndroid wrote: post #43
pc86 wrote: post #9

Earlier quoted context omitted.

> Indeed, the turn-on-red rule in the US seems to work inverse to how I've seen it elsewhere – i.e. it's always allowed unless there's specific signage saying it isn't. Driving laws vary widely by state. You cannot say "$x is [il]legal in the US" because it's likely there's at least one state where the inverse is true. That being said, my state does allow turning on red unless it's explicitly prohibited, including le…

Having been across the US, I would say that the right-on-red rule is so consistent that you can say it's legal in the US. It's just a rule with an exception.

According to Wikipedia [1], "as of 1992, right turn on red is governed federally by 42 U.S.C. § 6322(c)", which reads [2]:

> Each proposed State energy conservation plan to be eligible > for Federal assistance under this part shall include [...] > a traffic law or regulation which, to the maximum extent > practicable consistent with safety, permits the operator of a > motor vehicle to turn such vehicle right at a red stop light > after stopping and to turn such vehicle left from a one-way > street onto a one-way street at a red light after stopping

I'm not sure how exactly the NYC exception works.

[1] https://en.wikipedia.org/wiki/Turn_on_red

[2] https://www.law.cornell.edu/uscode/text/42/6322

Re: How UPS trucks saved millions of dollars by eliminating left turns

#59

Post by gumby »

mstade wrote: post #8

> In the US, and other countries where you drive on the right side of the road, right turns are free, but for a left turn you need to wait for a green light. I don't know of any other country than the US where turning right on red is allowed, unless there's specific signage or additional traffic lights to allow it. Indeed, the turn-on-red rule in the US seems to work inverse to how I've seen it elsewhere – i.e. it's…

> I don't know of any other country than the US where turning right on red is allowed

The DDR (East Germany) had this law and IIRC it was one of the two things they tried to preserve in the unification agreement (the other was abortion rights). Neither survived.

Re: How UPS trucks saved millions of dollars by eliminating left turns

#60

Post by gumby »

lorenzhs wrote: post #58
JakeTheAndroid wrote: post #43

Earlier quoted context omitted.

Having been across the US, I would say that the right-on-red rule is so consistent that you can say it's legal in the US. It's just a rule with an exception.

According to Wikipedia [1], "as of 1992, right turn on red is governed federally by 42 U.S.C. § 6322(c)", which reads [2]: > Each proposed State energy conservation plan to be eligible > for Federal assistance under this part shall include [...] > a traffic law or regulation which, to the maximum extent > practicable consistent with safety, permits the operator of a > motor vehicle to turn such vehicle right at a red…

New York got to be the exception (!?)
Post reply on HN