1930

1940

1950

1960

1970

1980

1990

1954

This is the granddaddy of TSP papers. It reports on the solution of a 49-city TSP via linear-programming methods. Many of the ideas used to solve integer programming problems can be traced back to this paper.

An 88-page research report containing many basic results on the asymmetric TSP polytope. In the author's words, it is "an assembly of facts and tools, hence, a working paper in the literal sense of the word." (We thank Hernan Abeledo for kindly locating this manuscript for us at George Washington University.)

1955

This manuscript discusses linear systems for the TSP polytope, and some neighbor relations for the asymmetric TSP polytope.

The author announces a complete description of the 5-city asymmetric TSP polytope. (Several corrections are discussed in Kuhn [1991].)

The main portion of the paper discusses a linear programming approach to the TSP, but it also contains several interesting side discussions. In one of these discussions, the authors present their version of 3-opt: "We have developed a method for investigating the change in cost of all three-in, three-out changes which are possible without destroying the circuit." In another discussion, they introduce the capacitated vehicle routing problem. The authors also make several interesting historical remarks. They write that the TSP "may be familiar to statisticians as the `Mean Minimum Distance' problem", and they give several references dating back to 1942. They also write that they began their own study of the TSP independently from the work that was going on in the United States: "we used to call it the laundry van problem, where the conditions were a daily service by a one-van laundry."

The abstract announces complete descriptions of n-city TSP polytopes, for n <= 7. (The system for n = 7 was later shown to be insufficient by Boyd and Cunningham [1991], Fleischmann [1988], and Naddef and Rinaldi [1992].)

The author carries out computational tests of the Dantzig-Fulkerson-Johnson method by hand on 10 instances, each having 9 cities. His report that "the average time to work one of the problems was about 3 hours" is cited as a benchmark for the next few years of computational work on the TSP. He also describes the cheapest-insertion heuristic, giving credit for it to A. W. Boldyreff.

1956

Some heuristic methods for obtaining good tours are discussed, including the nearest-neighbor algorithm and 2-opt. It is very interesting to read the manuscript with knowledge of the results that have come afterwards. For example, the author writes: "It seems very likely that a quite different approach from any yet used may be required for successful treatment of the problem. In fact, there may be no general method for treating the problem and impossibility results would also be valuable."

This is the famous Kruskal's Algorithm for computing minimum-length spanning trees. The author writes that the computation of minimum spanning trees is interesting because that problem "on the surface is closely related to the well-known traveling salesman problem."

1957

The author describes an enumeration scheme for computing near-optimal tours and makes several observations on the structure of optimal tours for geometric problems. A tour for a 10-city instance is solved by hand to demonstrate the practicality of the method for small instances.

1958

A 3-opt algorithm is described, together with an enumeration scheme for computing an optimal tour. The author tests his algorithm on the examples of Robacker and Barachet, as well as on a new 10-city instance. The tests were carried out on an IBM 650 computer. The author notes that the method had an "impracticably slow rate of convergence on Dantizig's 42-city problem." The 42-city instance is derived from the 49-city Dantzig-Fulkerson-Johnson example via a simple reduction. (We thank Jan Karel Lenstra for kindly providing us with a copy of this manuscript.)

A variant of 3-opt is proposed, together with an enumeration scheme for computing an optimal tour. The authored solved the Dantzig-Fulkerson-Johnson 42-city example in 70 hours by hand. He also solved several of the Robacker examples in an average time of 25 minutes per example.

A branch-and-bound algorithm using the assignment problem to obtain lower bounds is described. The branching step chooses a subtour from the solution to the assignment problem, and considers, in turn, setting x_e = 0 for each edge e in the subtour. The algorithm is tested on examples having up to 10 cities.

The authors announce an implicit enumeration algorithm for the TSP. The algorithm was used to solve a 13-city instance by hand.

1959

A step-by-step application of the Dantzig-Fulkerson-Johnson algorithm is given for Barachet's 10-city example. They write: "judging from the number of queries we have received from readers, this method was not elaborated sufficiently to make the proposal clear."

The author announces an algorithm for the TSP. He writes: "The algorithm employs the concept of basic minimal change that can be made to a given route. Successive examination of particular subsets of these minimal changes are found to form the optimum (minimum or maximum) route quickly." The details of the algorithm are not given in the abstract.