Traveling salesman problem
The traveling salesman problem (also called the traveling salesperson problem or TSP) asks: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.
The traveling purchaser problem and vehicle routing problems are both TSP generalizations.
In the theory of computational complexity, the decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) belongs to the class of NP-complete problems. Thus, the worst-case running time for any algorithm for the TSP may increase super polynomially (but no more than exponentially) with the number of cities.
The problem was first formulated 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 complex, many heuristics and exact algorithms are known so that some instances with tens of thousands of cities can be solved entirely, and even issues with millions of cities can be approximated within a small fraction of 1%.
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 traveling times or cost or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimize the time spent moving the telescope between the authorities; in such problems, the TSP can be embedded inside an optimal control problem. Additional constraints, such as limited resources or time windows, may be imposed in many applications.
The original article is on Wikipedia.