FACTOID # 17: Though Rhode Island is the smallest state in total area, it has the longest official name: The State of Rhode Island and Providence Plantations.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Traveling salesman problem

The traveling salesman problem (TSP), 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. Discrete optimization is a branch of optimization in applied mathematics and computer science. ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ... In computer science, computational complexity theory is the branch of the theory of computation that studies the resources required during computation to solve a given problem. ...

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. A diagram of a graph with 6 vertices and 7 edges. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ... In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. ...


It can be shown that the requirement of returning to the starting city does not change the computational complexity of the problem. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given 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 Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. ... In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ... This article just presents the basic definitions. ...


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). Close-up photo of one side of a motherboard PCB, showing conductive traces, vias and solder points for through-hole components on the opposite side. ...


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. // Mathematics In mathematics, especially in abstract algebra and related areas, a permutation is a bijection from a finite set X onto itself. ... In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ... In mathematics, the factorial of a natural number n is the product of all positive integers less than and equal to n. ...


Using the techniques of dynamic programming, one can solve the problem exactly in time O(n22n). Although this is exponential, it is still much better than O(n!). See Big O notation. In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ... Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...


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. In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...


The bottleneck traveling salesman problem is also NP-hard. The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. ...


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. In mathematics the Euclidean distance or Euclidean metric is the ordinary distance between the two points that one would measure with a ruler, which can be proven by repeated application of the Pythagorean theorem. ...


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). In mathematics, the triangle inequality states that the distance from A to B to C is never shorter than going directly from A to C. The triangle inequality is a theorem in spaces such as the real numbers, Euclidean space, Lp spaces (p ≥ 1) and in all inner product spaces...


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 probably 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. In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ... Close-up photo of one side of a motherboard PCB, showing conductive traces, vias and solder points for through-hole components on the opposite side. ...


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.
  • Recent Implementations of Branch and bound and Cut based on linear programming works very well for up to 5,000 cities, and this approach has been used to solve instances with up to 33,810 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. Branch and bound is a general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... The cutting-plane method by Gomory is a procedure used to find integer solutions of a linear program. ... George Bernard Dantzig (8 November 1914 – 13 May 2005) was a mathematician who introduced the simplex algorithm and is considered the Father of linear programming. He was the recipient of many honors, including the National Medal of Science in 1975, the John von Neumann Theory Prize in 1974. ... 1954 (MCMLIV) was a common year starting on Friday of the Gregorian calendar. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... Rice University Rice University William Marsh Rice University, commonly called Rice University and opened in 1912 as Rice Institute, is one of the nations top teaching and research universities. ... Princeton University, located in Princeton, New Jersey, is the fifth-oldest institution of higher education in the United States. ... DEC Alpha AXP 21064 Microprocessor The DEC Alpha, also known as the Alpha AXP, is a 64-bit RISC microprocessor originally developed and fabricated by Digital Equipment Corp. ...


In March 2005, the traveling salesman problem of visiting all 33,810 points in a circuit board was solved using CONCORDE: a tour of length 66,048,945 units was found and it was proven that no shorter tour exists, the computation took approximately 15.7 CPU years.


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 with a high probability just 2-3% away from the optimal solution. In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...


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. In practice, this heuristic provides solutions which are in average 10 to 15 percent above the optimal.

The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the traveling salesman problem, and usually comes to within twenty percent of the optimal 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. In mathematics, a (discrete-time) Markov chain, named after Andrei Markov, is a discrete-time stochastic process with the Markov property. ... A genetic algorithm (GA) is a search technique used in computer science to find approximate solutions to optimization and search problems. ... Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ... Tabu search is a mathematical optimization method, belonging to the class of local search techniques. ... A neural network is an interconnected group of neurons. ... The ant colony optimization algorithm (ACO), introduced by Marco Dorigo in his doctoral thesis, is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ...


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.

Triangle inequality and the Christofides algorithm

A very natural restriction of the TSP 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 mathematics, the triangle inequality states that the distance from A to B to C is never shorter than going directly from A to C. The triangle inequality is a theorem in spaces such as the real numbers, Euclidean space, Lp spaces (p ≥ 1) and in all inner product spaces...


In this case, there is a constant-factor approximation 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. In complexity theory the class APX (an abbreviation of approximable) is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short). ...


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. The minimum spanning tree of a planar graph. ... In mathematics, the triangle inequality states that the distance from A to B to C is never shorter than going directly from A to C. The triangle inequality is a theorem in spaces such as the real numbers, Euclidean space, Lp spaces (p ≥ 1) and in all inner product spaces... The minimum spanning tree of a planar graph. ...

  • Step 1: Construct the minimal spanning tree.
  • Step 2: Duplicate all its edges. That is, wherever there is an edge from u to v, add a second edge from u to v. 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. The Königsberg Bridges graph In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. ... The Königsberg Bridges graph In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. ... In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph which visits each vertex exactly once. ...


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). In mathematics, a perfect matching for a graph is a matching (a subset of edges without common vertices) which touches all vertices exactly once. ...


The Christofides algorithm was one of the first approximation algorithms, and was in part responsible for drawing attention to approximation algorithms as a practical approach to intractable problems. As a matter of fact, the term "algorithm" was not commonly extended to approximation algorithms until later. At the time of publication, the Christofides algorithm was referred to as the Christofides heuristic. In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...


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. In mathematics the Euclidean distance or Euclidean metric is the ordinary distance between the two points that one would measure with a ruler, which can be proven by repeated application of the Pythagorean theorem. ...


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 example, the minimum spanning tree of the graph associated with an instance of Euclidean TSP is a Euclidean minimum spanning tree, and so can be computed in expected O(n log n) time for n points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly. An EMST computed and drawn by Leda, a C++ commercial algorithm library; see the External Links section The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane, where the weight of the edge between each pair of points is the...


In general, 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); this is called a polynomial-time approximation scheme. This algorithm is too slow in practice, however. Instead, heuristics with weaker guarantees are used, but they also perform better on instances of Euclidean TSP than on general instances. In computer science, a polynomial-time approximation scheme (abbreviated PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). ...


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, Carnegie Mellon University, 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.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 35.2: The traveling-salesman problem, pp.1027–1033.
  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman. ISBN 0716710455. A2.3: ND22–24, pp.211–212.

Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ...

See also

Tabu search is a mathematical optimization method, belonging to the class of local search techniques. ... The assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. ...

External links


  Results from FactBites:
 
Traveling Salesman Problem (284 words)
The Concorde TSP solver is used in a genome sequencing package from the National Institutes of Health.
A collection of 25 TSP challenge problems consisting of cities in Argentina through Zimbabwe.
A challenge problem consisting of the locations of 1,904,711 cities throughout the world.
TSPBIB Home Page (5518 words)
A study of complexity transitions on the asymmetric traveling salesman problem, by W. Zhang and R.E. Korf.
The traveling salesman problem, by V. Chvatal, who is one of the authors of a computer code that solved more than twenty previously unsolved instances.
Polynomially Solvable Cases of the Traveling Salesman Problem and a New Exponential Neighbourhood, by R.E. Burkard and V.G. Deineko, Technische Universität Graz, SFB-Report 1, July 1994.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m