In the April 2000 issue of this Newsletter I produced an article about the application of insect behavioural patterns to common OR problems. In particular I wrote about Marco Dorigo and his team at the Free University of Brussels, and their work with ant-like agents applied in that instance to the travelling salesman problem (TSP).

At this time it occurred to me that the majority of OR oriented minds had been presented with the TSP or variations of, for a very considerable time. TSP is a problem which is both short and easy to state: given a finite number of cities along with the cost of travel between each pair of them, and with the object of finding the cheapest way of visiting all the cities and returning the original point of departure. (The travel costs are symmetric from the point of view that travelling from city X to city Y costs just as much as travelling from Y to X - the manner of visiting all the cities is simply the order in which the cities are visited.)

I began to wonder when the original TSP had surfaced? Who thought of it? Was
it called the Travelling Salesman Problem? Who produced the first solutions?
During a period of research which I expected to be brief, I came across increasing
numbers of references to the solution of the TSP and TSP like problems. I was
surprised to learn that the mathematician and economist Karl Menger, perhaps
best know for his interests in hyperbolic, probabilistic geometry, and the
algebra of functions had publicised TSP among his colleagues in Vienna in the
1920s. It seemed then, that the TSP has spanned at least 9 decades! In 1932
Menger published "Das botenproblem", in *Ergebnisse eines Mathematischen Kolloquiums *(This volume contains a statement of a problem posed by Karl Menger on February 5, 1930, at a mathematical colloquium in Vienna)

Menger *(pictured left and above)* called it the "Messenger Problem" a
problem encountered by postal messengers, as well as by many travellers he
went on to define the problem as: "the task of finding, for a finite
number of points whose pairwise distances are known, the shortest path connecting
the points The rule, that one should first go from the starting point to the
point nearest this, etc., does not in general result in the shortest path."

In the 1940s the TSP was studied by statisticians: Mahalanobis (in 1940 -
*pictured right*), Jessen (in 1942), Gosh (in 1948), and Marks (in 1948)) in
connection with an agricultural application. P. C. Mahalanobis's, "A
sample survey of the acreage under jute in Bengal" discussed 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.

The mathematician Merill M. Flood made the TSP popular among his colleagues at the RAND Corporation. Over the years the problem gained notoriety as the prototype of a hard problem in combinatorial optimisation - examining the tours one by one is difficult because of their large number.

TSP data consists of integer weights assigned to the edges of a finite complete graph; the objective is to find a hamiltonian cycle (that is, a cycle passing through all the vertices) of the minimum total weight. In this context, hamiltonian cycles are commonly called *tours.*

Julia Robinson *(pictured left)* is most famous for her work with Hilberts tenth
problem, which asked for a procedure for deciding if a Diophantine equation
had a solution in integers also [published a paper concerning the TSP. Published
in 1949 the paper entitled "On the Hamiltonian Game" provided a method
for solving a problem related to the TSP. Although the problem was well known
at that time, there does not appear to be any earlier reference in the literature.

During the 1950s a number of solutions appeared from the likes of George B.
Dantzig *(pictured right)*, Fulkerson, and Johnson (1954). Their approach remains
the only known tool for solving nontrivial TSP instances with more than several
hundred cities; over the years, it has evolved further through the work of
M.Grtschel, S. Hong, M. Jnger, P. Miliotis, D. Naddef, M. Padberg, W.R. Pulleyblank,
G. Reinelt, and G. Rinaldi. *(George B. Dantzig is generally regarded as
one of the three founders of linear programming, along with von Neumann and
Kantorovich.)*

In 1954 I. Heller published an 88-page report containing many basic results on the asymmetric TSP polytope. Heller described this work as "an assembly of facts and tools, hence, a working paper in the literal sense of the word."

A year later (1955) G. Morton and A.H. Land provided additional solutions, though interestingly they wrote that they originally called the TSP, the laundry van problem. The paper mainly concerns the use of linear programming for solving the TSP but there are several interesting side topics such as the authors use of 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." They also said that, "the TSP may be familiar to statisticians as the `Mean Minimum Distance' problem", and they give several references dating back to 1942. (G. Morton and A.H. Land, "A contribution to the `travelling-salesman' problem", *Journal of the Royal Statistical Society, Series B* **17, **185-194.)

In 1956 Merill M. Flood published "The travelling-salesman problem", *Operations Research* **4, **61-75. In which he described some heuristic methods for obtaining good tours, including the nearest-neighbour algorithm and 2-opt.

In 1957 L.L. Barachet published, "Graphic solution of the travelling-salesman problem", (*Operations Research* **5, **841-845.) This paper described an enumeration scheme for computing near-optimal tours and made observations on the structure of optimal tours for geometric problems. The paper also detailed a tour for a 10-city instance which was solved by hand to demonstrate the practicality of the method for small instances.

In 1959 George.B. Dantzig, D.R. Fulkerson, and S.M. Johnson published "On a linear-programming, combinatorial approach to the travelling-salesman problem", *Operations Research ***7, **59-66. This provided a step-by-step application of the Dantzig-Fulkerson-Johnson for a ten city example.

Around this time M. F. Dacey announced 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. Dacey noted that when the heuristic was applied to 10 Robacker instances, the solutions found were on average 4.8 percent longer than the optimal solutions.

1963 saw the publication of a paper jointly by J.D.C. Little, K.G. Murty, D.W. Sweeney, and C. Karel, entitled "An algorithm for the travelling salesman problem", the authors coined the term Branch and Bound, and proceeded to illustrate a combinatorial bounding method in their algorithm, and they regarded branch on edges being either in or not in the tour. Their algorithm was implemented on an IBM 7090 computer.

In 1964 heuristics were applied to a 57 city problem among others by R.L. Karg and G.L. Thompson, their method was described in "A heuristic approach to solving travelling salesman problems", (*Management Science* **10, **225-248.) The following year Shen Lin published a paper which detailed a heuristic solution for up to 105 cities.

In 1974 further improvements to the Held-Karp algorithm for the symmetric travelling-salesman problem were announced by K. Helbig Hansen and J. Krarup, who tested their version of Held-Karp on the 57-city instance of Karg and Thompson (1964) and a set of instances having random edge lengths. In 1976 P. Miliotis applied integer programming to the TSP and implemented a branch-and-cut algorithm using subtour inequalities.

1977 saw M. Grtschel's thesis which contained much of the polyhedral work on the TSP that he carried out jointly with M. Padberg. It also provided the solution for a 120-city instance by means of a cutting-plane algorithm, where cuts (subtour inequalities and comb inequalities) were detected and added by hand to the linear programming relaxation. From that time onward, further work in cutting planes methods was carried out by the likes of: P. Miliotis, "Using cutting planes to solve the symmetric travelling salesman problem", *Mathematical Programming* **15**, 177-188. And M.W. Padberg and S. Hong, "On the symmetric travelling salesman problem: a computational study", *Mathematical Programming Study* **12, **78-107. As recently as 1991 M. Grtschel collaborated with O. Holland on, "Solution of large-scale symmetric travelling salesman problems."