Friday, June 14, 2013

The Traveling Salesman Problem Gets Real

(pic via Wikipedia)

Most folks are familiar with the Traveling Salesman Problem, one of the most famous dilemmas in all of math -- finding the shortest possible route between a given set of points (particularly ubiquitous in discussions of P vs. NP).
One real life example of TSP is route-scheduling for UPS delivery drivers who, every single workday, make on average, 120 deliveries. How most efficiently to drive that delivery route? There are a lot of consequences.

Apparently UPS has been field-testing a system, designated ORION ("On-Road Integrated Optimization and Navigation") which is their best algorithm for approximating a solution to TSP. So far they estimate it has saved them 35 million driving miles. Read more about it in the articles below (although they don't really give much information about the actual math behind ORION).

A quick couple of lines from the second piece:
“ 'Advanced analytics should be one of the top priorities for CIOs,' says Levis [UPS Director], who can talk of math in near-koans: 'Beyond knowledge is wisdom, and beyond that is clairvoyance.' Math simply can solve problems that humans can’t."

1 comment:

18c877d0-ef0d-11e2-80ce-000bcdca4d7a said...

I talk to our UPS delivery driver every week, which is where I first learned about the ORION program. He reports that so far every driver that uses the program logs many more miles and works hours of overtime to get everything delivered. The drivers that do not use the program are still demonstrably much more efficient. He also mentioned that to save face they changed how their office delivers to certain areas in order to show less miles logged since the implementation of the program. I think we can safely say this math problem has not been solved in a practical way by anyone at UPS