Travelling salesman problem

The Traveling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science and operations research. It is focused on optimization. In this context, a better solution often means a solution that is cheaper, shorter, or faster. TSP is a mathematical problem. It is most easily expressed as a graph describing the locations of a set of nodes.


Stating the problem
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 once 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 and 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
In general, the traveling salesman problem is hard 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 180 thousand combinations to try (since the start city is defined, there can be permutations on the remaining nine). We only count half since each route has an equal route in reverse with the same length or cost.
9! / 2 = 181 440
 Exact solutions to the problem can be found, using branch and bound algorithms.. How to cut unfruitful branches using reduced rows and columns as in Hungarian matrix algorithm This is currently possible for up to 85,900 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 
 TSPLIB 

References

Category:Theoretical computer science
Category:Combinatorial optimization