C&B Notes

A Difference Between an Answer and a Solution

There is an understandable tendency to try to boil logistics down into math problems that can be “solved” via complicated algorithms.  The engineers tasked with building these systems at companies like UPS and Schneider, however, continue to wrestle with the sheer complexity of the problems while also trying to address the outside elements (unexpected traffic, emotion, etc.) that are difficult or impossible to quantify.

The problem that Santilli posed to his daughter’s class is known as a traveling salesman problem. Algorithms solving this problem are among the most important and most commonly implemented in the transportation industry.  Generally speaking, the traveling salesman problem asks: Given a list of stops, what is the most time-efficient way for a salesman to make all those stops?  In 1962, for example, a Procter and Gamble advertisement tasked readers with such a challenge: To help “Toody and Muldoon,” co-stars of the Emmy-award-winning television show Car 54, Where Are You?, devise a 33-city trip across the continental United States.  “You should plan a route for them from location to location,” went the instructions, “which will result in the shortest total mileage from Chicago, Illinois, back to Chicago, Illinois.”  A mathematician claimed the prize, and a regal $10,000.  But the contest organizers could only verify that his solution was the shortest of those submitted, and not that it was the shortest possible route.  That’s because solving a 33-city problem by calculating every route individually would require 28 trillion years — on the Department of Energy’s 129,000-core supercomputer Roadrunner (which is among the world’s fastest clusters).  It’s for this reason that William J. Cook,  his book In Pursuit of the Traveling Salesman, calls the traveling salesman problem “the focal point of a larger debate on the nature of complexity and possible limits to human knowledge.” Its defining characteristic is how quickly the complexity scales.  A six-city tour has only 720 possible paths, while a 20-city tour has — by Cook’s quick calculations on his Mac — more than 100 quadrillion possible paths.

There are answers to some traveling salesman problems.  Cook himself has produced an iPhone app that will crack 100 cities, using relaxed linear programming and other algorithmic techniques.  And every few years or so, teams armed with sophisticated hardware and programming approaches set the bar higher.  In 2006, for example, an optimal tour was produced by a team led by Cook for a 85,900-city tour.  It did not, of course, given the computing constraints mentioned above, involve checking each route individually.  “There is no hope to actually list all the road trips between New York and Los Angeles,” he says.  Instead, almost all of the computation went into proving that there is no tour shorter than the one his team found.  In essence, there is an answer, but there is not a solution.  “By solution,” writes Cook, “we mean an algorithm, that is a step-by-step recipe for producing an optimal tour for any example we may now throw at it.”

*****

Powell’s biggest revelation in considering the role of humans in algorithms, though, was that humans can do it better.  “I would go down to Yellow, we were trying to solve these big deterministic problems.  We weren’t even close. I would sit and look at the dispatch center and think, how are they doing it?” That’s when he noticed: They are not trying to solve the whole week’s schedule at once.  They’re doing it in pieces. “We humans have funny ways of solving problems that no one’s been able to articulate,” he says.  Operations research people just punt and call it a “heuristic approach.”  This innate human ability was at work in Santilli’s daughter’s class, too.  The fifth graders got it about right.  As James MacGregor and Thomas Ormerod note, “the task of the traveling salesman problem may happen to parallel what it is natural for the perceptual system to do in any case when presented with an array of dots.”  Curiously, using this heuristic approach, they note, subjects in experiments were “exceptionally good at finding the optimum tours.”  In other experiments, when subjects were shown images of optimal tours, they were thought to be more aesthetically pleasing than sub-optimal tours.

Of course, even the human balks at understanding the behavior of other humans.  Powell showed me a sample diagram he’ll sometimes give to a roomful of trucking executives.  “I’ve got a load that has to be picked up.  I’ve got a driver 60 miles away.  All I have to do is dispatch him and it’s done.  I’ve got another driver who, once he unloads, will be about 30 miles away — should be in around midafternoon.”  Do you take the sure thing, even if it consumes more miles?  Or do you take the risk on the shorter trip, which might get in later?  When he asks for a show of hands which choice is better, the response is typically mixed.  “Driver B saves me miles.  But he hasn’t arrived yet, and what if he doesn’t?” he says, his voice dropping to a conspiratorial whisper.  “Different people will answer it differently.  They’ll say, ‘I know that driver, he’ll make it.’  Welcome to real-world decision making.”

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