Traveling salesman problem Guide, Meaning , Facts, Information and Description
The traveling salesman problem (TSP), also known as the traveling salesperson problem, is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are hard to solve.
| Table of contents |
|
2 Computational complexity 3 Algorithms 4 References 5 Related articles 6 External Links |
Given a number of cities and the costs of travelling from one to the other, what is the cheapest roundtrip route that visits each city and then returns to the starting city?
An equivalent formulation in terms of graph theory is: Find the Hamiltonian cycle with the least weight in a weighted graph.
It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem.
A related problem is the Bottleneck traveling salesman problem (bottleneck TSP): Find the Hamiltonian cycle in a weighted graph with the minimal length of the longest edge.
The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classic example is in printed circuit manufacturing -- scheduling of a route of the drill machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing problem).
The most direct solution would be to try all the combinations and see which one is cheapest, but given that the number of combinations is N! (the factorial of the number of cities), this solution rapidly becomes impractical.
The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see the function problem article), and the decision problem version ("given the costs and a number x, decide whether there is a roundtrip route cheaper than x") is NP-complete.
The bottleneck traveling salesman problem is also NP-hard.
The traditional lines of attack for the NP-hard problems are the following:
Various approximation algorithms, which "quickly" yield "good" solutions with "high" probability, have been devised. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are provably 2-3% away from the optimal solution.
Several categories of heuristics are recognized.
A very natural restriction is the triangle inequality. That is, for any 3 cities A, B and C, the distance between A and C must be at most the distance from A to B plus the distance from B to C. Most natural instances of TSP satisfy this constraint.
In this case, there is an algorithm (due to Christofides, 1975) which always finds a tour of length at most 1.5 times the shortest tour. In the next paragraphs, we explain a weaker (but simpler) algorithm which finds a tour of length at most twice the shortest tour.
The length of the minimum spanning tree of the network is a natural lower bound for the length of the optimal route. In the TSP with triangle inequality case it is possible to prove upper bounds in terms of the minimum spanning tree and design an algorithm that has a provable upper bound on the length of the route. The first published (and the simplest) example follows.
Christofides algorithm follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight perfect matching. This gives a TSP tour which is at most 1.5 times the optimal. It is a long-standing (since 1975) open problem to improve 1.5 to a smaller constant. It is known, however, that there is no polynomial time algorithm that finds a tour of length at most 1+1/219 times the optimal, unless P=NP (Papadimitriou and Vempala, 2000).
Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance. The problem still remains NP-hard, however many heuristics work better.
Euclidean TSP is a particular case of TSP with triangle inequality, since distances in plane obey triangle inequality. However, it seems to be easier than general TSP with triangle inequality. For any c>0, there is a polynomial time algorithm that finds a tour of length at most (1+c) times the optimal on any graph (Arora, 1997). In practice, the running time of this algorithm is too large and heuristics with weaker guarantees are used but they also perform better on instances of Euclidean TSP than on general instances.
This is an Article on Traveling salesman problem. Page Contains Information, Facts Details or Explanation Guide About Traveling salesman problem Problem statement
Computational complexity
Algorithms
For benchmarking of TSP algorithms, TSPLIB a library of sample instances of the TSP and related problems is maintained, see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual printed circuits.Exact algorithms
An exact solution for 15,112 German cities from TSPLIB was found in 2001 using the Cutting-plane method proposed by George Dantzig, Ray Fulkerson, and Selmer Johnson in 1954, based on linear programming. The computations were performed on a network of 110 processors located at Rice University and Princeton University, see the Princeton external link. The total computation time was equivalent to 22.6 years on a single 500 MHz Alpha processor.Heuristics
Constructive heuristics
Iterative improvement
Randomized improvement
TSP is a touchstone for many general heuristics devised for combinatorial optimization: genetic algorithms, simulated annealing, Tabu search, neural nets, ant system.Special cases
Restricted locations
TSP with triangle inequality
It is easy to prove that the last step works. Moreover, thanks to the triangle inequality, each skipping at Step 4 is in fact a shortcut, i.e., the length of the cycle does not increase. Hence it gives us a TSP tour no more than twice as long as the optimal one.Euclidean TSP
Asymmetric TSP
In most cases, the distance between two nodes in the TSP network is the same in both directions - the special case where the distance from A to B is not equal to the distance from B to A is called Asymmetric TSP and has some practical applications.References
Related articles
External Links