History of German TSP Tours

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.