The Travelling Salesman Problem has plagued computer science for nearly sixty years. Countless hours have been spent on the problem. Countless millions of dollars—funneled through universities, corporations, and government contracts—have been poured into the quest for a solution. Countless computer scientists—withered, hapless creatures—have gone bald and blind, hunched over diagrams of circuitous graphs and motorway maps. Many of our brightest minds have wasted away, desperately searching for a solution.
This pernicious puzzle has claimed too steep a price.
Today I declare an end to the waste and futility that this problem has imposed upon our nation’s resources. Today I propose a Final Solution to the Travelling Salesman Problem.
To understand my solution, you must know something of the problem’s history.
The story goes that in the mid-1950s, a travelling salesman by the name of Richard Puce visited the Burbank home of famed computer scientist Edsger Dijkstra. He attempted to interest Dijkstra in the purchase of a fine Electrolux carpet cleaning device. Dijkstra—ever the gentleman—politely declined, but in the aftermath, the two began discussing some of the challenges of the salesman’s nomadic livelihood.
“Why, just this afternoon,” explained Mr. Puce, “I have to visit no less than sixty homes in six different cities.”
“Indeed,” replied Dr. Dijkstra.
“After leaving here I’ve got to head down to Long Beach, then San Pedro, over to Culver City, back up to Glendale, and then out to Pasadena. Now that’s a lot of driving!”
“Quite so,” answered the sage.
“I’ll probably travel 200 miles when all is said and done. Maybe more.”
“Yes I quite see the pr—”
“So you can see how much it means to me when a customer helps me out by giving one of these superb Electrolux appliances a whirl. There’s no obligation you understand…”
But Dijkstra, so they say, had already begun to see another avenue by which he might help the salesman on his way. At the next available opportunity, he inquired as to which order Mr. Puce intended to visit the required cities.
“Well, I don’t see that it makes that much of a difference, if you don’t mind me saying so,” answered Puce.
“Ah, but—but I think it very well might!” exclaimed Dijkstra, warming to the conversation. “I think if you choose the order carefully, you might be able to shave dozens of miles off your trip. You wouldn’t happen to have a map in your car would you?”
Puce warily produced the document, and Dijkstra, plucking a pen from Puce’s pocket, began to make some notes.
“You see,” continued Dijkstra, “if we consider the extreme case, we can easily discern that if you proceed from here to Long Beach, then back across to Pasadena, then right the way through town to San Pedro, then over again to Glensdale, then back through to Culver City—”
“Why would anyone do it that way?” inquired Puce.
“That’s my point exactly. The resulting graph is virtually a star. There is no question but that a great many redundant traversals of the edges will be required by the proposed route.”
Puce looked at him mutely.
“The total distance, my good man,” answered Dijkstra in measured tones, “of this sequence would be suboptimal.”
Puce shook his head.
Dijkstra took off his thick-rimmed, black glasses. “It would be a bloody long way to go, is what I’m trying to tell you.”
“Ah! I can see that,” replied Puce, and wiped his brow. “Is there a better way?”
“Certainly,” answered Dijkstra quickly. He found a second pen and began making marks.
“Intuitively we can see that any route in which near nodes are—in general—preferred over distant nodes will result in an overall route that tends to improve upon our first one.”
He completed the illustration, and both men stood by, regarding it for a moment.
Even Richard Puce saw the improvement.
It was then, on that sunny Burbank afternoon, that this hapless salesman, quite unknowingly, asked the fateful question.
“Is there a best route?”
“Oh I’m sure there is,” Dijkstra responded immediately, moving his pen toward the paper. Then he hesitated, and his eyes searched the map for some time.
After a moment, Puce interrupted. “Mr., uh—? Are you all right?”
No reply.
“Well, if it’s all the same to you, I think I should be going.” Puce reached for his map.
Dijkstra did not budge. “I’m sure there is a best route,” he said at last, his eyes not leaving the page.
Puce gripped the map by one corner. “I appreciate all your help. Uh, could I just—?”
“It’s eluding me just now, but it is surely a trivial matter. I think I just see… hm, no…”
Puce tugged harder. “That’s all right Mr., uh—I really had better get out on the road.”
“The road. The edge. Edges. Yes. Precisely,” Dijkstra continued to mutter.
Puce yanked once more on the map and it broke from the professor’s grasp.
Dijkstra, they say, stood blinking in the California sun for some time.
When Dijkstra’s wife arrived home that evening from her afternoon of Cribbage at the local Ladies’ Circle, she found him hunched over the kitchen table, a hand-drawn map of Los Angeles (he had reproduced it from memory) a few inches from his nose.
And so the Travelling Salesman Problem was born.
Since that time, computer scientists across the country have been enthralled by this strange puzzle.
The problem is this. Given a graph of nodes (say, cities) connected by edges (roads) of arbitrary lengths, what is the shortest route that visits every node at least once?
This question has proven very difficult. Specifically, the number of steps required to solve the problem grows rapidly as the number of “cities” grows. Like this:
| Cities | Steps |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5040 |
| 8 | 40320 |
| 9 | 362880 |
| 10 | 3628800 |
Which is to say:
This, my friends, is the Slope of Doom. Here there be dragons. Here angels fear to tread.
An ordinary person, using only his or her mind and a pencil, would struggle to solve a Travelling Salesman Problem involving as few as five cities. Six cities might be accomplished by someone going for a doctorate. For numbers greater than six, a computer must be employed.
But so devious is this puzzle that even computers are soon befuddled by numbers not much greater than ten. Experts have shown that if all the computers in the world were brought together to solve a Travelling Salesman Problem involving a mere thirty cities, the amount of time required to solve it would amount to more than 12 parsecs—even longer if the graph involved the Kessel Run.
This, my friends, is one difficult problem.
How then—you may well ask—has it claimed so many fruitless human hours—so many misspent tax dollars? Why haven’t computer scientists—or those who pay them—simply given up?
The answer, in a word, is usefulness.
Today there are over 20 million salespersons plying their trade in this country. (That archaic and hateful term, “salesmen” is preserved in the name of the problem only as a matter of tradition, in honor of the fallen dead.) Many of them travel extensively and so may rightly be considered “travelling salespeople.” Research shows that for an average trip, the typical salesperson visits upwards of 15 “nodes”—be they cities or shops or houses. If these 15 nodes are visited in a haphazard order, the cost in petroleum alone—not to mention emissive waste, human energy, etc.—quickly escalates. Thus the annual cost to the United States of suboptimal routes carried out daily by our millions of salespeople amounts to more than the cost of bedbugs, artichokes, vinyl, breath mints, and tape combined. The cost of wasteful salespeople is very nearly immeasurable.
A solution to the Travelling Salesman Problem—Richard Puce’s old dilemma—would mitigate these costs. The savings both to the individual salespeople, the companies they represent, and the American people would be significant.
The reason, then, that so many great computer scientific minds have pursued the dream of solving this problem for so long is that the rewards—both personal and societal—are great. Or would be, if such a solution could ever be found.
Yet sixty years have passed. Mankind is no closer to finding a solution than we were that sunny day in Burbank when the problem was first discovered. Since then a thousand wild schemes—interstellar computers, improbable quantum bits, so-called “approximating” algorithms—have been proposed, funded, and ultimately proven hopeless. All appearances say that we have as great a chance as finding a fast algorithm for solving large-scale Travelling Salesman Problems as we have of constructing a perpetual motion machine.
But I have seen a better way.
The solution lies with the salesmen.
What use is a salesman, after all? What is it they actually accomplish?
Computer scientists have spent the better part of sixty years trying to improve the efficiency of sales-related travel. But are salesmen actually worth this long and painstaking service? Might this not be a case of casting pearls before swine?
What have salesmen done for you lately?
The final solution which I propose to the Travelling Salesman Problem is just this: the eradication of salesmen.
Just think of it. If all the salesmen were suddenly gone, the Travelling Salesman Problem would become a thing of the past. Computer scientists across the country—yea, around the world!—could thrust aside from their weary desks the yellowing notes of their endless investigations into the problem. In that scramble of pages the liberation of computer scientists would be born! No more endless, fiddly, dagger-shaped graphs. No more pouring over atlases of the nation. No more tediously looking up the distance between cities using impressive-for-the-time-but-subsequently-inadequate printed tables.
The vigorous minds of a hundred thousand scientists would be set free from bondage in a moment!
The only question that remains is the means by which this solution might be carried out. I set this problem before you—a new problem, a replacement for the old, which I daresay will prove much more fruitful.
