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.