Category: 

What is the Traveling Salesman Problem?

Article Details
  • Written By: Malcolm Tatum
  • Edited By: Bronwyn Harris
  • Last Modified Date: 10 December 2016
  • Copyright Protected:
    2003-2016
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
The great magician and escape artist Harry Houdini died on Halloween in 1926.  more...

December 11 ,  1946 :  UNICEF was established.  more...

The traveling salesman problem is a traditional issue that has to do with making the most efficient use of resources while at the same time expending the least amount of energy in that utilization. The designation for this type of problem hails back to the days of the traveling salesman, who often wished to arrange travel in a manner that allowed for visiting the most towns without having to double back and cross into any given town more than once.

In a wider sense, the traveling salesman problem is considered to be a classic example of what is known as a tour problem. Essentially, any type of tour problem involves making a series of stops along a designated route and making a return journey without ever making a second visit to any previous stop. Generally, a tour problem is present when there is concern on making the most of available resources such as time and mode of travel to accomplish the most in results. Finding a solution to a tour problem is sometimes referred to as discovering the least-cost path, implying that the strategic planning of the route will ensure maximum benefit with minimum expenditure incurred.

Ad

The concept of the traveling salesman problem can be translated into a number of different disciplines. For example, the idea of combinatorial optimization has a direct relationship to the traveling salesman model. As a form of optimization that is useful in both mathematical and computer science disciplines, combinatorial optimization seeks to team relevant factors and apply them in a manner that will yield the best results with repeated usage.

In a similar manner, discrete optimization attempts to accomplish the same goal, although the term is sometimes employed to refer to tasks or operations that occur on a one-time basis rather than recurring. Discrete optimization also is helpful in computer science and mathematical disciplines. In addition, discrete optimization has a direct relationship to computational complexity theory and is understood to be of use in the development of artificial intelligence.

While the imagery associated with a traveling salesman problem may seem an oversimplification of these types of detailed options for optimization, the idea behind the imagery helps to explain a basic fundamental to any type of optimization that strives for efficiency. The traveling salesman problem that is solved will yield huge benefits in the way of maximum return for minimum investment of resources.

Ad

You might also Like

Recommended

Discuss this Article

MrMoody
Post 2

@miriam98 - The traveling salesman problem heuristics begin by treating each “city” the salesman has to travel to as a node. Then a line is drawn from where the salesman is at, to the city he is traveling to. Then a number, quantity or cost is attached to that line.

It would be like asking, what’s the cost for a direct flight to Houston? As a matter of fact, travel is one industry for which the traveling salesman problem is applicable, for obvious reasons.

So with each city as a node, and travel to each node having a “price” associated with it, the computer has to figure out the cheapest route for the salesman to travel to all the cities without going back and repeating his trip.

That’s an oversimplification, I guess, but that’s it in a nutshell. Like you said, modern computers are better able to do the number crunching and figure all the possible travel routes.

miriam98
Post 1

Back when I was in college we had a computer science professor who bragged that he had developed a traveling salesman problem genetic algorithm. He did this by stringing together a whole bunch of servers running nearly 24-7 to do the advanced number crunching.

I never did understand the explanation he gave about how he solved the problem (or claimed to solve it), but he sure did get a lot of funding for it.

Nowadays computers are more powerful and I don't think this problem is as hard to solve as it once was. It just requires a lot of processing time and the ability to solve for an undetermined number of destinations.

Post your comments

Post Anonymously

Login

username
password
forgot password?

Register

username
password
confirm
email