Is it hopeless to try to compute the shortest route to visit a large number of cities? Not just a good route but the guaranteed shortest. The task is the long-standing challenge known as the traveling salesman problem, or TSP for short.

Finding a method that can quickly solve every example of the TSP would be a stunning breakthrough in mathematics. Using complexity theory, such a method would allow us to solve efficiently any computational problem for which answers can be easily verified. Most mathematicians expect this to be impossible.

But suppose that you are handed the locations of 100,000 cities. Is it really impossible to find the shortest route? We are not asking for a solution to every instance of the TSP, just the quickest way around these specific locations.

To take up the challenge, your best bet is to follow Yogi Berra’s advice: “When you come to a fork in the road, take it.” A tool called linear programming allows us to do just that by assigning fractions to roads that join pairs of cities rather than deciding immediately whether to use a road or not. In this model, it is perfectly fine to send half a salesman along both branches of the fork. The process begins with the requirement that, for every city, the fractions assigned to the arriving and departing roads each sum to 1. Then, step by step, further restrictions are added, each involving sums of fractions assigned to roads. Linear programming eventually points us to the best decision for each road and thus the shortest possible route.

I should add that 100,000 cities is not a hypothetical challenge. Current computations are zeroing in on the solution to a pretty set of 100,000 points created by Robert Bosch of Oberlin College, where the tour traces out a drawing of the Mona Lisa. We may not be able to knock off every example of the TSP, but new ideas can push the frontiers of solvability.

Here is the big picture: complexity theory suggests there are limits to the power of general computational techniques in science and elsewhere. What are these limits and how widely do they constrain our quest for knowledge? That is what research into the TSP is all about. 

This article was published in print as "The Case of the Traveling Salesman."

4 Comments

1. 1. jtdwyer 01:26 PM 5/18/12

   "I should add that 100,000 cities is not a hypothetical challenge. Current computations are zeroing in on the solution to a pretty set of 100,000 points created by Robert Bosch of Oberlin College, where the tour traces out a drawing of the Mona Lisa."
   
   A route that traces out an image of the Mona Lisa is not considered hypothetical?!?
   
   Please come down from your lofty tower - you must be starving up there...

   Reply | Report Abuse | Link to this

2. 2. LarryW 09:03 PM 5/19/12

   Not a useful article. Define the problem, why it is difficult, what is complexity theory, why it is an important model for computation, why the solution of TSP could lead to solution of other problems, and how such a solution might actually cause problems (such as making computer security harder to enforce), TSP's relationship to NP complete problems.

   Reply | Report Abuse | Link to this

3. 3. Will_in_BC 01:36 PM 5/21/12

   I agree he article is a bit fluffy. A good explanation of NP-Complete can be found here:
   
   http://explorations.chasrmartin.com/2008/11/24/what-are-p-np-complete-and-np-hard/

   Reply | Report Abuse | Link to this

4. 4. Eco_steve 08:49 AM 6/24/12

   One simple solution is to define the perimeter, then 'shrink-wrap' it until all points have been touched. The solution may not be absolutely optimal, but it is very fast.
   The other, easier solution is to ask your sat-nav...

   Reply | Report Abuse | Link to this