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.

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,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.