Editing Travelling salesman problem (section)

{{Short description|NP-hard problem in combinatorial optimization}}
{{Use Oxford spelling|date=August 2016}}
{{Use dmy dates|date=November 2020}}
[[File:Illustration of an unsolved travelling salesman problem.svg|thumb|right|The travelling salesman problem seeks to find the shortest possible loop that connects every red dot.]]
[[File:GLPK solution of a travelling salesman problem.svg|thumb|right|Solution of the above problem]]
In the [[Computational complexity theory|theory of computational complexity]], the '''travelling salesman problem''' ('''TSP''') asks the following question: "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-hardness|NP-hard]] problem in [[combinatorial optimization]], important in [[theoretical computer science]] and [[operations research]].

The [[Traveling purchaser problem|travelling purchaser problem]], the [[vehicle routing problem]] and the [[ring star problem]]<ref name="Labbe2004">{{cite journal |last1=Labbé |first1=Martine |last2=Laporte |first2=Gilbert |last3=Martín |first3=Inmaculada Rodríguez |last4=González |first4=Juan José Salazar |title=The Ring Star Problem: Polyhedral analysis and exact algorithm |journal=Networks |date=May 2004 |volume=43 |issue=3 |pages=177–189 |doi=10.1002/net.10114 |language=en |issn=0028-3045}}</ref> are three generalizations of TSP.

The decision version of the TSP (where given a length ''L'', the task is to decide whether the graph has a tour whose length is at most ''L'') belongs to the class of [[NP-completeness|NP-complete]] problems. Thus, it is possible that the [[Best, worst and average case|worst-case]] [[Time complexity|running time]] for any algorithm for the TSP increases [[Time complexity#Superpolynomial time|superpolynomially]] (but no more than [[Exponential time hypothesis|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 (computing)|benchmark]] for many optimization methods. Even though the problem is computationally difficult, many [[heuristic]]s and [[exact algorithm]]s are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%.<ref>See the TSP world tour problem which has already been solved to within 0.05% of the optimal solution. [http://www.math.uwaterloo.ca/tsp/world/]</ref>

The TSP has several applications even in its purest formulation, such as [[planning]], [[logistics]], and the manufacture of [[Integrated circuit|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. The TSP also appears in astronomy, as astronomers observing many sources want to minimize the time spent moving the telescope between the sources; in such problems, the TSP can be embedded inside an [[Optimal control|optimal control problem]]. In many applications, additional constraints such as limited resources or time windows may be imposed.

{{Toclimit|3}}