Traveling salesman problem
|
|
The traveling salesman problem or travelling 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.
| Contents |
Problem statement
Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city once and then returns to the starting city?
An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find the Hamiltonian cycle with the least weight.
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).
Computational complexity
The most direct solution would be to try all the permutations (ordered combinations) and see which one is cheapest (using brute force), but given that the number of permutations is n! (the factorial of the number of cities, n), this solution rapidly becomes impractical.
Using the techniques of dynamic programming, one can solve the problem exactly in time <math>O(n^22^n)<math>. Although this is exponential, it is still much better than n! time.
NP-hardness
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 problem remains NP-hard even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases.
Removing the condition of visiting each city "only once" does not remove the NP-hardness, since it is easily seen that in the planar case an optimal tour visits cities only once (otherwise, by the triangle inequality, a shortcut that skips a repeated visit will decrease the tour length).
Algorithms
The traditional lines of attack for the NP-hard problems are the following:
- Devising algorithms for finding exact solutions (they will work reasonably fast only for relatively small problem sizes).
- Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver either seemingly or provably good solutions, but which could not be proved to be optimal.
- Finding special cases for the problem ("subproblems") for which either exact or better heuristics are possible.
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
- Various branch-and-bound algorithms, which can be used to process TSPs containing 40-60 cities.
- Progressive improvement algorithms which use techniques reminiscent of linear programming. Works well for up to 120-200 cities.
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. In May 2004, the traveling salesman problem of visiting all 24,978 cities in Sweden was solved: a tour of length approximately 72,500 kilometers was found and it was proven that no shorter tour exists.
Heuristics
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.
Constructive heuristics
- The nearest neighbor algorithm, which is normally fairly close to the optimal route, and does not take too long to execute. Unfortunately, it is provably reliable only for special cases of the TSP. In the general case, there exists an example for which the nearest neighbor algorithm gives the worst possible route.
Iterative improvement
- Pairwise exchange, or Kernighan-Lin heuristics.
- k-opt heuristic: Take a given tour and delete k mutually disjoint edges. Reassemble the remaining fragments into a tour, leaving no disjoint subtours (that is, don't connect a fragment's endpoints together). This in effect simplifies the TSP under consideration into a much simpler problem. Each fragment endpoint can be connected to 2k − 2 other possibilities: of 2k total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such a constrained 2k-city TSP can then be solved with brute force methods to find the least-cost recombination of the original fragments.
Randomized improvement
- Optimized Markov chain algorithms which utilize local searching heuristic sub-algorithms can find a route extremely close to the optimal route for 700-800 cities.
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
- A trivial special case is when all cities are located on the perimeter of a convex polygon.
- A good exercise in combinatorial algorithms is to solve the TSP for a set of cities located along two concentric circles.
TSP with triangle inequality
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.
- Step 1: Construct the minimal spanning tree.
- Step 2: Duplicate all its edges. This gives us an Eulerian graph.
- Step 3: Find an Eulerian cycle in it. Clearly, its length is twice the length of the tree.
- Step 4: Convert the Eulerian cycle into the Hamiltonian one in the following way: walk along the Eulerian cycle, and each time you are about to come into an already visited vertex, skip it and try to go to the next one (along the Eulerian cycle).
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.
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/219 more than optimal, unless P = NP (Papadimitriou and Vempala, 2000).
Euclidean TSP
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.
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. An example of a practical application of an asymmetric TSP is route optimization using street-level routing (asymmetric due to one-way streets, slip-roads and motorways).
References
- G. B. Dantzig, R. Fulkerson, and S. M. Johnson, Solution of a large-scale traveling salesman problem, Operations Research 2 (1954), 393-410.
- S. Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. Journal of ACM, 45(1998), 753-782.
- N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
- C. H. Papadimitriou, S. Vempala: On the approximability of the traveling salesman problem (extended abstract). Proceedings of STOC'2000, 126-133.
- D. S. Johnson and L. A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization, Local Search in Combinatorial Optimization, E. H. L. Aarts and J.K. Lenstra (ed), John Wiley and Sons Ltd, 1997, pp 215-310.
Related articles
External links
- TSPLIB (http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/)
- TSP page (http://www.tsp.gatech.edu/index.html)
- Private web page with 2 algorithms & demo program to download (http://www.pcug.org.au/~dakin/tsp.htm)
- Example of finding approximate solution of TSP problem using a (http://cs.felk.cvut.cz/~xobitko/ga/tspexample.html) genetic algorithm
- Solution of the Traveling Salesman Problem using a Kohonen Map (http://www.vias.org/simulations/simusoft_travsalm.html)
- Java Applet that solves the traveling salesman problem (http://pcbunn.cacr.caltech.edu/Java/Genetic.html)cs:Problém obchodního cestujícího
de:Problem des Handlungsreisenden he:בעיית הסוכן הנוסע ja:巡回セールスマン問題 lt:Keliaujančio pirklio udavinys nl:Handelsreizigersprobleem pl:Problem_komiwojażera ru:Задача коммивояжёра