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.