The cities of Germany play an important role in the history of the TSP. 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)", an example of a 45-city TSP from the alten Commis-Voyageur manual is presented.
German cities appear again in Martin Groetschel's record TSP solution of a 120-city instance in 1977. His solution is presented in Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme, Mathematical Systems in Economics 36, 1977 and also in "On the symmetric travelling salesman problem: solution of a 120-city problem", Mathematical Programming Study 12, 1980. Groetschel's problem was formulated by taking the 120 cities that were listed in a distance table in the Deutscher General Atlas (1967/68). The 120 cities include two cities in Switzerland (Basel and Schaffhausen) and one city in Austria (Salzburg), with the remainder in Germany. An interesting point is that Groetschel's problem contains a German city that is not included in the 15,112-city instance, namely the city of Puttgarden on the island of Fehmarn in the north of Germany.
In the following figure we present the three German tours. The Alten Commis-Voyageur tour is given in green, Groetschel's tour in blue, and the 15,112-city tour in red.