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
Other articles related to "problem, travelling salesman problem, salesman, problems, travelling salesman":
... In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a ... Notable examples include the travelling salesman problem, which asks for the route taken by the salesman, and the integer factorization problem, which ... Function problems are more awkward to study than decision problems because they don't have an obvious analogue in terms of languages, and because the notion of reduction between ...
... Travelling Salesman, by director Timothy Lanzone, is the story of 4 mathematicians hired by the US Government to solve the most elusive problem in computer-science history P vs ...
Famous quotes containing the words problem, travelling and/or salesman:
“I dont have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I dont think any of us would challenge that. I do have a problem with the singular focus on this, as if thats the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)
“In America there are two classes of travelfirst class, and with children. Travelling with children corresponds roughly to travelling third-class in Bulgaria. They tell me there is nothing lower in the world than third-class Bulgarian travel.”
—Robert Benchley (18891945)
“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)