Fall 2012

Coming Full Circle

The Traveling Salesman Problem and the dream of optimality

D. Graham Burnett

The problem is easily stated: given a finite number of points, find the shortest connecting path—the shortest line that touches each point once, and closes on itself by returning to the point of departure. What could be more straightforward? It is a problem a child can understand—a simple game of connect-the-dots.

It is also, however, a problem of absolutely legendary difficulty. Add more than a handful of points, and a brute-force solution requires more computer-years than there are particles in the universe. Untold millions of human- and machine-hours have now been expended on the problem, which has come to function as a touchstone for theories of complexity, and as a kind of conceptual fetish object at the center of the overlapping disciplines of applied mathematics, algorithm theory, and computational geometry. There is, at present, a million-dollar bounty on its head, and some of the very deepest questions in theoretical computer science hang on the prospect of a general solution.1

Mathematicians call it the TSP—the Traveling Salesman Problem, a moniker that speaks subtly to the twinned genealogies of capitalism and calculating rationality. And indeed the problem—which has become nothing less than a model system for understanding what can be understood—began its life as a head-scratcher for the shock troops of consumer economics, those late eighteenth- and early nineteenth-century itinerant missionaries of an increasingly abstract and globalizing market. Those men girded their loins and shouldered their sample cases only after perusing the new cartographies made available by centralizing states and expanding empires. They plotted their routes, these drummers, and did so with an eye on the bottom line. Which is to say, actual travelling salesmen fretted the TSP long before a clutch of Cold War theoreticians at the RAND Corporation found their way to it, and restyled it as an all-purpose test of number-crunching power and analytic ingenuity. Tellingly, the earliest formulation of the problem would seem to hail from a German-language gazetteer/handbook prepared in the early 1830s for commercial travelers intending to make tours through the Swiss cantons and the German lands. That volume (Der Handlungsreisende—von einem alten Commis-Voyageur), mindful that time and space were money, carefully laid out a thirty-three-city circuit—Freiberg-Dresden-Leipzig-Halle, etc.—that pretended to optimality.2

Optimality. Life itself is obviously not an optimization function. Nevertheless, one could do worse than describe modernity as the ideological commitment to a progressive extension of optimization logic to domains of self and society not previously understood to yield to such treatment. Where the limits of this exercise lie remains unclear. Again and again it has proven possible (and profitable) to step over the various boundaries inscribed by tradition, habit, and custom. By these lights, “logistics”—the formal science of spatio-temporal optimization; the toolkit for synchronized coordination of human beings and materials in dynamic systems; the study of all problems that can be stated in the form, “Who and what are where when, and how could we do it better?”—must be understood as nothing less than the standard-bearer for social, political, and economic transformation across the last two centuries. Where the formal concepts and technics of logistics have gone—and they have sequenced impressively through war, wealth production, and governance—the modern world has fol

Subscribe to access our entire archive.
Log In and read it now.