top tsp

German Cities in the TSP

The cities of Germany play a big 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.

Three German Tours

David Applegate, Robert Bixby, Va?ek Chvátal, William Cook
Back to TSP home.

Last updated:  June  1, 2001.
Original located at
Contact:  bico@math.princeton.eduThe TSP Home pageTSP ApplicationsTSP History PageSolution of 15,112-city TSP