Editing Travelling salesman problem (section)

== History ==

The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through [[Germany]] and [[Switzerland]], but contains no mathematical treatment.<ref>[https://zs.thulb.uni-jena.de/receive/jportal_jparticle_00248075 "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur"] (The travelling salesman – how he must be and what he should do in order to get commissions and be sure of the happy success in his business – by an old ''commis-voyageur'')</ref>

[[File:William Rowan Hamilton painting.jpg|thumb|William Rowan Hamilton, c. 1850]]

The TSP was mathematically formulated in the 19th century by the Irish mathematician [[William Rowan Hamilton]] and by the British mathematician [[Thomas Kirkman]]. Hamilton's [[icosian game]] was a recreational puzzle based on finding a [[Hamiltonian path|Hamiltonian cycle]].<ref>A discussion of the early work of Hamilton and Kirkman can be found in ''[[Graph Theory, 1736–1936]]'' by Biggs, Lloyd, and Wilson (Clarendon Press, 1986).</ref> The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at [[Harvard University|Harvard]], notably by [[Karl Menger]], who defines the problem, considers the obvious [[Brute-force search|brute-force algorithm]], and observes the non-optimality of the [[nearest neighbour algorithm|nearest neighbour]] heuristic:
{{Blockquote|
We denote by ''messenger problem'' (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.<ref>Cited and English translation in {{harvp|Schrijver|2005}}. Original German: "Wir bezeichnen als ''Botenproblem'' (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."</ref>}}

It was first considered mathematically in the 1930s by [[Merrill M. Flood]], who was looking to solve a school bus routing problem.<ref name="Wiley">{{Cite book|url={{google books |plainurl=y |id=qbFlMwEACAAJ}}|title=The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization|last=Lawler|first=E. L.|date=1985|publisher=John Wiley & sons|isbn=978-0-471-90413-7|edition=Repr. with corrections.}}</ref> [[Hassler Whitney]] at [[Princeton University]] generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling [or traveling] salesman problem" was the 1949 [[RAND Corporation]] report by [[Julia Robinson]], "On the Hamiltonian game (a traveling salesman problem)."<ref name="Robinson1949">{{cite tech report |last1=Robinson |first1=Julia |title=On the Hamiltonian game (a traveling salesman problem) |date=5 December 1949 |id=RM-303 |url=https://apps.dtic.mil/sti/tr/pdf/AD0204961.pdf |access-date=2 May 2020 |publisher=The RAND Corporation |location=Santa Monica, CA |language=en |via=Defense Technical Information Center}}</ref><ref name="Schrijver2005">A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in {{harvp|Schrijver|2005}}.</ref>

In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the United States after the [[RAND Corporation]] in [[Santa Monica]] offered prizes for steps in solving the problem.<ref name="Wiley"/> Notable contributions were made by [[George Dantzig]], [[Delbert Ray Fulkerson]], and [[Selmer M. Johnson]] from the RAND Corporation, who expressed the problem as an [[integer linear program]] and developed the [[Cutting-plane method|cutting plane]] method for its solution. They wrote what is considered the seminal paper on the subject in which, with these new methods, they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. Dantzig, Fulkerson, and Johnson, however, speculated that, given a near-optimal solution, one may be able to find optimality or prove optimality by adding a small number of extra inequalities (cuts). They used this idea to solve their initial 49-city problem using a string model. They found they only needed 26 cuts to come to a solution for their 49 city problem. While this paper did not give an algorithmic approach to TSP problems, the ideas that lay within it were indispensable to later creating exact solution methods for the TSP, though it would take 15 years to find an algorithmic approach in creating these cuts.<ref name="Wiley"/> As well as cutting plane methods, Dantzig, Fulkerson, and Johnson used [[branch and bound|branch-and-bound]] algorithms perhaps for the first time.<ref name="Wiley"/>

In 1959, [[Jillian Beardwood]], J.H. Halton, and [[John Hammersley]] published an article entitled "The Shortest Path Through Many Points" in the journal of the [[Cambridge Philosophical Society]].{{sfnp|Beardwood|Halton|Hammersley|1959}} The Beardwood–Halton–Hammersley theorem provides a practical solution to the travelling salesman problem. The authors derived an asymptotic formula to determine the length of the shortest route for a salesman who starts at a home or office and visits a fixed number of locations before returning to the start.

In the following decades, the problem was studied by many researchers from [[mathematics]], [[computer science]], [[chemistry]], [[physics]], and other sciences. In the 1960s, however, a new approach was created that, instead of seeking optimal solutions, would produce a solution whose length is provably bounded by a multiple of the optimal length, and in doing so would create lower bounds for the problem; these lower bounds would then be used with branch-and-bound approaches. One method of doing this was to create a [[minimum spanning tree]] of the graph and then double all its edges, which produces the bound that the length of an optimal tour is at most twice the weight of a minimum spanning tree.<ref name="Wiley" />

In 1976, [[Nicos Christofides|Christofides]] and Serdyukov (independently of each other) made a big advance in this direction:<ref name="bs20">{{Cite journal|last1=van Bevern|first1=René|last2=Slugina|first2=Viktoriia A.|year=2020|title=A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem|journal=Historia Mathematica|volume=53|pages=118–127|doi=10.1016/j.hm.2020.04.003|arxiv=2004.02437|s2cid=214803097}}</ref> the [[Christofides algorithm|Christofides–Serdyukov algorithm]] yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution. As the algorithm was simple and quick, many hoped it would give way to a near-optimal solution method. However, this hope for improvement did not immediately materialize, and the Christofides–Serdyukov algorithm remained the method with the best worst-case scenario until 2011, when a (very) slightly improved approximation algorithm was developed for the subset of "graphical" TSPs.<ref>{{Cite magazine|last1=Klarreich|first1=Erica|title=Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem|url=https://www.wired.com/2013/01/traveling-salesman-problem/|magazine=WIRED|access-date=2015-06-14|date=2013-01-30}}</ref> In 2020, this tiny improvement was extended to the full (metric) TSP.<ref>{{cite web |last1=Klarreich |first1=Erica |author-link1=Erica Klarreich |title=Computer Scientists Break Traveling Salesperson Record |url=https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/ |website=Quanta Magazine |access-date=13 October 2020 |language=en |date=8 October 2020}}</ref><ref>{{citation
 | last1 = Karlin | first1 = Anna R. | author1-link = Anna Karlin
 | last2 = Klein | first2 = Nathan
 | last3 = Gharan | first3 = Shayan Oveis
 | editor1-last = Khuller | editor1-first = Samir | editor1-link = Samir Khuller
 | editor2-last = Williams | editor2-first = Virginia Vassilevska | editor2-link = Virginia Vassilevska Williams
 | arxiv = 2007.01409
 | contribution = A (slightly) improved approximation algorithm for metric TSP
 | doi = 10.1145/3406325.3451009
 | pages = 32–45
 | title = STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021
 | year = 2021| isbn = 978-1-4503-8053-9 | s2cid = 220347561 }}</ref>

[[Richard M. Karp]] showed in 1972 that the [[Hamiltonian cycle]] problem was [[NP-complete]], which implies the [[NP-hard]]ness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.

Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2,392 cities, using cutting planes and [[branch and bound|branch-and-bound]].

In the 1990s, [[David Applegate|Applegate]], [[Robert E. Bixby|Bixby]], [[Vašek Chvátal|Chvátal]], and [[William J. Cook|Cook]] developed the program ''Concorde'' that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2006, Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2–3% of an optimal tour.<ref name="rggo">{{citation
 | last1 = Rego | first1 = César
 | last2 = Gamboa | first2 = Dorabela
 | last3 = Glover | first3 = Fred
 | last4 = Osterman | first4 = Colin
 | doi = 10.1016/j.ejor.2010.09.010
 | issue = 3
 | journal = [[European Journal of Operational Research]]
 | mr = 2774420
 | pages = 427–441
 | title = Traveling salesman problem heuristics: leading methods, implementations and latest advances
 | volume = 211
 | year = 2011| s2cid = 2856898
 }}.</ref>