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.
|