1960

R. Bellman, "Combinatorial processes and dynamic programming", in: Combinatorial Analysis (R. Bellman and M. Hall, Jr., eds.), American Mathematical Society, pp. 217-249.
Bellman uses the TSP as an example of a combinatorial problem that can be solved via dynamic programming. He writes: "It follows that with current machines it would be possible to solve problems of this type in a direct fashion for N <= 17."
M.F. Dacey, "Selection of an initial solution for the traveling-salesman problem", Operations Research 8, 133-134.
The author announces a new heuristic algorithm for the TSP. The details of the algorithm were given in a technical report from the Department of Geography, University of Washington. He reports that on the 10 Robacker instances, the solutions found by the heuristic were on average 4.8 percent longer than the optimal solutions.
F. Lambert, "The traveling-salesman problem", Cahiers du Centre de Recherche Opérationelle 2, 180-191.
A 5-city example of the TSP is solved using Gomory cutting planes.
C.E. Miller, A.W. Tucker, and R.A. Zemlin, "Integer programming formulation of traveling salesman problems", Journal of the Association for Computing Machinery 7, 326-329.
The authors present an integer programming formulation of the TSP and report their computational experience on solving several small problems using Gomory's cutting-plane algorithm. The largest instance solved was the 10-city example of Barachet.
W. Riley, III, "Micro-analysis applied to the travelling salesman problem", Operations Research (Supplement 1) 8, Abstract D4.
This is a continuation of the author's earlier work. The details of his method are not given.

1961

E.L. Arnoff and S.S. Sengupta, "Mathematical programming", in: Progress in Operations Research (R.L. Ackoff, editor), John Wiley and Sons, New York, pp. 105-210.
A good survey of the computational work on the TSP that was carried out in the 1950's.
H. Müuller - Merbach, "Die ermittlung des kürzesten rundreiseweges mittels linear programmierung", Ablauf und Planungsforschung 2, 70-83.
An algorithm for the asymmetric TSP is proposed. It is illustrated on a 7-city example.
B. Thüring, "Zum problem der exakten ermittlung des kürzesten rundreiseweges", Elektronische Datenverarbeitung 3, 147-156.
A TSP algorithm is described and illustrated on a 10-city example.

1962

R. Bellman, "Dynamic programming treatment of the travelling salesman problem", Journal of the Association for Computing Machinery 9, 61-63.
Some additional remarks on dynamic programming algorithms for the TSP are given.
R.H. Gonzales, "Solution to the traveling salesman problem by dynamic programming on the hypercube", Technical Report Number 18, Operations Research Center, Massachusetts Institute of Technology.
The author solved instances with up to 10 cities using dynamic programming. The tests were carried out on an IBM 1620 computer.
M. Held and R.M. Karp, "A dynamic programming approach to sequencing problems", Journal of the Society of Industrial and Applied Mathematics 10, 196-210.
Dynamic programming algorithm are described for solving small instances and for finding approximate solutions to larger instances. The exact algorithm was used to solve 13-city instances on an IBM 7090 computer. The approximation algorithm (also programmed for the IBM 7090) found the optimal solution to the 42-city Dantzig-Fulkerson-Johnson example on two out of five trials, and was also tested on a new 48-city instance.

1963

F. Bock, "Mathematical programming solution of traveling salesman examples", in: Recent Advances in Mathematical Programming (R.L. graves and P. Wolfe, eds.), McGraw-Hill, New York.
The author gives a sketch of a linear-programming based algorithm for the TSP. The paper contains the now well-known 1930 quote from Karl Menger describing the Hamiltonian path problem.
J.D.C. Little, K.G. Murty, D.W. Sweeney, and C. Karel, "An algorithm for the traveling salesman problem", Operations Research 11, 972-989.
The authors coin the term branch-and-bound: "The subsets of tours are conveniently represented as the nodes of a tree and the process of partitioning as a branching of the tree. Hence we have called the method `branch-and-bound'." They use a combinatorial bounding method in their algorithm, and they branch on edges being either in or not in the tour. Their algorithm was implemented on an IBM 7090 computer. Some interesting computational tests are given, including the solution of a 25-city problem that was contained in the Held and Karp test set. Their most cited success is the solution of a set of 30-city asymmetric problems having random edge lengths. They also report that 10-city instances can be solved in under 1 hour by hand.
V.I. Mudrov, "A method of solution of the traveling salesman problem by means of integer linear programming (the problem of finding the Hamiltonian paths of shortest length in a complete graph)" (in Russian), Zhurnal Vychislennoi Fiziki (USSR) 3, 1137-1139. (Abstract in: International Abstracts in Operations Research 5 (1965), Abstract Number 3330.)
This is a review of an paper written in Russian. The paper contains an integer programming formulation of the TSP. The author proposes to use this formulation together with Gomory's cutting-plane algorithm to solve TSP instances.

1964

R.L. Karg and G.L. Thompson, "A heuristic approach to solving travelling salesman problems", Management Science 10, 225-248.
The cheapest-insertion heuristic is described, together with a proposal for using it to improve subsections of tours. The authors employ their heuristic methods on several large instances, including a 57-city instance with data taken from a road atlas.
W. Suurballe, "Network algorithm for the traveling salesman problem", Operations Research (Supplement 1) 12, Abstract 3Tc.1.
The author announces a enumeration algorithm for computing all optimal tours to TSP instances.

1965

S. Lin, "Computer solutions of the traveling salesman problem", The Bell System Technical Journal, 2245-2269.
This is an important paper in heuristic methods for the TSP. The author defines k-optimal tours, and gives an efficient way to implement 3-opt (extending the work of Croes). Computational results are given for instances with up to 105 cities. The paper also includes a discussion about the probability of obtaining optimal tours via repeated trials of the heuristic.
S. Reiter and G. Sherman, "Discrete optimizing", SIAM Journal on Applied Mathematics 13, 864-889.
A local-search algorithm for the TSP is proposed and tested on problems from the literature. The largest instance considered is the 57-city example of Karg and Thompson. In each case, the algorithm was able to produce a tour at least as good as the tours that were reported in earlier papers.
N.P. Salz, "The NORMA: a possible basis for a theory for the traveling-salesman problem", Operations Research (Supplement 1) 13, Abstract C4h.
A framework for studying the TSP is proposed.

1966

R.E. Gomory, "The traveling salesman problem", in: Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, IBM, White Plains, pp. 93-121.
Gomory's paper includes very nice descriptions of the methods of Dantzig, Fulkerson, and Johnson [1954], Held and Karp [1962], and Little, Murty, Sweeney, and Karel [1963]. The paper also includes the text of a beautiful discussion between Gomory, J. Edmonds, and H.W. Kuhn, concerning the use of linear programming methods to solve combinatorial problems.
E.L. Lawler and D.E. Wood, "Branch-and-bound methods: a survey", Operations Research 14, 699-719.
The paper includes descriptions of the branch-and-bound algorithms of Eastman [1958] and Little, Murty, Sweeney, and Karel [1963]. The authors suggest the use of minimum spanning trees as a lower bound in a branch-and-bound algorithm for the TSP.
G.T. Martin, "Solving the traveling salesman problem by integer linear programming", Operations Research (Supplement 1) 14, Abstract WA7.10.
The author outlines a cutting-plane algorithm for the TSP. The algorithm adds both TSP-specific inequalities (their form is not mentioned in the text, but from the context it would seem that they are subtour inequalities) as well as cutting planes from Gomory's method of integer forms. The Dantzig-Fulkerson-Johnson problem was solved using 9 TSP cuts and 10 Gomory cuts. The author writes: "Advanced programming may well reduce both final model size and number of iterations significantly, but several present-day computers solve such problems in five to ten minutes."
G.T. Martin, "Solving the traveling salesman problem by integer linear programming", C-E-I-R, New York, 1966.
This is a full version of the work announced in the above abstract.   We thank John Tomlin for kindly providing us with a copy of this paper.
H. Mueller-Merbach, "Drei neue methoden zur lösung des travelling salesman problems, teil 1", Ablauf und Planungsforschung 7, 32-46.
The author describes some enumerative methods for the TSP.
H. Mueller-Merbach, "Drei neue methoden zur lösung des travelling salesman problems, teil 2", Ablauf und Planungsforschung 7, 78-91.
Continuation of the above paper.
S.M. Roberts and B. Flores, "An engineering approach to the traveling salesman problem", Management Science 13, 269-288.
The authors present an enumerative heuristic for the TSP. Using this algorithm they obtained a tour for Karg and Thompson's 57-city example, having cost equal to the best tour found by Karg and Thompson.
N.P. Salz, "The NORMA: a theory for the traveling salesman problem", Operations Research (Supplement 2) 14, Abstract MP3.11.
Some additional results on the author's framework for studying the TSP.
D. Shapiro, "Algorithms for the solution of the optimal cost traveling salesman problem", Sc.D. Thesis, Washington University, St. Louis.
The authors describes an algorithm similar to Eastman's branch-and-bound algorithm, but with some additional ideas to improve the performance on symmetric instances.

1967

B. Fleischmann, "Computational experience with the algorithm of Balas", Operations Research 15, 153-154.
This paper includes computational results for 6-city and 7-city instances of the TSP.

1968

M. Bellmore and G.L. Nemhauser, "The traveling salesman problem: a survey", Operations Research 16, 538-558.
The authors present an extensive survey of algorithms for the TSP. They write: "If the authors were faced with the problem of finding a solution to a particular traveling salesman problem we would use dynamic programming for problems with 13 cities or less, Shapiro's branch-and-bound algorithm for larger problems (up to about 70-100 cities for asymmetric problems and up to about 40 cities for symmetric problems) and Shen Lin's `3-opt' algorithm for problems that cannot be handled by Shapiro's algorithm."
P. Pfluger, "Diskussion der modellwahl am beispiel des traveling-salesman problems", in: Einführung in die Methode Branch and Bound (M. Bechmann and H.P. Künzi, eds.), Lecture Notes in Operations Research and Mathematical Economics 4, Springer, Berlin, pp. 88-106.
The author gives a short description of the TSP algorithms of Bellman [1962], Held and Karp [1962], Eastman [1958], and Little, Murty, Sweeney, and Karel [1963].

1969

A.M. Issac and E. Turban, "Some comments on the traveling salesman problem", Operations Research 17, 543-546.
This paper contains a short survey of some TSP heuristic methods that were not covered in Bellmore and Nemhauser [1968].
T.C. Raymond, "Heuristic algorithm for the traveling-salesman problem", IBM Journal of Research and Development 13, 400-407.
This author develops some extensions to Karg and Thompson's heuristic for the TSP. Computational results are reported for instances having up to 57 cities.