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.
The travelling salesman problem was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman. Hamilton’s Icosian Game was a recreational puzzle based on finding a Hamiltonian cycle. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic:
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.
Hassler Whitney at Princeton University introduced the name travelling salesman problem soon after.
In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the USA. Notable contributions were made by George Dantzig, Delbert Ray Fulkerson and Selmer M. Johnson at the RAND Corporation in Santa Monica, who expressed the problem as an integer linear program and developed the cutting plane method for its solution. 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. In the following decades, the problem was studied by many researchers from mathematics, computer science, chemistry, physics, and other sciences.
Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness 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 2392 cities, using cutting planes and branch-and-bound.
In the 1990s, Applegate, Bixby, Chvátal, and 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 2005, Cook and others computed an optimal tour through a 33,810-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 1% of an optimal tour.
Read more about this topic: Travelling Salesman Problem
Famous quotes containing the word history:
“The myth of independence from the mother is abandoned in mid- life as women learn new routes around the mother—both the mother without and the mother within. A mid-life daughter may reengage with a mother or put new controls on care and set limits to love. But whatever she does, her child’s history is never finished.”
—Terri Apter (20th century)
“Throughout the history of commercial life nobody has ever quite liked the commission man. His function is too vague, his presence always seems one too many, his profit looks too easy, and even when you admit that he has a necessary function, you feel that this function is, as it were, a personification of something that in an ethical society would not need to exist. If people could deal with one another honestly, they would not need agents.”
—Raymond Chandler (1888–1959)
“To summarize the contentions of this paper then. Firstly, the phrase ‘the meaning of a word’ is a spurious phrase. Secondly and consequently, a re-examination is needed of phrases like the two which I discuss, ‘being a part of the meaning of’ and ‘having the same meaning.’ On these matters, dogmatists require prodding: although history indeed suggests that it may sometimes be better to let sleeping dogmatists lie.”
—J.L. (John Langshaw)