If we imagine a salesman who is planning to travel to a number of different cities to sell his goods, starting out from, and ending at, his home city, we would also imagine that he would select a route which would minimise the distance travelled. Assuming he knows the distance between each pair of cities on his tour, we can state that he has all the data necessary to plan such a route. However, it is certainly not obvious as to how to use this data to plan said route. This is commonly known as the travelling salesman problem (TSP), and it is the most prominent of the NP-complete optimisation problems.
The first mention of the TSP in literature was made in 1832 in a German book entitled “Der Handlungsreisende, wie er sien soll und was er zu thun hat, um Auftrage zu erhalten und eines glucklichen Erfolgs in seinen Geschaften gewiss zu sein. Von einem alten Commis-Voyageur” (“The Travelling Salesman, how he should be and what he should do to get Commissions and to be Successful in his Business”). The last chapter makes the first explicit reference to the TSP: ‘By a proper choice and scheduling of the tour, one can often gain so much time that we have to make some suggestions... The most important aspect is to cover as many locations as possible without visiting a location twice...’ (Voigt, 1831; Muller-Merbach, 1983).
Although it is not certain who brought the TSP into mathematical scrutiny, it is supposed that Merrill Flood is responsible for bringing it into focus having heard about it from A. W. Tucker in 1937. Flood writes that Tucker heard about the TSP from Hassler Whitney at Princeton University. This seems to make Whitney the founder of the mathematical TSP. The study of the problem, at time of writing, seems to have been just over 60 years; there is still no polynomial-time solution.
Flood was urged in 1948 to popularise the TSP at the RAND Corporation, partly motivated by the purpose of creating intellectual challenges for models outside the theory of games.