Travelling salesman problem
From Wikipedia, the free encyclopedia
The Travelling Salesman problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.
The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.
The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a subproblem in many areas, such as genome sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.
In the theory of computational complexity, the decision version of TSP belongs to the class of NPcomplete problems. Thus, it is assumed that there is no efficient algorithm for solving TSP problems. In other words, it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly.
[edit] History
The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment.^{[2]}
Mathematical problems related to the travelling salesman problem were treated 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.^{[3]} 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, who defines the problem, considers the obvious bruteforce algorithm, and observes the nonoptimality 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. ^{[4]}
Hassler Whitney at Princeton University introduced the name travelling salesman problem soon after.^{[5]}
In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the USA. Notable contributions were made by George Dantzig, Delbert Ray Fulkerson and Selmer M. Johnson at the RAND Corporation in Santa Monica, who expressed the problem as an integer linear program and developed the cutting planemethod for its solution. With these new methods they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. In the following decades, the problem was studied by many researchers from mathematics, computer science,chemistry, physics, and other sciences.
Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NPcomplete, which implies the NPhardness of TSP. This supplied a scientific explanation for the apparent computational difficulty of finding optimal tours.
Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and other managed to exactly solve instances with up to 2392 cities, using cutting planes and branchandbound.
In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2005, Cook and others computed an optimal tour through a 33,810city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are provably within 1% of optimal tour.
[edit] Description
[edit] As a graph problem
TSP can be modelled as a graph: the graph’s vertices correspond to cities and the graph’s edges correspond to connections between cities, the length of an edge is the corresponding connection’s distance. A TSP tour is now a Hamiltonian cycle in the graph, and an optimal TSP tour is a shortest Hamiltonian cycle.
Often, the underlying graph is a complete graph, so that every pair of vertices is connected by an edge. This is a useful simplifying step, because it makes it easy to find a solution, however bad, because the Hamiltonian cycle problem in complete graphs is easy. Instances where not all cities are connected can be transformed into complete graphs by adding very long edges between these cities, edges that will not appear in the optimal tour.
[edit] Asymmetric and symmetric
In the symmetric TSP, the distance between two cities is the same in each direction. Thus, the underlying structure is an undirected graph between; especially, each tour has the same length in both directions. This symmetry halves the number of feasible solutions.
In the asymmetric TSP, the distance from one city to the other need not equal the distance in the other direction, in general, there may not even be a connection in the other direction. Thus, the underlying structure is a directed graph. For example, the asymmetric case models oneway streets or airfares that depend on the direction of travel.
[edit] With metric distances
In the metric TSP the intercity distances satisfy the triangle inequality. This can be understood as “no shortcuts”, in the sense that the direct connection from A to B is never longer than the detour via C.
These edge lengths define a metric on the set of vertices. When the cities are viewed as points in the plane, many natural distance functions are metrics.
 In the Euclidian TSP the distance between two cities is the Euclidean distance between the corresponding points.
 In the Rectilinear TSP the distance between two cities is the sum of the differences of their x and ycoordinates. This metric is often called the Manhattan distance or cityblock metric.
 In the maximum metric, the distance between two points is the maximum of the differences of their x and ycoordinates.
The last two metrics appear for example in routing a machine that drills a given set of holes in a printed circuit. The Manhattan metric corresponds to a machine that adjusts first one coordinate, and then the other, so the time to move to a new point is the sum of both movements. The maximum metric corresponds to a machine that adjusts both coordinates simultaneously, so the time to move to a new point is the slowest of the two movements.
[edit] Nonmetric distances
Distance measures that do not satisfy the triangle inequality arise in many routing problems. For example, one mode of transportation, such as travel by airplane, may be faster, even though it covers a longer distance.
In its definition, the TSP does not allow cities to be visited twice, but many applications do not need this constraint. In such cases, a symmetric, nonmetric instance can be reduced to a metric one. This replaces the original graph with a complete graph in which the intercity distance c_{ij} is replaced by the shortest path between i and j in the original graph.
[edit] Related problems
 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 a Hamiltonian cycle with the least weight.
 The requirement of returning to the starting city does not change the computational complexity of the problem, see Hamiltonian path problem.
 Another related problem is the bottleneck travelling salesman problem (bottleneck TSP): Find a Hamiltonian cycle in a weighted graph with the minimal weight of the weightiest 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 generalized travelling salesman problem deals with "states" that have (one or more) "cities" and the salesman has to visit exactly one "city" from each "state". Also known as the "travelling politician problem". One application is encountered in ordering a solution to the cutting stock problem in order to minimise knife changes. Another is concerned with drilling in semiconductor manufacturing, see e.g. U.S. Patent 7,054,798 . Surprisingly, Behzad and Modarres^{[6]} demonstrated that the generalised travelling salesman problem can be transformed into a standard travelling salesman problem with the same number of cities, but a modified distance matrix.
[edit] Computing a solution
The traditional lines of attacking for the NPhard 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 better or exact heuristics are possible.
[edit] Computational complexity
The problem has been shown to be NPhard (more precisely, it is complete for the complexity class FP^{NP}; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a roundtrip route cheaper than x") is NPcomplete. The bottleneck travelling salesman problem is also NPhard. The problem remains NPhard 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 NPhardness, since it is easily seen that in the planar case there is an optimal tour that visits each city only once (otherwise, by the triangle inequality, a shortcut that skips a repeated visit would not increase the tour length).
[edit] Complexity of approximation
In the general case, finding a shortest travelling salesman tour is NPOcomplete.^{[7]} If the distance measure is a metric and symmetric, the problem becomes APXcomplete^{[8]} and Christofides’s algorithm approximates it within 3/2.^{[9]} If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 7/6. In the asymmetric, metric case, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio 0.814 log n^{[10]}; it is an open question if a constant factor approximation exists.
The corresponding maximization problem of finding the longest travelling salesman tour is approximable within 63/38.^{[11]} If the distance function is symmetric, the longest tour can be approximated within 4/3 by a deterministic algorithm ^{[12]} and within (33 + ε) / 25 by a randomised algorithm.^{[13]}
[edit] Exact algorithms
The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute force search). The running time for this approach lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest applications of dynamic programming is an algorithm that solves the problem in time O(n^{2}2^{n})^{[14]}
The dynamic programming solution requires exponential space. Using inclusion–exclusion, the problem can be solved in time within a polynomial factor of 2^{n} and polynomial space.^{[15]}
Improving these time bounds seems to be difficult. For example, it is an open problem if there exists an exact algorithm for TSP that runs in time O(1.9999^{n})^{[16]}
Other approaches include:
 Various branchandbound algorithms, which can be used to process TSPs containing 4060 cities.
 Progressive improvement algorithms which use techniques reminiscent of linear programming. Works well for up to 200 cities.
 Implementations of branchandbound and problemspecific cut generation; this is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities, see Applegate (2006)
An exact solution for 15,112 German towns from TSPLIB was found in 2001 using the cuttingplane 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 travelling salesman problem of visiting all 24,978 towns in Sweden was solved: a tour of length approximately 72,500 kilometers was found and it was proven that no shorter tour exists.^{[17]}
In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved using Concorde TSP Solver: 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 (Cook et al. 2006). In April 2006 an instance with 85,900 points was solved using Concorde TSP Solver, taking over 136 CPU years, see Applegate (2006).
[edit] Heuristic and approximation algorithms
Various heuristics and approximation algorithms, which quickly yield good solutions 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 23% away from the optimal solution.
Several categories of heuristics are recognized.
[edit] Constructive heuristics
The nearest neighbour (NN) algorithm (or socalled greedy algorithm) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For N cities randomly distributed on a plane, the algorithm averagely yields length = 1.25 * exact_shortest_length.
However, there exist many specially arranged city distributions which make the NN algorithm gives the worst route (Gutin, Yeo, and Zverovich, 2002). This is true for both asymmetric and symmetric TSPs (Gutin and Yeo, 2007).
Rosenkrantz et al. [1977] showed that the NN algorithm has the approximation factor Θ(log  V  ) for instances satisfying the triangle inequality.
Recently a new constructive heuristic, Match Twice and Stitch (MTS) (Kahng, Reda 2004 ^{[18]}), has been proposed. MTS has been shown to empirically outperform all existing tour construction heuristics. MTS performs two sequential matchings, where the second matching is executed after deleting all the edges of the first matching, to yield a set of cycles. The cycles are then stitched to produce the final tour.
[edit] Iterative improvement
 Pairwise exchange, or LinKernighan heuristics.
 The pairwise exchange or '2opt' technique involves iteratively removing two edges and replacing these with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. This is a special case of the kopt method. Note that the label 'LinKernighan' is an often heard misnomer for 2opt. LinKernighan is actually a more general method.
 kopt 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 2kcity TSP can then be solved with brute force methods to find the leastcost recombination of the original fragments. The kopt technique is a special case of the Vopt or variableopt technique. The most popular of the kopt methods are 3opt, and these were introduced by Shen Lin of Bell Labs in 1965. There is a special case of 3opt where the edges are not disjoint (two of the edges are adjacent to one another). In practice, it is often possible to achieve substantial improvement over 2opt without the combinatorial cost of the general 3opt by restricting the 3changes to this special subset where two of the removed edges are adjacent. This socalled twoandahalfopt typically falls roughly midway between 2opt and 3opt, both in terms of the quality of tours achieved and the time required to achieve those tours.
 V'opt heuristic
 The variableopt method is related to, and a generalization of the kopt method. Whereas the kopt methods remove a fixed number (k) of edges from the original tour, the variableopt methods do not fix the size of the edge set to remove. Instead they grow the set as the search process continues. The best known method in this family is the LinKernighan method (mentioned above as a misnomer for 2opt). Shen Lin and Brian Kernighan first published their method in 1972, and it was the most reliable heuristic for solving travelling salesman problems for nearly two decades. More advanced variableopt methods were developed at Bell Labs in the late 1980s by David Johnson and his research team. These methods (sometimes called LinKernighanJohnson) build on the LinKernighan method, adding ideas from tabu search and evolutionary computing. The basic LinKernighan technique gives results that are guaranteed to be at least 3opt. The LinKernighanJohnson methods compute a LinKernighan tour, and then perturb the tour by what has been described as a mutation that removes at least four edges and reconnecting the tour in a different way, then vopting the new tour. The mutation is often enough to move the tour from the local minimum identified by LinKernighan. Vopt methods are widely considered the most powerful heuristics for the problem, and are able to address special cases, such as the Hamilton Cycle Problem and other nonmetric TSPs that other heuristics fail on. For many years LinKernighanJohnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best known solutions for all other TSPs on which the method had been tried.
[edit] Randomised improvement
 Optimised Markov chain algorithms which use local searching heuristic subalgorithms can find a route extremely close to the optimal route for 700 to 800 cities.
 Random path change algorithms are currently the stateoftheart search algorithms and work up to 100,000 cities. The concept is quite simple: Choose a random path, choose four nearby points, swap their ways to create a new random path, while in parallel decreasing the upper bound of the path length. If repeated until a certain number of trials of random path changes fail due to the upper bound, one has found a local minimum with high probability, and further it is a global minimum with high probability^{[citation needed]} (where high means that the rest probability decreases exponentially in the size of the problem  thus for 10,000 or more nodes, the chances of failure is negligible).
TSP is a touchstone for many general heuristics devised for combinatorial optimization such as genetic algorithms, simulated annealing, Tabu search, ant colony optimization, and the cross entropy method.
[edit] Example letting the inversion operator find a good solution
This article is missing citations or needs footnotes. Please help add inline citations to guard against copyright violations and factual inaccuracies. (February 2009) 
^{[original research?]}
Suppose that the number of towns is sixty. For a random search process, this is like having a deck of cards numbered 1, 2, 3, ... 59, 60  the number of permutations is of the same order of magnitude as the total number of atoms in the known universe. If the hometown is not counted the number of possible tours becomes 60*59*58*...*4*3; approximately 4×10^{81}.
Suppose that the salesman does not have a map showing the location of the towns, but only a deck of numbered cards, which he may permute, put in a card reader  as in early computers  and let the computer calculate the length of the tour. The probability to find the shortest tour by random permutation is about one in 10^{81} so, it will never happen. So, should he give up?
No, by no means, evolution may be of great help to him; at least if it could be simulated on his computer. The natural evolution uses an inversion operator, which  in principle  is extremely well suited for finding good solutions to the problem. A part of the card deck (DNA)  chosen at random  is taken out, turned in opposite direction and put back in the deck again like in the figure below with 6 towns. The hometown (nr 1) is not counted.
If this inversion takes place where the tour happens to have a loop, then the loop is opened and the salesman is guaranteed a shorter tour. The probability that this will happen is greater than 1/(60*60) for any loop if we have 60 towns, so, in a population with one million card decks it might happen 1000000/3600 = 277 times that a loop will disappear.
This has been simulated with a population of 180 card decks, from which 60 decks are selected in every generation. The figure below shows a random tour at start
After about 1500 generations all loops have been removed and the length of the random tour at start has been reduced to 1/5 of the original tour. The human eye can see that some improvements can be made, but probably the random search has found a tour, which is not much longer than the shortest possible. See figure below.
In a special case when all towns are equidistantly placed along a circle, the optimal solution is found when all loops have been removed. This means that this simple random search is able to find one optimal tour out of as many as 10^{80}. See also Goldberg, 1989.
[edit] Ant colony optimization
This section does not cite any references or sources. Please help improve this article by adding citations to reliable sources (ideally, using inline citations). Unsourced material may be challenged and removed. (February 2009) 
Artificial intelligence researcher Marco Dorigo described in 1997 a method of heuristically generating "good solutions" to the TSP using a simulation of an ant colony called ACS.^{[19]} It uses some of the same ideas used by real ants to find short paths between food sources and their nest, an emergent behavior resulting from each ant's preference to follow trail pheromones deposited by other ants.
ACS sends out a large number of virtual ant agents to explore many possible routes on the map. Each ant probabilistically chooses the next city to visit based on a heuristic combining the distance to the city and the amount of virtual pheromone deposited on the edge to the city. The ants explore, depositing pheromone on each edge that they cross, until they have all completed a tour. At this point the ant which completed the shortest tour deposits virtual pheromone along its complete tour route (global trail updating). The amount of pheromone deposited is inversely proportional to the tour length; the shorter the tour, the more it deposits.
[edit] Special cases
[edit] Metric TSP
A very natural restriction of the TSP is to require that the distances between cities form a metric, i.e., they satisfy 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 a constantfactor approximation algorithm due to Christofides^{[20]} that 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.
 Construct the minimum spanning tree.
 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.
 Find a Eulerian cycle in it. Clearly, its length is twice the length of the tree.
 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 Christofides algorithm follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimumweight perfect matching. This gives a TSP tour which is at most 1.5 times the optimal. 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; the Christofides algorithm was initially referred to as the Christofides heuristic.
In the special case that distances between cities are all either one or two (and thus the triangle inequality is necessarily satisfied), there is a polynomialtime approximation algorithm that finds a tour of length at most 8/7 times the optimal tour length^{[21]}. However, it is a longstanding (since 1975) open problem to improve the Christofides approximation factor of 1.5 for general metric TSP to a smaller constant. It is known that, unless P = NP, there is no polynomialtime algorithm that finds a tour of length at most 220/219=1.00456… times the optimal tour's length^{[22]}. In the case of bounded metrics it is known that there is no polynomial time algorithm that constructs a tour of length at most 1/388 more than optimal, unless P = NP^{[23]}.
[edit] Euclidean TSP
Euclidean TSP, or planar TSP, is the TSP with the distance being the ordinary Euclidean distance.
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 2approximation algorithm for TSP with triangle inequality above to operate more quickly.
In general, for any c > 0, there is a polynomialtime algorithm that finds a tour of length at most (1 + 1/c) times the optimal for geometric instances of TSP in O(n (log n)^O(c)) time; this is called a polynomialtime approximation scheme^{[24]} In practice, heuristics with weaker guarantees continue to be used.
[edit] Asymmetric TSP
In most cases, the distance between two nodes in the TSP network is the same in both directions. The case where the distance from A to B is not equal to the distance from B to A is called asymmetric TSP. A practical application of an asymmetric TSP is route optimisation using streetlevel routing (asymmetric due to oneway streets, sliproads and motorways).
[edit] Solving by conversion to Symmetric TSP
Solving an asymmetric TSP graph can be somewhat complex. The following is a 3x3 matrix containing all possible path weights between the nodes A, B and C. One option is to turn an asymmetric matrix of size N into a symmetric matrix of size 2N, doubling the complexity.

Asymmetric Path Weights A B C A 1 2 B 6 3 C 5 4
To double the size, each of the nodes in the graph is duplicated, creating a second ghost node. Using duplicate points with very low weights, such as ∞, provides a cheap route "linking" back to the real node and allowing symmetric evaluation to continue. The original 3x3 matrix shown above is visible in the bottom left and the inverse of the original in the topright. Both copies of the matrix have had their diagonals replaced by the lowcost hop paths, represented by ∞.

Symmetric Path Weights A B C A' B' C' A ∞ 6 5 B 1 ∞ 4 C 2 3 ∞ A' ∞ 1 2 B' 6 ∞ 3 C' 5 4 ∞
The original 3x3 matrix would produce two Hamiltonian cycles (a path that visits every node once), namely ABCA [score 9] and ACBA [score 12]. Evaluating the 6x6 symmetric version of the same problem now produces many paths, including AA'BB'CC'A, AB'CA'A, AA'BC'A [all score 9∞].
The important thing about each new sequence is that there will be an alternation between dashed (A',B',C') and undashed nodes (A,B,C) and that the link to "jump" between any related pair (AA') is effectively free. A version of the algorithm could use any weight for the AA' path, as long as that weight is lower than all other path weights present in the graph. As the path weight to "jump" must effectively be "free", the value zero (0) could be used to represent this cost — if zero is not being used for another purpose already (such as designating invalid paths). In the two examples above, nonexistent paths between nodes are shown as a blank square.
[edit] Benchmarks
For benchmarking of TSP algorithms, TSPLIB is 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.
[edit] Human performance on TSP
The TSP, in particular the Euclidean variant of the problem, has attracted the attention of researchers in cognitive psychology. It is observed that humans are able to produce good quality solutions quickly. The first issue of the Journal of Problem Solving is devoted to the topic of human performance on TSP.
[edit] TSP path length for random pointset in a square
Consider N stations randomly distributed in a 1 x 1 square with N>>1.
[edit] Lower bound
A lower bound of the shortest tour length is , obtained by assuming the mover stands on station j and always visits j's nearest as next. ^{[25]}
A better lower bound is , obtained by assuming j's next is j's nearest, and j's previous is j's second nearest. This can be written as
A similar result obtained by dividing the points into equal disjoint sets and considering steps forwards and backwards from point j on the shortest path gives a lower bound of .
 David S. Johnson^{[26]} obtained a lower bound by computer experiment:
, where 0.522 comes from boundary effect.
 Christine L. Valenzuela and Antonia J. Jones ^{[27]} obtained another lower bound by computer experiment:
[edit] Upper bound
By applying simulated annealing method on samples of N=40000, computer shows an upper bound
( +0.72)*1.015 , where 0.72 comes from boundary effect.
[edit] See also
 Canadian traveller problem
 Vehicle routing problem
 Route inspection problem
 Set TSP problem
 Seven Bridges of Königsberg
 Six degrees of separation
 Traveling repairman problem (minimum latency problem)
 Traveling tourist problem
[edit] Notes
 ^ Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other: 14! / 2 = 43589145600
 ^ “Der Handlungsreisende – wie er sein soll und was er zu thun [sic] hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten CommisVoyageur”
 ^ A discussion of the early work of Hamilton and Kirkman can be found in Graph Theory 17361936
 ^ 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. 168.PS,PDF
 ^ Behzad, Arash; Modarres, Mohammad (2002), "New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem", Proceedings of the 15th International Conference of Systems Engineering (Las Vegas)
 ^ Orponen (1987)
 ^ Papadimitriou (1983)
 ^ Christofides (1976)
 ^ Kaplan (2004)
 ^ Kosaraju (1994)
 ^ Serdyukov (1984)
 ^ Hassin (2000)
 ^ Bellman (1960), Bellman (1962), Held (1962)
 ^ Kohn (1977) Karp (1982)
 ^ Woeginger (2003)
 ^ Work by David Applegate, AT&T Labs  Research, Robert Bixby, ILOG and Rice University, Vašek Chvátal, Concordia University, William Cook, Georgia Tech, and Keld Helsgaun, Roskilde University is discussed on their project web page hosted by Georgia Tech and last updated in June 2004, here
 ^ A. B. Kahng and S. Reda, "Match Twice and Stitch: A New TSP Tour Construction Heuristic," Operations Research Letters, 2004, 32(6). pp. 499509. http://www.sciencedirect.com/science?_ob=GatewayURL&_method=citationSearch&_uoikey=B6V8M4CKFN5S4&_origin=SDEMFRASCII&_version=1&md5=04d492ab46c07b9911e230ebecd0f70d
 ^ Marco Dorigo. Ant Colonies for the Traveling Salesman Problem. IRIDIA, Université Libre de Bruxelles. IEEE Transactions on Evolutionary Computation, 1(1):53–66. 1997. http://citeseer.ist.psu.edu/86357.html
 ^ N. Christofides, Worstcase analysis of a new heuristic for the traveling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, 1976.
 ^ P. Berman (2006). M. Karpinski, "8/7Approximation Algorithm for (1,2)TSP", Proc. 17th ACMSIAM SODA (2006), pp. 641648.
 ^ C.H. Papadimitriou and Santosh Vempala. (2000). "On the approximability of the traveling salesman problem", Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000.
 ^ L. Engebretsen, M. Karpinski, Approximation hardness of TSP with bounded metrics, Proceedings of 28th ICALP (2001), LNCS 2076, Springer 2001, pp. 201212.
 ^ Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. Journal of the ACM, Vol.45, Issue 5, pp.753–782. ISSN:00045411. September 1998. http://citeseer.ist.psu.edu/arora96polynomial.html
 ^ Lingwanjae talk
 ^ David S. Johnson
 ^ Christine L. Valenzuela and Antonia J. Jones
[edit] References
 Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook (2006), The Traveling Salesman Problem
 Bellman, R. (1960), "Combinatorial Processes and Dynamic Programming", Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,, American Mathematical Society, pp. 217–249
 Bellman, R. (1962), "Dynamic Programming Treatment of the Travelling Salesman Problem", J. Assoc. Comput. Mach. 9: 61–63
 Christofides, N. (1976), "Worstcase analysis of a new heuristic for the travelling salesman problem", Technical Report 388, Graduate School of Industrial Administration, CarnegieMellon University, Pittsburgh.
 Hassin, R.; Rubinstein, S. (2000), "Better approximations for max TSP", Information Processing
Letters 75: 181–186
 Held, M.; Karp, R. M. (1962), "A Dynamic Programming Approach to Sequencing Problems", Journal of the Society for Industrial and Applied Mathematics 10 (1): 196–210, doi:
 Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), "Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs", In Proc. 44th IEEE Symp. on Foundations of Comput. Sci., pp. 56–65
 Karp, R.M. (1982), Oper. Res. Lett. 1: 49–51
 Kohn, S.; Gottlieb, A.; Kohn, M. (1977), "A Generating Function Approach to the Traveling Salesman Problem", ACM Annual Conference, ACM Press, pp. 294–300
 Kosaraju, S. R.; Park, J. K.; Stein, C. (1994), "Long tours and short superstrings'", Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, pp. 166177
 Orponen, P.; Mannila, H. (1987), "On approximation preserving reductions: Complete problems and robust measures'", Technical Report C198728, Department of Computer Science, University of Helsinki
 Papadimitriou, C. H.; Yannakakis, M. (1993), "The traveling salesman problem with distances one and two", Math. Oper. Res. 18: 111
 Serdyukov, A. I. (1984), "An algorithm with an estimate for the traveling salesman problem of the maximum'", Upravlyaemye Sistemy 25: 8086
 Woeginger, G.J. (2003), "Exact Algorithms for NPHard Problems: A Survey", Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer, pp. 185–207
[edit] Further reading
 Gilbert Babin Stephanie Deneaulty Gilbert Laportey (2005). "Improvements to the Oropt Heuristic for the Symmetric Traveling Salesman Problem".
 D.L. Applegate, R.E. Bixby, V. Chvátal and W.J. Cook (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press. ISBN 9780691129938.
 S. Arora (1998). "Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems". Journal of ACM, 45 (1998), pp. 753782.
 William Cook, Daniel Espinoza, Marcos Goycoolea (2006). Computing with dominoparity inequalities for the TSP. INFORMS Journal on Computing. Accepted.
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (1954). Introduction to Algorithms, Second Edition. MIT Press and McGrawHill, 2001. ISBN 0262032937. Section 35.2: The travelingsalesman problem, pp. 1027–1033.
 G.B. Dantzig, R. Fulkerson, and S. M. Johnson, Solution of a largescale traveling salesman problem, Operations Research 2 (1954), pp. 393410.
 Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman. ISBN 0716710455. A2.3: ND22–24, pp.211–212.
 D.E. Goldberg (1989). Genetic Algorithms in Search, Optimization & Machine Learning. AddisonWesley, New York, 1989.
 G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedytype heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 8186.
 G. Gutin and A.P. Punnen (2006). The Traveling Salesman Problem and Its Variations. Springer. ISBN 0387444599.
 D.S. Johnson & L.A. McGeoch (1997). The Traveling Salesman Problem: A Case Study in Local Optimization, Local Search in Combinatorial Optimisation, E. H. L. Aarts and J.K. Lenstra (ed), John Wiley and Sons Ltd, 1997, pp. 215310.
 E. L. Lawler and Jan Karel Lenstra and A. H. G. Rinnooy Kan and D. B. Shmoys (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons. ISBN 0471904139.
 J.N. MacGregor & T. Ormerod (1996). Human performance on the traveling salesman problem. Perception & Psychophysics, 58(4), pp. 527–539.
 J. S. B. Mitchell (1999). "Guillotine subdivisions approximate polygonal subdivisions: A simple polynomialtime approximation scheme for geometric TSP, kMST, and related problems", SIAM Journal on Computing, 28 (1999), pp. 1298–1309.
 S. Rao, W. Smith. Approximating geometrical graphs via 'spanners' and 'banyans'. Proc. 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 540550.
 Daniel J. Rosenkrantz and Richard E. Stearns and Phlip M. Lewis II (1977). "An Analysis of Several Heuristics for the Traveling Salesman Problem". SIAM J. Comput. 6 (5): 563–581. doi: .
 D. Vickers, M. Butavicius, M. Lee, & A. Medvedev (2001). Human performance on visually presented traveling salesman problems. Psychological Research, 65, pp. 34–45.
 Chris Walshaw, A Multilevel LinKernighanHelsgaun Algorithm for the Travelling Salesman Problem (CMS Press Paper S.), CMS Press, Paperback, December 2001.
 Chris Walshaw, A Multilevel Approach to the Travelling Salesman Problem, CMS Press, Paperback, August 2000.
[edit] External links
 Travelling Salesman Problem by Jon McLoone based on a program by Stephen Wolfram, after work by Stan Wagon, Wolfram Demonstrations Project.