The Traveling Salesman Problem: An Optimization Model

A guest post today from Debra Johnson. I have not altered the American spelling or the politically incorrect title!

Traveling Salesman

FreeDigitalPhotos.net

Given a salesman who needs to travel to a certain set of cities, what is the least expensive way for him to get to all of his destinations and return home? This question is known as the traveling salesman problem (TSP), and it is an important problem for computational mathematicians. Because the problem is one of general optimization, its solution has applications for diverse fields including transportation, electronics and genetics. Even though it has been formally studied by mathematicians since the 1930s, no general solution has yet been discovered for the TSP.

Attempts at solving specific instances of the TSP have taken different forms and have been made by mathematicians, computer scientists, chemists, physicists and other scientists. In the 1950s and 1960s, integer linear programming was used to solve an instance of 49 cities. In the 1990s, a group of mathematicians developed a computer program called Concorde that is capable of solving for larger numbers of cities. In fact, William Cook, one of the program’s developers, worked with other scientists to solve a record 33,810 city tour based on a layout problem for a microchip.

The actual problem is, on its surface, a simple one. However, current methods require each instance to be solved individually. A general solution has eluded mathematicians for decades. This difficulty is due to the fact that the TSP is an NP-hard problem. This means that, among other things, the TSP is a problem in which correct solutions are easy to verify, but there is no efficient way to solve the problem itself. This also means that a solution to the TSP would put to rest the question of whether or not it is possible to solve NP-complete problems. Called the P versus NP problem, this is one of the most challenging questions facing mathematicians today. In fact, it was designated a millennium prize problem by the Clay Mathematics Institute. This means that the one who solves this problem will win a million dollar prize.

In addition to putting the P versus NP problem to rest, a solution to the TSP would revolutionize many fields. Far from being merely a mathematical curiosity, the TSP has many practical applications. Obviously, it directly applies to logistics and transportation. This makes finding a solution valuable to the military, commercial delivery services, companies that schedule home service calls, bus companies and many others. The model is also general enough that it can be applied to other fields such as microchip design, genome sequencing, fiber optic network design and others. The wide applicability of the TSP model, the million dollar prize and the difficulty of finding a general solution make the TSP an intriguing and important problem in applied mathematics.
About the Author:

This guest post is contributed by Debra Johnson, blogger and editor of live in nanny.

She welcomes your comments at her email Id: – jdebra84 @ gmail.com.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, guest posts and tagged . Bookmark the permalink.

6 Responses to The Traveling Salesman Problem: An Optimization Model

  1. Laurent says:

    Sometimes, Best is the enemy of Good (Enough). Sure, a general solution would be marvelous, but a good computational heuristics for cases where n is < 1000 would be tremendously useful to a lot of applications.
    As it stands, the NP scarecrow turns everyone away on the basis that no general solution has been found…leaving truck drivers in the neighborhood to a random walk of fuel-inefficient deliveries.

    • I don’t agree. I think that the world is big enough for the Good and the Best to coexist.

      I have been to several conference talks (most recently just last December) where somebody presented a new and improved heuristic for TSP. Even if there were an abstract proof that P=NP, this activity would continue.

      A similar case fairly recently was the proof that primality testing can be done in polynomial time. It was certainly not the case that people immediately stop using probabilistic algorithms for primality testing. Or again, Khachian’s ellipsoid method showed that linear programming is polynomial-time, but a lot of people went on using the simplex method (and still do).

      Another point is that complexity theory is wide enough to embrace approximation. There are some cases where, even though exact calculation is hard, there is an efficient approximation algorithm; but many more where this is not known.

      • Laurent says:

        I didn’t mean mathematicians around the world should stop looking for a general solution, Peter.
        All I meant is that, in my very specific, pointy-haired environment, if someone puts the NP tag on an approach, it’s the kiss of death. We won’t consider any approximation, any heuristics…anything, we will move right along and try to sidestep the “problem”, as if it were the plague.
        What I meant is that, even though some problems are truly NP, under certain conditions (where n is kept below a limit), they are tractable and can be addressed quite elegantly using an approximation or a heuristics.
        In my environment, which is not focused on mathematics, no one should read the NP sign as meaning “dead end”.

        In that spirit, could you share a link to that talk of last December?

      • Bill Fahle says:

        An interesting result I saw recently had to do with the so-called gas station problem. It’s a case where adding a realistic constraint to the problem makes it solvable.
        http://www.cs.umd.edu/projects/gas/gas-station.pdf

    • Gordon Royle says:

      Just picking a nit… the NP tag on its own does not mean that the problem is necessarily hard; all polynomial time or even trivial decision problems are in NP.

      It is the NP-hard or NP-complete problems that cause difficulties.

  2. gold price says:

    The actual problem is, on its surface, a simple one. However, current methods require each instance to be solved individually. A general solution has eluded mathematicians for decades. This difficulty is due to the fact that the TSP is an NP-hard problem. This means that, among other things, the TSP is a problem in which correct solutions are easy to verify, but there is no efficient way to solve the problem itself. This also means that a solution to the TSP would put to rest the question of whether or not it is possible to solve NP-complete problems. Called the P versus NP problem, this is one of the most challenging questions facing mathematicians today. In fact, it was designated a millennium prize problem by the Clay Mathematics Institute. This means that the one who solves this problem will win a million dollar prize.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s