We are independent & ad-supported. We may earn a commission for purchases made through our links.
Advertiser Disclosure
Our website is an independent, advertising-supported platform. We provide our content free of charge to our readers, and to keep it that way, we rely on revenue generated through advertisements and affiliate partnerships. This means that when you click on certain links on our site and make a purchase, we may earn a commission. Learn more.
How We Make Money
We sustain our operations through affiliate commissions and advertising. If you click on an affiliate link and make a purchase, we may receive a commission from the merchant at no additional cost to you. We also display advertisements on our website, which help generate revenue to support our work and keep our content free for readers. Our editorial team operates independently of our advertising and affiliate partnerships to ensure that our content remains unbiased and focused on providing you with the best information and recommendations based on thorough research and honest evaluations. To remain transparent, we’ve provided a list of our current affiliate partners here.

What is the Traveling Salesman Problem?

Malcolm Tatum
Updated May 21, 2024
Our promise to you
All The Science is dedicated to creating trustworthy, high-quality content that always prioritizes transparency, integrity, and inclusivity above all else. Our ensure that our content creation and review process includes rigorous fact-checking, evidence-based, and continual updates to ensure accuracy and reliability.

Our Promise to you

Founded in 2002, our company has been a trusted resource for readers seeking informative and engaging content. Our dedication to quality remains unwavering—and will never change. We follow a strict editorial policy, ensuring that our content is authored by highly qualified professionals and edited by subject matter experts. This guarantees that everything we publish is objective, accurate, and trustworthy.

Over the years, we've refined our approach to cover a wide range of topics, providing readers with reliable and practical advice to enhance their knowledge and skills. That's why millions of readers turn to us each year. Join us in celebrating the joy of learning, guided by standards you can trust.

Editorial Standards

At All The Science, we are committed to creating content that you can trust. Our editorial process is designed to ensure that every piece of content we publish is accurate, reliable, and informative.

Our team of experienced writers and editors follows a strict set of guidelines to ensure the highest quality content. We conduct thorough research, fact-check all information, and rely on credible sources to back up our claims. Our content is reviewed by subject-matter experts to ensure accuracy and clarity.

We believe in transparency and maintain editorial independence from our advertisers. Our team does not receive direct compensation from advertisers, allowing us to create unbiased content that prioritizes your interests.

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.

All The Science is dedicated to providing accurate and trustworthy information. We carefully select reputable sources and employ a rigorous fact-checking process to maintain the highest standards. To learn more about our commitment to accuracy, read our editorial process.
Malcolm Tatum
By Malcolm Tatum
Malcolm Tatum, a former teleconferencing industry professional, followed his passion for trivia, research, and writing to become a full-time freelance writer. He has contributed articles to a variety of print and online publications, including All The Science, and his work has also been featured in poetry collections, devotional anthologies, and newspapers. When not writing, Malcolm enjoys collecting vinyl records, following minor league baseball, and cycling.
Discussion Comments
By MrMoody — On May 16, 2011

@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.

By miriam98 — On May 14, 2011

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.

Malcolm Tatum
Malcolm Tatum
Malcolm Tatum, a former teleconferencing industry professional, followed his passion for trivia, research, and writing...
Learn more
All The Science, in your inbox

Our latest articles, guides, and more, delivered daily.

All The Science, in your inbox

Our latest articles, guides, and more, delivered daily.