How UPS trucks saved millions of dollars by eliminating left turns

http://gadgets.ndtv.com/transportation/features/how-ups-trucks-saved-million-of-dollars-by-eliminating-left-turns-1657808

by rootein • 9 years ago

75 92 9 years ago

gadgets.ndtv.com

Unbeliever69• 9 years ago

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!

dx0342• 9 years ago

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.

lnanek2• 9 years ago

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.

spraak• 9 years ago

This is why I love data science

amelius• 9 years ago

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

snrplfth9• 9 years ago

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.

pc863• 9 years ago

They're asking about typical nav software, not large business logistics software.

toomanybeersies• 9 years ago

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.

lorenzhs8• 9 years 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

euyyn3• 9 years 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?

briankwest• 9 years ago

Yes they may save money doing this, but when you do that follow your driver for your delivery thing they just came out with, It looks like your driver is on crack the travel patterns make no sense. No order. They are all over the place, similar to how Delta does connecting flights.

dx0342• 9 years ago

Worth mentioning that many drivers will be self-employed and have no such software. UPS seems to give all drivers a software with a route to follow, many others won't bother (as they pay the driver by delivery).

leereeves• 9 years ago

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 distance travelled by trucks by 20.4 million miles. A recent report by The Independent says that the total reduction in distance travelled by UPS trucks now stands at 45.8 million miles.

But how does eliminating left turns even it means a longer journey reduce the total distance travelled?

Edit:

The Independent article referenced here explains:

The efficiency of planning routes with its navigation software this way has even helped the firm cut the number of trucks it uses by 1,100, bringing down the company’s total distance travelled by 28.5m miles – despite the longer routes.

pc863• 9 years ago

It won't always be longer, it just wasn't a deal breaker if it was.

gjem97• 9 years ago

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?

lorenzhs8• 9 years ago

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 :)

snrplfth9• 9 years ago

It also tends to reduce distance travelled because left turns are often done to get onto faster roads - if you right-turn it all the way, you're often on slower roads, so you're not going as fast, but you're saving actual travel distance.

snrplfth9• 9 years ago

This is an impressive result, but not exactly a UPS exclusive. Pretty much any vehicle routing software worth using has offside-turn-minimization options, usually as one of several 'weighting factors'. For example, almost every garbage collection service of any size minimizes its offside turns.

mstade• 9 years ago

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 always allowed unless there's specific signage saying it isn't.

I was just in the US, and I love their turn-on-red rules, and I kept thinking that sometimes it's got to be smarter to turn right than go straight ahead, when there's a red light, even if it may be a longer drive. Glad to see someone took the time to figure this out.

pc863• 9 years ago

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 left turns if you are on a one-way street turning onto a one-way street.

I kept thinking that sometimes it's got to be smarter to turn right than go straight ahead, when there's a red light, even if it may be a longer drive.

The city I live in actually times the light cycles to prevent this, you will end up exactly where you would have been had you not turned, or behind.

JakeTheAndroid• 9 years ago

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.

Naga• 9 years ago

It is legal to turn right on a red light in Canada, except the Isle of Montreal. It actually used to be illegal in all of Quebec until 2003.

snrplfth9• 9 years ago

And in Quebec, you still see people turning right on red lights while looking solely to the right, instead of looking for oncoming traffic from the left.

digler999• 9 years ago

in NYC right turn on red is illegal, and it makes sense due to the number of pedestrians.

helipad• 9 years ago

My brother came to Michigan to visit from the UK. After a few days he said:

"So, I can go on a red light for a right turn, but sometimes I have to wait at a green light for a left turn?"

It was then I realised how peculiar the signals in the US can be.

bisby• 9 years ago

If you have to cross lanes of traffic, you have to wait for a light. If you are merely "changing lanes" you just have to wait for right of way.

(in my state at least) you're allowed to turn left from a one way to a one way on red, because you're not crossing any other lanes.

So do the math... how many lanes are involved. If it's just "current lane" and "target lane", you can go when the coast is clear. If there are ANY other lanes involved, wait for a light.

camiller• 9 years ago

Flip side, having driven in England 20+ years ago. In England, when stopped at a red they politely blink a yellow light when your stop light is about to turn green. In the US not only do we not do that, but many localities put extended shields around the lights, polarized lenses, etc. To prevent you from knowing when your light is about to turn by observing the lights for the perpendicular street.

In other words...

England provides more information to the driver expecting the driver to use that information to make good driving decisions.

The US hides information from drivers in an attempt to control their behavior because they don't trust the driver to make good driving decisions.

and now I'm once again angry about it.....

dorfsmay2• 9 years ago

Turning right on red is one of those idea that once you've been exposed to it you wonder why isn't everybody adopting it...

A similar idea is the train system in Munich where they built their platforms such that they can open doors on both sides, making one side of the train the exit, and the other side the entrance. Ever since I saw that, every single time I wait for people getting off a crowded train, I wonder "Why?".

alextheparrot• 9 years ago

There's an elevator in one of the London tube stations like this (Everyone uses the elevator, like 150 stairs). Just makes so much sense, moves so many more people that way.

snrplfth9• 9 years ago

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.

jventura2• 9 years ago

Turning right on red is one of those idea that once you've been exposed to it you wonder why isn't everybody adopting it...

Because someone who comes from your left may go forward, or someone who comes from your front mau turn left?

Where I live, we do not assume that we can turn right on red lights. Where and when that's possible, we have a blinking yellow light (basically meaning proceed with caution)..

jweir• 9 years ago

NYC has no right on red. After getting used to I loved it. Now I live in another city with right on red and a fair amount of bike and pedestrian traffic.

Turning right on red means looking out for cars, people, bikes and having the pressure of a car behind you - perhaps honking because it wants you to go.

Analemma_• 9 years ago

Turning right on red is one of those idea that once you've been exposed to it you wonder why isn't everybody adopting it...

I believe Jeremy Clarkson once called it, "America's only useful contribution to Western civilization" :)

capnrefsmmat• 9 years ago

Turning right on red is one of those idea that once you've been exposed to it you wonder why isn't everybody adopting it...

It was first introduced in the 70s in the US in response to high oil prices, and only after road safety tests apparently demonstrated its safety. But since then there's been a fair amount of research indicating it increases accidents and pedestrian fatalities, amounting to somewhere under 100 deaths per year. The original studies were not large enough to detect the effect.

https://www.statisticsdonewrong.com/power.html#the-wrong-tur...

theonething• 9 years ago

This is OT but do others have this experience?

You're a pedestrian at an intersection and patiently waiting for the crosswalk signal to flash walk because you want to be safe and not jaywalk. As soon as it flashes walk, a "right turner" comes zooming in and proceeds to take their right. Either they abruptly stop when they finally notice me or they don't and just roll on through and I have to jump back on the sidewalk to avoid them. I try to intentionally wait in a position that is very visible to the right turners and it still happens.

I don't feel safe legally crossing the street. It sucks.

jogjayr2• 9 years ago

Ever since I saw that, every single time I wait for people getting off a crowded train, I wonder "Why?".

Cost reasons. Wherever you adopt this, you need two platforms to serve a train instead of one. Not saying it doesn't make sense to do, just that someone probably sat down and did a cost/benefit calculation.

hobarrera• 9 years ago

I guess the train thing isn't done everywhere because it basically requires that you rebuild every single train station for it to work (plus, you have to re-do all the railing to have space for an additional platform in between).

I do agree that new stations should do this.

fosco• 9 years ago

Keep in mind everywhere in NYC unless noted does not allow right on red. however on Long Island and in Upstate New York it is typically allowed unless noted. laws not only vary by state but also by locality [pardon if this is not the correct usage of the term]

f_allwein• 9 years ago

It's legal to turn right at a red light in parts of Germany (if there s a sign saying so at the traffic light). One of the few things that were adopted from East Germany after the reunification. https://de.wikipedia.org/wiki/Grünpfeil

poulsbohemian• 9 years ago

It gets even better -- you can also make an "Oregon left" - in Oregon it is legal to turn left on red if you are turning onto a one way street.

http://www.oregonlive.com/commuting/index.ssf/2015/10/turn_l...

TruthSHIFT• 9 years ago

Georgia has this too. Who doesn't have this?

stevedt• 9 years ago

In California you can turn left on red from a one-way to a one-way street.

jusuchin• 9 years ago

In Milwaukee there are a few spots you can turn left on red technically "after stopping". The locations I know are freeway off-ramps onto one way streets, and simple left turns onto one way streets.

gumby2• 9 years ago

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.

arnarbi• 9 years ago

It's not just about turning on red. Even where that's not allowed, when the light is green the right turning traffic is less impeded and more cars pass through in a cycle. Those turning left have to wait longer for gaps in the oncoming traffic, in general at least.

michalskop• 9 years ago

It is common in Germany," too.

BrailleHunting2• 9 years ago

ToR was not allowed in all states until the late 70's, especially back East. It's not like pedestrians have enough dangers to worry about.

Popular expedience != sensible policies.

Curiously also, only California allows motorcycle lane-splitting.

vermontdevil• 9 years ago

Hence the need for more roundabouts.

shakencrew• 9 years ago

A different article about this was discussed on Hacker News before: https://news.ycombinator.com/item?id=7538316. The cited article also references the Mythbusters video.

imcoconut• 9 years ago

now that's what I'm talking about. good for ups.

Theodores• 9 years ago

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.

lorenzhs8• 9 years ago

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.

DerekL• 9 years ago

It reduces to a special case called the metric TSP. If going through node C is shorter than going from A to B directly, then just replace the A-to-B distance with the length of A-to-C-to-B. It's just as hard to solve as regular TSP, but easier to approximate.

d--b• 9 years ago

In 2005, a year after it announced that it will minimise left turns, the company said that the total distance covered by its 96,000 trucks was reduced by 747,000km, and 190,000 litres of fuel had been saved.

Er... I understand that you may reduce your fuel consumption by not waiting at red lights, but that the total distance driven has been reduced is clearly wrong!

Guys, you have a bug in your spreadsheet!

deelowe• 9 years ago

Maybe they also implemented a better navigation algorithm as part of this? The media likes to reduce everything down to soundbites, but IIRC, this is a rather large effort within UPS to improve routes in general. The left hand turn optimization was just one of the outcomes of this.

sctb• 9 years ago

Discussion from a few years ago: https://news.ycombinator.com/item?id=7538316

eggie5• 9 years ago

i talked to my friend, a UPS driver, about this last year when this same story surfaced on HN. He said it's not really true and that they turn left all the time -- but he was aware of some training about it.

tiffani• 9 years ago

Right. It's a great story, but I've seen many a UPS truck take a left turn.

How UPS trucks saved millions of dollars by eliminating left turns

Related Stories