The first time someone mentioned the Traveling Salesman Problem to me, I figured it had something to do with those ribald jokes I used to hear when I was young. But once it was explained to me, I realized we were instead talking about something that is at the core of logistics efficiency.
In a nutshell, the problem is this: A traveling salesman has to visit a defined number of cities. You know the costs between any two city pairs. (The cost can be measured in time or money.) Find the cheapest or most efficient way for the salesman to visit all the cities and return home.
This poser is nothing new. According to a Georgia Tech Web site dedicated to the problem (www.tsp.gatech.edu), the problem was first explored in the 1800s by mathematicians in Ireland and England, and then taken up again in the 1930s by mathematicians at Harvard and Princeton. The work continues in universities and research labs today.
Just as it's not new, neither is it simple. The problem's complexity is amply illustrated by an example cited in a short paper by Karla Hoffman of George Mason University and Manfred Padberg of New York University. Hoffman and Padberg modeled all the possible ways Odysseus could visit all 16 cities mentioned in the Odyssey exactly once and found there were no fewer than 653 billion distinct routes.
Fortunately, the algorithms used to solve actual, as opposed to theoretical, problems don't have to examine every possible route; they just have to find the best one. And researchers are getting better at it all the time. Last year, a research team found the optimal route for a salesman who wanted to visit all 24,978 cities in Sweden.
Though that might seem to be an exercise for computer nerds with time on their hands, it is actually quite serious. (The U.S. Navy and the National Science Foundation, sponsors of the research, weren't in it for the fun, I suspect.) And certainly, for managers responsible for moving goods from hundreds of origins to hundreds of destinations each day, development of optimization tools meets a real need. In fact, the routing sheet handed to your driver each time he pulls out of your yard bound for your customers' docks may well be the product of optimization software that grew out of the Traveling Salesman Problem. But at least his route won't include 24,978 stops in the Swedish boondocks.
