right_division Green SCM Distribution
Bookmark us
SCDigest Logo

SCDigest Expert Insight: Supply Chain by Design

About the Author

Dr. Michael Watson, one of the industry’s foremost experts on supply chain network design and advanced analytics, is a columnist and subject matter expert (SME) for Supply Chain Digest.

Dr. Watson, of Northwestern University, was the lead author of the just released book Supply Chain Network Design, co-authored with Sara Lewis, Peter Cacioppi, and Jay Jayaraman, all of IBM. (See Supply Chain Network Design – the Book.)

Prior to his current role at Northwestern, Watson was a key manager in IBM's network optimization group. In addition to his roles at IBM and now at Northwestern, Watson is director of The Optimization and Analytics Group.

By Dr. Michael Watson

March 31, 2015

Routing Optimization is Hard: Lessons from UPS

The UPS Story Shows that Coming up with the Optimal Delivery Routes Isn't as Easy as it Would Seem

Dr. Watson Says:

...The article notes that it has taken UPS over ten years to develop their routing system at an estimated cost of $200-300M...
What Do You Say?

Click Here to Send Us Your Comments
Click Here to See Reader Feedback


Truck routing seems like it should be easy.  You can manually come up with a solution that loooks reasonable:  You send your truck out to an area with several stops, hit those stops, maybe hit some on the way out there and the way back, and you are done. 

But, how do you know you’ve found a good solution?

And, if some of the stops have tight time windows, how do you know that your route even works?

The answer is that you don’t know that you’ve found a good solution.   And, if you do have time windows, the solution you found may not even be feasible—that is, you may show up for a delivery at noon when you were supposed to be there at 9am. 

You might think that this would be an easy fix with some simple mathematical optimization—give the problem to an optimization engine and let it find the best answer.  Again, this sounds easy, but in practice, this is often more difficult that you would think.

The Wall Street Journal recently wrote an article on UPS’s quest to develop a better vehicle routing solution (the article may require subscription, but we’ll highlight the key points here).  This story highlights just how hard a routing problem can be.

Previous Columns by Dr. Watson

The Three Use Cases for Data Scientists

Learn Python, PuLP, Jupyter Notebooks, and Network Design

EOQ Model and the Hidden Costs of Fixed Costs

CSCMP Edge - Nike Quote: "It is All an Art Project Until you Get it on Someone's Feet"

Supply Chain by Design: Why Business Leaders should think of AI as an Umbrella Term


UPS has every incentive to find better routes.  It runs 55,000 routes per day and can save $50M for every 1 mile average reduction in the routes.

This first thing the article does is point out the mathematical difficulty of the problem.   It notes that for typical route with 120 stops, there are “6,689,502,913,449,135,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000, 000,000,000,000,000,000,000,000,000, 000,000,000,000,000,
000,000,000,000,000,000” different combinations!  And, this does not even include the interaction between trucks in the same area.  With this many options, it is very easy to bog down any optimization engine. 

But, despite the challenge, UPS has every incentive to find better routes.  It runs 55,000 routes per day and can save $50M per year for every 1 mile average reduction in the daily routes.

The article notes that it has taken UPS over ten years to develop their routing system at an estimated cost of $200-300M.  This should give you proof of the challenges in solving these types of problesm.   UPS is expected a pay-off of $300-$400M a year once the system is fully rolled out.

This example is not just from the fact that UPS has a particulary hard problem.  In a 2009 a paper by Gilbert Laporte titled "Fifty Years of Vehicle Routing" discusses the progress that has been made in this field.  He notes that the fifty years of research in the field has led to significant advances in different approaches and algorithms.  But, he cautions that the field still has a long way to go to solve larger (and more realistically sized) problems found in industry.


Final Thoughts

Routing problems are difficult.  Be wary of a solution that promises to find the optimal solution to any routing problem.  Instead, our experience has shown us that you may need to tailor a solution to your particular problem.  And, you should be ready to use solutions that find better, but maybe not the optimal solution.

Let me know your thoughts at the Feedback section below.

Recent Feedback

Obviously finding an optimized route is critical for a company like UPS who's business is based entirely on shipping. Right off the bat you can see several problems in finding an optimized route such as traffic, accidents, unexpected weather, road closings, and etc. I think the advantage that companies like UPS and Fedex have is that they have years of data which they can use to come to an optimal solution.  

Hussain Parbtani
University of Texas at Austin
Apr, 14 2015