|
|
 |
| TSP Annotated Bibliography |
 |
|
1940
P. C. Mahalanobis, "A sample survey of the acreage under jute in
Bengal", Sankhyu 4, 511-530.
The well-known statistician Mahalanobis discusses
some aspects of TSP solutions through randomly chosen locations in the
Euclidean plane. This work was in connection with a survey
of farm lands in Bengal that took place in 1938, where one of the major
costs in carrying out the survey was the transportation of men and equipment
from one survey point to the next. This work appears to independent
of the Merill Flood led efforts on TSP applications that took place several
years earlier.
1942
R. J. Jessen, "Statistical investigation of a sample survey for obtaining
farm facts", Research Bulletin #304, Iowa State College of
Agriculture.
The title suggests that this report deals with
a problem similar to the application studied by Mahalanobis.
If this is the case, there may be a case for referring to the TSP as the
"traveling farmer's problem." We were not able to obtain a
copy of this paper. We would certainly appreciate receiving
any information on how we could locate this historically interesting paper.
1949
J.B. Robinson, "On the Hamiltonian game (a traveling-salesman problem)",
RAND
Research Memorandum RM-303.
This paper is the earliest reference we could
find that uses the term "traveling salesman problem" in the context of mathematical
optimization. The introduction to the paper, however, makes it clear that
the TSP was already a well-known problem at that time (at least at the
RAND Corporation). The paper contains an algorithm for solving a variation
of the assignment problem (given a complete directed graph, with weights
on the arcs, find a minimum-weight set of disjoint directed circuits that
cover the nodes of the graph) is described. The author writes that she
was led to the solution of the problem in an unsuccessful attempt to solve
the TSP. In the introduction to the paper, the TSP is described as follows:
"One formulation is to find the shortest route for a salesman starting
from Washington, visiting all the state capitals and then returning to
Washington." It is interesting to note that this is the instance that was
solved several years later by Dantzig, Fulkerson, and Johnson.
|
|
|
