The travelling salesman problem

Algorithms and the happiness of drivers. [Link]

Transport optimization, then, is hard, and understanding how to implement it can be harder still. “One of the hardest things to teach a math analytics group,” Santilli tells me, “is the difference between a feasible solution and an implementable solution. Feasible just means it meets all the math constraints. But implementable is something the human can carry out.”

But optimization has succeeded in coming a very long way. Modeling has become much more sophisticated, a development that Powell outlines in his life’s work, a book called Approximate Dynamic Programming: Solving the Curses of Dimensionality. “You went to the math literature, and it was all toy problems. It was literally about 20 years before I could go to a whiteboard and say, you know what, I can actually write down the problem.” Mapping has improved dramatically. A few decades ago, the mapping service UPS bought literally had people calling businesses to ask them if they actually were where the data UPS had suggested they were. Early GPS maps were also flawed. “When we got some bad results early on,” says Ranga Nuggehalli, UPS’s principal scientist, “we didn’t know whether it was because the algorithm was so bad, or our data was so bad.”  It was the latter. 

The data acquisition needed for tracking has since been developed. UPS’s “Delivery Information Acquisition Device,” or DIAD, the brown handheld computer upon which you have no doubt signed your name, creates a data architecture that underpins their optimization strategy.

And the end result has been one of slow but steady improvement. Powell and Santilli point to their own success stories. Yellow Freight used to have some 700 “end of lines,” Powell says, which are sorting terminals where cargo is transferred to its end customers. Powell developed a model that delivered a counterintuitive message: Trucks were traveling farther to get to the customer with so many terminals. Today, he says, Yellow Freight has 400 end of lines. “That was the right number,” he says. As for UPS, Santilli notes that a driver in Gettysburg, Pa. is now driving nearly 25 miles less per day, from an original route of more than 150 miles down to 126 miles—with the same number of stops.

We are getting smarter at moving things around. But the less obvious story is that we are getting a grasp on how to model the human element in transportation. Just as we are getting to know algorithms, algorithms are getting to know us.