The earliest known reference to the traveling salesman problem is contained in the manual  Der Handlungsreisende - wie er sein soll und was er zu thun hat, um Auftraege zu erhalten und eines gluecklichen Erfolgs in seinen Geschaeften gewiss zu sein - Von einem alten Commis-Voyageur, published in 1832.   This manual was cited by H. Mueller-Merbach, in DGOR Bulletin 25, 1983; the manual does not contain a mathematical treatment of the TSP, but it does give a precise description of the problem.    In A. Schrijver's beautiful paper "On the history of combinatorial optimization (till 1960)",  the following example of a 45-city TSP from the alten Commis-Voyageur manual is presented.