When Bob Santilli, a senior project manager at UPS, was invited in 2009 to his daughter’s fifth grade class on Career Day, he struggled with how to describe exactly what he did for a living. Eventually, he decided he would show the class a travel optimization problem of the kind he worked on, and impress them with how fun and complex it was. The challenge was to choose the most efficient route among six different stops, in a typical suburban-errands itinerary. The class devised their respective routes, then began picking them over. But one girl thought past the question of efficiency. “She says, my mom would never go to the store and buy perishable things—she didn’t use the word perishable, I did—and leave it in the car the whole day at work,” Santilli tells me.
Her comment reflects a basic truth about the math that runs underneath the surface of nearly every modern transportation system, from bike-share rebalancing to airline crew scheduling to grocery delivery services. Modeling a simplified version of a transportation problem presents one set of challenges (and they can be significant). But modeling the real world, with constraints like melting ice cream and idiosyncratic human behavior, is often where the real challenge lies. As mathematicians, operations research specialists, and corporate executives set out to mathematize and optimize the transportation networks that interconnect our modern world, they are re-discovering some of our most human quirks and capabilities. They are finding that their job is as much to discover the world, as it is to change it.
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, in 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.”
And that solution may never come. The traveling salesman problem is at the heart of an ongoing question—the question—in computer science: whether or not P equals NP. As summarized with blunt elegance by MIT’s news office, “roughly speaking, P is a set of relatively easy problems, NP is a set of incredibly hard problems, and if they’re equal, then a large number of computer science problems that seem to be incredibly hard are actually relatively easy.” The Clay Mathematics Institute offers a $1 million reward to a meta-problem hovering like a mothership over the Car 54 challenge and its ilk: proving that P does or does not equal NP.
By now it should be clear that we are not talking just about the routing needs of salesmen, for even the most trenchant of regional reps does not think about hitting 90,000 far-flung burghs on a call. But the Traveling Salesman Problem, and its intellectual cousins, are far from theoretical; indeed, they are at the invisible heart of our transportation networks. Every time you want to go somewhere, or you want something to get to you, the chances are someone is thinking at that very moment how to make that process more efficient. We are all of us traveling salesmen.
by Tom Vanderbilt, Nautilus | Read more:
Image: Peter and Maria Hoey
