Jump to content

The Math Behind UPS’ New Tool to Deliver Packages Faster


al mcguire

Recommended Posts

The Astronomical Math Behind UPS’ New Tool to Deliver Packages Faster

In a sense, all business boils down to math. But some companies have tougher equations to solve than others.

At UPS, the average driver makes about 120 deliveries per day, says Jack Levis, the shipping giant’s director of process management. To figure out how many different possible routes that driver could travel, just start multiplying: 120 * 119 * 118 * . . . * 3 * 2 * 1. The end result, Levis likes to say, far exceeds the age of the Earth in nanoseconds.

If that number sounds big, imagine having to make those calculations for 55,000 drivers every day. Until recently, UPS used a software tool that gave drivers a general route to follow but allowed wide latitude for human judgement along the way. Over the next five years, however, the company will roll out widely a more exacting algorithm designed to steer drivers away from well-worn paths toward often counterintuitive routes calculated to make delivery faster.

Called ORION, or On-Road Integrated Optimization and Navigation, UPS’ data-drenched route optimization tool aims to deliver the best answer yet to the traveling salesman problem, the classic computational conundrum that shows just how hard it is to find the shortest distance among a series of points on a map. The size of the numbers involved means simple arithmetic is out. Instead, ORION depends on heuristics, the field of math and computer science devoted to finding answers that are good enough, and that get better based on past experience.

Of course, finding the shortest distance is only one of many variables in play for UPS. Promised delivery times, different types of customers and the types of packages being delivered and picked up are just a few of the additional factors ORION must take into consideration. And Levis is quick to emphasize that UPS doesn’t discount the value of driver wisdom accumulated during years on a route. The best system, he says, is one that relies on both human and algorithmic intelligence, not just one or the other.

Still, computers simply have far more raw calculation power than humans. That capacity combined with the massive amount of data needed to feed that brainpower are what Levis hopes add up to superhuman intelligence: “How do we come up with ways that are better than what humans would have come up with on their own?”

Here’s a few more numbers that play into the math behind UPS’ quest for efficiency:

$30 million—The cost to UPS per year if each driver drives just one more mile each day than necessary. By that same logic, the company saves $30 million if each driver finds a way to drive one mile less.

15 trillion trillion—The number of possible routes a driver with just 25 packages to deliver can choose from. As illustrated by the classic traveling salesman problem, the mathematical phenomenon that makes figuring out the best delivery routes so difficult is called a combinatorial explosion.

55,000—The number of “package cars” (the brown trucks) in UPS’ U.S. fleet. If the figures involved in determining the most efficient route for one driver are astronomical in scale, imagine how those numbers look for the entire fleet.

85 million—The number of miles Levis says UPS’ analytics tools are saving UPS drivers per year.

16 million—The number of deliveries UPS makes daily.

30—The maximum number of inches UPS specifies a driver should have to move to select thethe next package. This is accomplished through a meticulous system for loading packages into the truck in the order in which they’ll be delivered.

200 million—The number of addresses mapped by UPS drivers on the ground.

74—The number of pages in the manual for UPS drivers detailing the best practices for maximizing delivery efficiency.

100 million—The reduction in the number of minutes UPS trucks spend idling thanks in part, the company says, to onboard sensors that helped figure out when in the delivery process to turn the truck on and off.

200—The number of data points monitored on each delivery truck to anticipate maintenance issues and determine the most efficient ways to operate the vehicles.

 

http://www.wired.com/business/2013/06/ups-astronomical-math/

 

 

Link to comment
Share on other sites

This is one of those BS number games that have only one foot in reality. For instance this stat: "15 trillion trillion—The number of possible routes a driver with just 25 packages to deliver can choose from".  1 trillion is an astronomically huge number, 15 trillion is unfathomable.  I guess they get this number when the delivery is from Van Nuys, CA to Oxnard, CA and they suggest one of the routes could be going around the world and taking every side road.  

 

These stats that companies spew out are corporate masterbation.  "Look how hard it is and yet we make it work" blah, blah.  Yeah well, like I tell the teamsters when they start spouting about how movies can't be made with out them - "My grandma's got a drivers licence too."

Link to comment
Share on other sites

We all had to graduate in physics before we could take the entrance exam to the film school. Vinod has managed to retain most of the stuff, I, being older  :) has let much of what I've learnt evaporate. 

 

Suresh

 

Bombay, India

Link to comment
Share on other sites

For instance this stat: "15 trillion trillion—The number of possible routes a driver with just 25 packages to deliver can choose from". I guess they get this number when the delivery is from Van Nuys, CA to Oxnard, CA and they suggest one of the routes could be going around the world and taking every side road.

 

Actually, I believe this number only takes into account delivery order and doesn't even consider the various streets one could take. So, say you have 3 packages to deliver to the following 3 locations:

 

1) Van Nuys, 2) Oxnard, and 3) Burbank

 

You could go

a ) Burbank, Oxnard, Van Nuys, or

b ) Oxnard, Burbank, Van Nuys, or

c ) Oxnard, Van Nuys, Burbank, or

d ) ... you get the idea

 

With 3 pacakges there are 6 possible routes. Now obviously some of these make way more sense than others, like © would probably be a much better bet than (a). But the problem is that the more delivery locations you add, the number of combinations grows exponentially, so it quickly gets out of control.

 

So with 25 delivery locations you end up with 15 trillion trillion combinations of delivery order. And it becomes impossible to compute the best route, even if all you care about is minimizing the total distance traveled and the only thing you can vary is the delivery order.

 

If you start taking into account different streets you can take between each location, traffic, road closures, time of day, etc. then things get even more complicated. And if you want to optimize for several different variables: delivery time, distance traveled, number of drivers, highway vs. surface street miles your head starts to hurt (and your computer starts to overheat).

 

This is why UPS uses imperfect heuristics and human input rather than trying to calculate the best route directly.

 

One of the biggest unsolved problems in theoretical computing is whether or not the traveling salesman problem (and other similar problems) can be solved efficiently. Basically is there a way to solve the problem with polynomial growth as the number of locations increases rather than the exponential explosion described in the article. Many people believe the answer is no, but no one has been able to prove it yet.

 

But what makes this interesting is that here is a case where the theory actually has significant real-world implications. If there were an efficient way to compute an answer to the traveling salesman problem, it would save UPS a bundle of money and a bundle of time. Which for consumers would likely mean lower prices and faster delivery times.

 

Anyway, something to think about the next time a package is delayed or the UPS guy doesn't show up until well into the evening ...

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...