11 ms·

How UPS trucks saved millions of dollars by eliminating left turns

75 points by rootein 10y ago

Unbeliever69 10y 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!
- dx034 10y 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 10y 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.
    - euyyn 10y ago
      That's odd, as Google Maps optimizes on duration, not distance: It takes speed into account. Maybe it's not taking into account how fast can cars make each of the turns?
spraak 10y ago
This is why I love data science
amelius 10y ago
Does typical navigation software assign the same cost to a left turn as a right turn?
- snrplfth 10y 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.
  - pc86 10y ago
    They're asking about typical nav software, not large business logistics software.
    - snrplfth 10y ago
      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.)
- toomanybeersies 10y 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.
- lorenzhs 10y 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 https://news.ycombinator.com/item?id=13616676
briankwest 10y 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.
- dx034 10y 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 10y 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.
- pc86 10y ago
  It won't always be longer, it just wasn't a deal breaker if it was.
- gjem97 10y 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?
  - deleted 10y ago
    [deleted]
  - lorenzhs 10y 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 https://algo2.iti.kit.edu/download/turn_ch.pdf http://i11www.iti.uni-karlsruhe.de/extra/publications/dgpw-crp-11.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 :)
snrplfth 10y 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 10y 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.
- pc86 10y 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 10y 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.
    - lorenzhs 10y ago
      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 https://en.wikipedia.org/wiki/Turn_on_red [2] https://www.law.cornell.edu/uscode/text/42/6322 https://www.law.cornell.edu/uscode/text/42/6322
vermontdevil 10y ago
Hence the need for more roundabouts.
shakencrew 10y ago
A different article about this was discussed on Hacker News before: https://news.ycombinator.com/item?id=7538316 https://news.ycombinator.com/item?id=7538316. The cited article also references the Mythbusters video.
imcoconut 10y ago
now that's what I'm talking about. good for ups.
deleted 10y ago
[deleted]
Theodores 10y 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.
- lorenzhs 10y 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 10y 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.
    - lorenzhs 10y ago
      Well yeah it's clearly still NP-complete. But the TSP (or variant thereof) isn't related to the routing engine at all, as the routing engine only defines the edge weights. They're fairly orthogonal problems. Logistics software needs to solve both, but consumer satnav doesn't.
d--b 10y 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 10y 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 10y ago
Discussion from a few years ago: https://news.ycombinator.com/item?id=7538316 https://news.ycombinator.com/item?id=7538316
eggie5 10y 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 10y ago
  Right. It's a great story, but I've seen many a UPS truck take a left turn.

75 points by rootein 10y 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!

dx034 10y 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 10y 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.
  - euyyn 10y ago
    That's odd, as Google Maps optimizes on duration, not distance: It takes speed into account. Maybe it's not taking into account how fast can cars make each of the turns?

spraak 10y ago

This is why I love data science

amelius 10y ago

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

snrplfth 10y 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.
- pc86 10y ago
  They're asking about typical nav software, not large business logistics software.
  - snrplfth 10y ago
    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.)
toomanybeersies 10y 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.
lorenzhs 10y 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 https://news.ycombinator.com/item?id=13616676

briankwest 10y 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.

dx034 10y 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 10y 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.

pc86 10y ago
It won't always be longer, it just wasn't a deal breaker if it was.
gjem97 10y 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?
- deleted 10y ago
  [deleted]
- lorenzhs 10y 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 https://algo2.iti.kit.edu/download/turn_ch.pdf http://i11www.iti.uni-karlsruhe.de/extra/publications/dgpw-crp-11.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 :)

snrplfth 10y 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 10y 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.

pc86 10y 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 10y 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.
  - lorenzhs 10y ago
    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 https://en.wikipedia.org/wiki/Turn_on_red [2] https://www.law.cornell.edu/uscode/text/42/6322 https://www.law.cornell.edu/uscode/text/42/6322

vermontdevil 10y ago

Hence the need for more roundabouts.

shakencrew 10y ago

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

imcoconut 10y ago

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

deleted 10y ago

[deleted]

Theodores 10y 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.

lorenzhs 10y 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 10y 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.
  - lorenzhs 10y ago
    Well yeah it's clearly still NP-complete. But the TSP (or variant thereof) isn't related to the routing engine at all, as the routing engine only defines the edge weights. They're fairly orthogonal problems. Logistics software needs to solve both, but consumer satnav doesn't.

d--b 10y 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 10y 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 10y ago

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

eggie5 10y 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 10y ago
Right. It's a great story, but I've seen many a UPS truck take a left turn.