BusinessWeek asks: Can UPS Save Christmas?

Nope. A strong holiday shopping season caused UPS to exceed their network capacity, making #UPSfail one of the top trending hashtags on Christmas day. UPS has tough job this time of year, and it’s all orchestrated from an office in Louisville, KY.

Consider this: A traveling salesman needs to make five stops in a city. What is the shortest path to hit all five points?

A UPS driver needs to make over 200 stops in a city, every day. What is the shortest path to hit all 200 points?

The computation time to solve the first problem might be less than a second. The second problem takes that amount of time, raised to the 20th power. Now scale the solution for the 132 million packages UPS must deliver in the week before Christmas. This is the task faced by the UPS dispatch planning system.

Look at the label on your next UPS package. This tells you exactly where the package sat in the brown truck on the drive to your home.

A UPS driver has 9 seconds to remove a package from the truck. She has another 30 seconds to walk to your doorstep and knock on the door. If there’s no response, you get an infonotice. UPS drivers adhere to this strict schedule to match their deliveries and breaks to the traveling salesman solution generated by the dispatch planner.

The drivers are under immense pressure. A 5-minute delay in a single driver’s day, added up over the course of the year, translates to a $105 million annual loss for UPS.

There’s a much simpler solution to all of this. With over 300 million passenger vehicles on the road and an average vehicle occupancy of 1.2 passengers, there already exists a self-assembled delivery network. What more, each driver has already optimized their own route.

This is tantamount to solving the traveling salesman problem with a distributed computing system versus a centralized machine. In effect, a solution is reached in constant time rather than exponential time. And as is the case with distributed systems, breakdowns are contained without resulting in an Epic Fail.

Crowdsourced delivery is becoming a reality on the west coast, thanks to Barnacle. Judging by the number of tweets claiming to renounce UPS and FedEx forever, it’s quite possible that next year, we won’t be asking if UPS can save Christmas. Christmas will be saved by the crowd.