Imagine a busy distribution center where machines and workers move optimally between each working and storage locations. Routes need to be planned well to meet strict time limits and keep costs and other factors low. This challenge is at the heart of the historically so-called traveling salesman problem (TSP). It’s not only in the logistic applications. This piece explores how the traveling salesman problem can be used in real life and manufacturing. It looks at how one can improve their route planning in all the industry.
While this problem is a classic in pure math and algorithmic studies, also studied in logistics with a more practical approach, it is almost unknown in other industries and manufacturing domains.
This post in a special focus on one algorithm of our post “the 10 main algorithms and methodologies to know in engineering”.
Key Takeaways
- The traveling salesman problem (TSP) is to find the most optimized route between several points.
- This problem started to gain interest in the 1930-1940
- It helps organizations enhance efficiency and reduce costs in their operations, limit resources and improve service delivery.
- The problem is widely applicable across different sectors and industries, not just in logistics and transports.
- As soon as there is more than a 12-20 points, the problem becomes too complex for calculating a perfect solution
- Several algorithms have been invented to find good approximations, thus not the perfect one
What is the Traveling Salesman Problem ?
The traveling salesman problem: finding the most efficient way for a salesperson to visit various cities and return to start. He must hit each city only once, aiming to cut the total distance to the shortest possible.
To understand the TSP definition, know that the number of routes grows as more cities are added. For example, four cities mean there are 24 possible paths. Adding more cities increases the challenge, leading to too many potential routes to consider.
Many businesses, like those in logistics, telecommunications, and manufacturing, face this issue often. A good solution to the traveling salesman problem could save money and boost efficiency. It shows how theoretical math-related research helps solve real-life problems.
Why is it a though problem?
If there are n cities, there are (n-1)!/2 unique tours (the /2 comes if the tour is a cycle and directions don’t matter).
Additionally, slight changes in input (e.g., distances or new cities) alter completely the optimal route, making the problem highly sensitive and complex to solve. | Cities visited | Possible routes / combinations |
| 3 | 6 | |
| 4 | 24 | |
| 5 | 120 | |
| 6 | 720 | |
| 7 | 5040 | |
| … | … | |
| 20 | 6 × 1016 (almost 2 millennia if each route calculation would require a microsecond) | |
| 25 | more than the age of our univers if each route calculation would require a microsecond |
History of the Traveling Salesman Problem
The Traveling Salesman Problem started in the early 1900s, thanks to some smart mathematicians. William Rowan Hamilton and Karl Menger were big names who helped us understand how to navigate complex paths. They really focused on making it easier to find the best route.
By the 1930s, people began to define the TSP more clearly. Scholars from Vienna and Harvard worked together on this. They started to see how it could solve real problems, like making school bus routes better. This made more people interested in solving the TSP.
The TSP became super useful for businesses, especially those in shipping and transportation. In the 1950s and 1960s, the RAND Corporation stepped up. They came up with smart ways to tackle the TSP that became a key part of making logistics run smoother.
Why is it an NP-Hard Problem?
The Traveling Salesman Problem is a tough puzzle in computer science. It’s marked famous as an NP-hard problem because it’s really hard to solve as it grows exponentially faster than any computer can handle if there are a lot of cities.
What is an “NP-hard” problem: in computer science and computational complexity theory, “NP” stands for Non-deterministic Polynomial time. An NP-hard problem is at least as hard as the hardest problems in NP, meaning every problem in NP can be polynomial-time reduced to it. Unlike NP-complete problems that can be verified in polynomial time, there is no known algorithm that solves NP-hard problems in polynomial time.
Because of this, experts use special shortcuts and smart guesses. These tricks help them find pretty good paths without needing impossible amounts of computing power to get a decent solution that works well enough in real life. See chapter below some of these approaches to help them deal with the huge number of possible paths.
Industrial Applications
The Traveling Salesman Problem helps different industries making things like routes and processes better. Many areas like logistics, transportation, and manufacturing use TSP to make their work easier. TSP approximate solutions and their variants are used in:
TransportationThe most similar usages to the original salesman problem:
| Routing
 Firms can set up their network nodes in the best way to cut down on signal loss and boosts performance in network design. |
Manufacturing & Machines
| In-house Logistics
It helps plan paths smartly for equipment and lines. This means machines and assembly lines are laid out better, saving time, making things fast and helping ergonomics.
|
Science & Research
|  |
Methods of Approximating the Best Answer Quickly
While this is out of the scope of this post to list and provide all details of almost 100 years of science research on this topic, here below some methods currently used.
These methods do not always find the best solution, but they get pretty close without taking a lot of time.
- Nearest Neighbor (NN) Heuristic
- Process: start at a random city; repeatedly visit the nearest unvisited city until all are visited.
- Pros: fast, simple, but not always close to optimal.
- Christofides’ Algorithm
- Process: builds a tour using minimum spanning trees and perfect matching (guarantees a solution within 1.5 times the optimal for metric TSP).
- Pros: best-known performance guarantee for metric TSP.
- Greedy Algorithm
- Process: at each step, pick the shortest available edge that does not form a cycle (except the final edge).
- Pros: fast, but usually not optimal.
- 2-opt and k-opt Local Search
- Process: iteratively replace k edges in the tour with different edges to reduce total length (2-opt, 3-opt are common).
- Pros: significantly improves initial heuristics, widely used for post-processing.
- Genetic Algorithms (GA)
- Process: use population-based search with crossover and mutation to evolve better solutions over generations.
- Pros: flexible, can escape local minima.
- Simulated Annealing (SA)
- Process: probabilistically accepts worse solutions occasionally to avoid local optima, gradually reducing “temperature”.
- Pros: effective for complex search spaces.
Other notable methods: Ant Colony Optimization, Tabu Search, Lin-Kernighan heuristic.
Conclusion on the TSP
The Traveling Salesman Problem (TSP) is crucial for many industries, while still unknown for some. It shows how important it is for improving efficiency and saving costs. Many organizations already use TSP solutions to make their routes and work plans better.
Finding new ways to solve this old problem shows its lasting value. The TSP solving is still a challenge with potential new options thanks to advancements in technology such as algorithms improved by artificial intelligence and machine learning will open new ways to solve this tough challenges. This progress will literally open new routes, make operations strategies better and help organizations streamline their processes more efficiently.
Related Readings
- Combinatorial Optimization Algorithms: exact and heuristic methods like Genetic Algorithms, Simulated Annealing
- Graph Theory and Network Analysis: Hamiltonian cycles, shortest path algorithms
- Operations Research: linear programming, integer programming
- Computational Complexity Theory: NP-hardness characterization
- Meta Heuristics and Swarm Intelligence: Ant Colony Optimization, Particle Swarm Optimization in solving TSP
FAQ
What is the Traveling Salesman Problem (TSP)?
The Traveling Salesman Problem (TSP) is an important puzzle. It’s about finding the shortest path that visits each location only once and returns to the start. This is key for businesses that need to plan routes efficiently. The major challenge is the enormous number of possible routes, which grows with every new location. Also, real-world issues like traffic and deadlines make planning even harder.
Why is the TSP considered an NP-hard problem?
The TSP is tough because the number of potential routes increases exponentially with each additional city. This makes it very hard to find the best route quickly, especially as more than 20 locations are added.
What are some common applications of TSP?
TSP is used in many areas, like making delivery routes more efficient and managing supply chains. It’s also helpful in healthcare for scheduling visits and in robotics for guiding movements or in manufacturing electronics positioning or testing small components and copper routes.
How does graph theory and heuristic algorithms relate to the TSP?
Graph theory is the math behind the TSP. It uses dots (vertices) to represent cities and lines (edges) for the paths between them. This helps develop methods to solve TSP problems effectively. Heuristic algorithms are smart shortcuts for solving TSP. They help find good enough routes quickly, even if they’re not perfect. Methods like the Nearest Neighbor and Greedy algorithms are common examples. Techniques like simulated annealing and genetic algorithms are also particularly helpful for big problems.
How does TSP impact supply chain efficiency?
TSP boosts supply chain efficiency by refining transportation routes. This leads to costs going down, better use of resources, and improved coordination among everyone involved. In healthcare, TSP optimizes how home care and emergency services are provided. It ensures that medical supplies are delivered promptly, enhancing overall patient care and satisfaction.
EN 
FR 
DE 
ES 
IT