1954

G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a large-scale traveling-salesman problem", Operations Research 2, 393-410.
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.
I. Heller, "The travelling salesman's problem: part 1 -- basic facts", Research Report, George Washington University Logistics Reserch Project.
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

I. Heller, "On the travelling salesman's problem", Proceedings of the Second Symposium in Linear Programming (Volume 1), Washington, D.C., January 27-29.
This manuscript discusses linear systems for the TSP polytope, and some neighbor relations for the asymmetric TSP polytope.
H.W. Kuhn, "On certain convex polyhedra", Abstract 799t, Bulletin of the American Mathematical Society 61, 557-558.
The author announces a complete description of the 5-city asymmetric TSP polytope. (Several corrections are discussed in Kuhn [1991].)
G. Morton and A.H. Land, "A contribution to the `travelling-salesman' problem", Journal of the Royal Statistical Society, Series B 17, 185-194.
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."
R.Z. Norman, "On the convex polyhedra of the symmetric traveling salesman problem", Abstract 804t, Bulletin of the American Mathematical Society 61, 559-559.
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].)
J.T. Robacker, "Some experiments on the traveling-salesman problem", RAND Research Memorandum RM-1521.
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

M.M. Flood, "The traveling-salesman problem", Operations Research 4, 61-75.
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."
J.B. Kruskal, "On the shortest spanning subtree of a graph and the traveling salesman problem", Proceedings of the American Mathematical Society 2, 48-50.
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

L.L. Barachet, "Graphic solution of the traveling-salesman problem", Operations Research 5, 841-845.
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

F. Bock, "An algorithm for solving `traveling-salesman' and related network optimization problems", Research Report, Armour Research Foundation. (Presented at the Operations Research Society of America Fourteenth National Meeting, St. Louis, October 24, 1958.) PDF file.
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.)
G.A. Croes, "A method for solving traveling-salesman problems", Operations Research 6, 791-812.
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.
W.L. Eastman, "Linear programming with pattern constraints", Ph.D. Dissertation, Harvard.
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 xe = 0 for each edge e in the subtour. The algorithm is tested on examples having up to 10 cities.
M.J. Rossman and R.J. Twery, "A solution to the travelling salesman problem", Operations Research 6, page 687, Abstract E3.1.3.
The authors announce an implicit enumeration algorithm for the TSP. The algorithm was used to solve a 13-city instance by hand.

1959

G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson, "On a linear-programming, combinatorial approach to the traveling-salesman problem", Operations Research 7, 59-66.
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."
W. Riley, III, "A new approach to the traveling-salesman problem", Operations Research (Supplement 1) 7, Abstract B4.
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.