1930

1940

1950

1960

1970

1980

1990

1960

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."

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.

A 5-city example of the TSP is solved using Gomory cutting planes.

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.

This is a continuation of the author's earlier work. The details of his method are not given.

1961

A good survey of the computational work on the TSP that was carried out in the 1950's.

An algorithm for the asymmetric TSP is proposed. It is illustrated on a 7-city example.

A TSP algorithm is described and illustrated on a 10-city example.

1962

Some additional remarks on dynamic programming algorithms for the TSP are given.

The author solved instances with up to 10 cities using dynamic programming. The tests were carried out on an IBM 1620 computer.

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

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.

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.

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

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.

The author announces a enumeration algorithm for computing all optimal tours to TSP instances.

1965

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.

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.

A framework for studying the TSP is proposed.

1966

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.

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.

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."

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.

The author describes some enumerative methods for the TSP.

Continuation of the above paper.

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.

Some additional results on the author's framework for studying the TSP.

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

This paper includes computational results for 6-city and 7-city instances of the TSP.

1968

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."

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

This paper contains a short survey of some TSP heuristic methods that were not covered in Bellmore and Nemhauser [1968].

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.