by Nigel Cummings
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 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), 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 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, 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.
The 1950s saw an increasing use of computers in solving such problems. 1958 saw F. Bocks , "An algorithm for solving travelling-salesman and related network optimisation problems", this paper was presented at the Operations Research Society of America, Fourteenth National Meeting, St. Louis, October 24, 1958. It described a 3-opt algorithm and an enumeration scheme for computing an optimal tour. The algorithm was tested on the examples of Robacker and Barachet, as well as on a new 10-city problem. All the tests were carried out on an IBM 650 computer.
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.
At the beginning of the 1960s, R. Bellman published "Combinatorial processes and dynamic programming". In this Bellman (no stranger to computers ) used the TSP as an example of a combinatorial problem that can be solved via dynamic programming. He wrote: "It follows that with current machines it would be possible to solve problems of this type in a direct fashion for ."
<p">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.
Leaping forward to the 1970s R.M. Karp and M. Held published "The travelling-salesman problem and minimum spanning trees", a paper which introduced the 1-tree relaxation of the TSP and the idea of using node weights to improve the bound given by the optimal 1-tree. Part II was published in 1971, and detailed An iterative method for computing a good 1-tree bound (using node weights). The authors embedded this method in a branch-and-bound algorithm and solved, amongst others, the 42-city instance of Dantzig, Fulkerson, and Johnson (1954), the 57-city instance of Karg and Thompson (1964), and a 64-city random Euclidean instance.
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."
It will be interesting to see what further papers result from the TSP problem now we are inhabiting the 21st century.
First published to members of the Operational Research Society in Inside OR June 2000
