Travelling Salesman Problem
The Travelling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science. It is focused on optimisation. In this context better solution often means a solution that is cheaper. TSP is a mathematical problem. It is most easily expressed as a graph describing the locations of a set of nodes.
The travelling salesman problem was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman. Hamilton’s Icosian Game was a recreational puzzle based on finding a Hamiltonian cycle. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger. Menger defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic:
We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for ﬁnitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.
Stating the problem[change | change source]
The Travelling Salesman Problem describes a salesman who must travel between N cities. The order in which he does so is something he does not care about, as long as he visits each one during his trip, and finishes where he was at first. Each city is connected to other close by cities, or nodes, by airplanes, or by road or railway. Each of those links between the cities has one or more weights (or the cost) attached. The cost describes how "difficult" it is to traverse this edge on the graph, and may be given, for example, by the cost of an airplane ticket or train ticket, or perhaps by the length of the edge, or time required to complete the traversal. The salesman wants to keep both the travel costs, as well as the distance he travels as low as possible.
The Traveling Salesman Problem is typical of a large class of "hard" optimization problems that have intrigued mathematicians and computer scientists for years. Most important, it has applications in science and engineering. For example, in the manufacture of a circuit board, it is important to determine the best order in which a laser will drill thousands of holes. An efficient solution to this problem reduces production costs for the manufacturer.
Difficulty[change | change source]
The travelling salesman problem is regarded as difficult to solve. If there is a way to break this problem into smaller component problems, the components will be at least as complex as the original one. This is what computer scientists call NP-hard problems.
Many people have studied this problem. The easiest (and most expensive solution) is to simply try all possibilities. The problem with this is that for N cities you have (N-1) factorial possibilities. This means that for only 10 cities there are over 360 thousand combinations to try (9*8*7...etc.).
- Exact solutions to the problem can be found, using branch and bound algorithms. This is currently possible for about 40-60 cities
- heuristics approaches use a set of guiding rules for selection of the next node. But since heuristics result in approximations, they will not always give the optimal solution, although high quality admissible heuristics can find a useful solution in a fraction of the time required for a full brute force of the problem. An example of a heuristic for a node would be a summation of how many unvisited nodes are "close by" a connected node. This could encourage the salesman to visit a group of close-by nodes clustered together before moving onto another natural cluster in the graph. See Monte Carlo algorithms and Las Vegas algorithms
Other websites[change | change source]
- TSP page
- Example of finding approximate solution of TSP problem using a genetic algorithm
- A Java implementation of a TSP-solution using JGAP (Java Genetic Algorithms Package). The technique used is a Genetic Algorithm.
- Solution of the Travelling Salesman Problem using a Kohonen Map
- Solution of the Travelling Salesman Problem using a Kohonen Map (in 3-dimensions!)
- The Travelling Salesman Problem Talks about the use of simulated annealing to solve this problem and allows download of a DOS/Windows command-line program demonstrating problem solution.
- Most TSP loop families grow polynomially Private web page shows that a method exists for obtaining a set of optimal "travelling salesman" routes that is a member of a family that grows no faster than about 2nIn2. However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.
- VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
- TSP solver with BING Maps solves TSP and TSPTW.
- TSP Software - Free software for finding approximate solutions to various TSP problem instances with many different approximation algorithms.
References[change | change source]
- A discussion of the early work of Hamilton and Kirkman can be found in Graph Theory 1736–1936
- Cited and English translation in Schrijver (2005). Original German: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."
- A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in Alexander Schrijver's 2005 paper "On the history of combinatorial optimization (till 1960). Handbook of Discrete Optimization (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, 2005, pp. 1–68.PS,PDF