The Travelling Salesman Problem

The Travelling Salesman Problem is probably the most famous optimisation problem. In essence, the problem is easy. Starting at his home base, a hypothetical travelling salesman has to travel to each city in a list of cities only once and return home. The cities are spread around and have x and y coordinates. It can be thought of that the salesman has one unit of goods to deliver to each city and a variable can be kept, either one or zero, representing the need to deliver to which cities left on the hamiltonian cycle or tour. Once all cities are completed, the tour is completed. The optimisation part of the problem is that one needs to find the shortest distance that the salesman must travel in order to carry out his task.

The Travelling Salesman Problem has been applied to all kinds of optimisation tasks including ones such as vehicle routing or even the sequence of loading jobs on a machine. For example, if some machine has a set of coloured inks in order to perform printing jobs and the specific jobs have timescales and reloading times, then an optimal sequence of job loading can be found with an analogy to the Travelling Salesman Problem.

The Travelling Salesman Problem was first used in the 1920s, when Karl Menger publicised it among his colleagues in Vienna. It reappeared in the 1930s in the mathematical circles of Princeton and was further studied by statisticians Mahalanobis (1940), Jessen (1942), Gosh (1948) and Marks (1948) with regards to an agricultural application. Merill Flood also used it at the RAND Corporation. It became notorious as no other idea was around at the time to study the large number of possible solutions to an optimisation problem and is thought of as an NP complete or NP hard problem. NP hard refers to the fact it cannot be solved in polynomial time or that the time needed to solve the problem grows exponentially per instance. In 1954 George Dantzig, Ray Fulkerson, and Selmer Johnson solved the Travelling Salesman Problem for 42 cities throughout the United States, but as the route passed through an extra seven cities, it could be thought of as solving the Travelling Salesman Problem for 49 cities. This was an unheard of level of success at the time and was a testament to their method.

In 1962 Proctor and Gamble ran a contest to see if anyone could solve the Travelling Salesman Problem for a specified 33 cities. Several people solved the optimal solution including Professor Gerald Thompson of Carnegie Mellon University.

Since this time a number of people have solved the Travelling Salesman Problem including:

  • Groetschel (1977) found the optimal tour of 120 cities from what was then West Germany.
  • Padberg and Rinaldi (1987) found the optimal tour of 532 AT&T switch locations in the USA.
  • Groetschel and Holland (1987) found the optimal tour of 666 interesting places in the world.
  • Padberg and Rinaldi (1987) found the optimal tour through a layout of 2,392 that was obtained from Tektronics Incorporated.
  • Applegate, Bixby, Chvatal, and Cook (1994) found the optimal tour for a 7,397-city Travelling Salesman Problem that arose in a programmable logic array application at AT&T Bell Laboratories.
  • Applegate, Bixby, Chvatal, and Cook (1998) found the optimal tour of the 13,509 cities in the USA with populations greater than 500.
  • Applegate, Bixby, Chvatal, and Cook (2001) found the optimal tour of 15,112 cities in Germany.



Bookmark and Share

Submit a comment about this page












I am available for freelance web design work in the Cambridge, UK area, outside normal working hours. If you are interested, please