What is the Traveling Salesman Problem?
Malcolm Tatum
Malcolm Tatum
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.
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.
Malcolm Tatum
After many years in the teleconferencing industry, Michael decided to embrace his passion for trivia, research, and writing by becoming a full-time freelance writer. Since then, he has contributed articles to a variety of print and online publications, including AllTheScience, and his work has also appeared in poetry collections, devotional anthologies, and several newspapers. Malcolm’s other interests include collecting vinyl records, minor league baseball, and cycling.
Malcolm Tatum
After many years in the teleconferencing industry, Michael decided to embrace his passion for trivia, research, and writing by becoming a full-time freelance writer. Since then, he has contributed articles to a variety of print and online publications, including AllTheScience, and his work has also appeared in poetry collections, devotional anthologies, and several newspapers. Malcolm’s other interests include collecting vinyl records, minor league baseball, and cycling.
AS FEATURED ON:
AS FEATURED ON:
-
![Woman standing behind a stack of books]()
Woman standing behind a stack of books
Discussion Comments
@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.
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