The travelling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city. It is a special case of the travelling purchaser problem.
The problem was first formulated as problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.
The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.
In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether any tour is shorter than L) belongs to the class of NP-complete problems. Thus, it is likely that the worst-case running time for any algorithm for the TSP increases exponentially with the number of cities.
Read more about Travelling Salesman Problem: History, Computing A Solution, Human Performance On TSP, TSP Path Length For Random Pointset in A Square, Analyst's Travelling Salesman Problem, Free Software For Solving TSP, Popular Culture
Famous quotes containing the words travelling, salesman and/or problem:
“I have been told lately that Fuseli was travelling by coach and a gentleman opposite him said: I understand, Mr. Fuseli, that you are a painter; it may interest you to know that I have a daughter who paints on velvet.
Fuseli rose instantly and said in a strong foreign accent, Let me get out.”
—Samuel Butler (18351902)
“Nobody dast blame this man.... For a salesman, there is no rock bottom to the life. He dont put a bolt to a nut, he dont tell you the law or give you medicine. Hes a man way out there in the blue, riding on a smile and a shoeshine. And when they start not smiling backthats an earthquake. And then you get yourself a couple of spots on your hat, and youre finished. Nobody dast blame this man. A salesman is got to dream, boy. It comes with the territory.”
—Arthur Miller (b. 1915)
“It is very comforting to believe that leaders who do terrible things are, in fact, mad. That way, all we have to do is make sure we dont put psychotics in high places and weve got the problem solved.”
—Tom Wolfe (b. 1931)