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.
David Applegate, Robert
Bixby, Va?ek Chvátal,
Back to TSP home.
Last updated: June 1, 2001.
Original located at http://www.math.princeton.edu/tsp/d15sol/dhistory.html