In thetheory of computational complexity, thetravelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is anNP-hard problem incombinatorial optimization, important intheoretical computer science andoperations research.
Thetravelling purchaser problem, thevehicle routing problem and thering star problem[1] are three generalizations of TSP.
The decision version of the TSP (where given a lengthL, the task is to decide whether the graph has a tour whose length is at mostL) belongs to the class ofNP-complete problems. Thus, it is possible that theworst-caserunning time for any algorithm for the TSP increasessuperpolynomially (but no more thanexponentially) with the number of cities.
The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as abenchmark for many optimization methods. Even though the problem is computationally difficult, manyheuristics andexact algorithms are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%.[2]
The TSP has several applications even in its purest formulation, such asplanning,logistics, and the manufacture ofmicrochips. Slightly modified, it appears as a sub-problem in many areas, such asDNA sequencing. In these applications, the conceptcity represents, for example, customers, soldering points, or DNA fragments, and the conceptdistance represents travelling times or cost, or asimilarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources want to minimize the time spent moving the telescope between the sources; in such problems, the TSP can be embedded inside anoptimal control problem. In many applications, additional constraints such as limited resources or time windows may be imposed.
The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours throughGermany andSwitzerland, but contains no mathematical treatment.[3]
The TSP was mathematically formulated in the 19th century by the Irish mathematicianWilliam Rowan Hamilton and by the British mathematicianThomas Kirkman. Hamilton'sicosian game was a recreational puzzle based on finding aHamiltonian cycle.[4] The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and atHarvard, notably byKarl Menger, who defines the problem, considers the obviousbrute-force algorithm, and observes the non-optimality of thenearest neighbour heuristic:
We denote bymessenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely 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.[5]
It was first considered mathematically in the 1930s byMerrill M. Flood, who was looking to solve a school bus routing problem.[6]Hassler Whitney atPrinceton University generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling [or traveling] salesman problem" was the 1949RAND Corporation report byJulia Robinson, "On the Hamiltonian game (a traveling salesman problem)."[7][8]
In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the United States after theRAND Corporation inSanta Monica offered prizes for steps in solving the problem.[6] Notable contributions were made byGeorge Dantzig,Delbert Ray Fulkerson, andSelmer M. Johnson from the RAND Corporation, who expressed the problem as aninteger linear program and developed thecutting plane method for its solution. They wrote what is considered the seminal paper on the subject in which, 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. Dantzig, Fulkerson, and Johnson, however, speculated that, given a near-optimal solution, one may be able to find optimality or prove optimality by adding a small number of extra inequalities (cuts). They used this idea to solve their initial 49-city problem using a string model. They found they only needed 26 cuts to come to a solution for their 49 city problem. While this paper did not give an algorithmic approach to TSP problems, the ideas that lay within it were indispensable to later creating exact solution methods for the TSP, though it would take 15 years to find an algorithmic approach in creating these cuts.[6] As well as cutting plane methods, Dantzig, Fulkerson, and Johnson usedbranch-and-bound algorithms perhaps for the first time.[6]
In 1959,Jillian Beardwood, J.H. Halton, andJohn Hammersley published an article entitled "The Shortest Path Through Many Points" in the journal of theCambridge Philosophical Society.[9] The Beardwood–Halton–Hammersley theorem provides a practical solution to the travelling salesman problem. The authors derived an asymptotic formula to determine the length of the shortest route for a salesman who starts at a home or office and visits a fixed number of locations before returning to the start.
In the following decades, the problem was studied by many researchers frommathematics,computer science,chemistry,physics, and other sciences. In the 1960s, however, a new approach was created that, instead of seeking optimal solutions, would produce a solution whose length is provably bounded by a multiple of the optimal length, and in doing so would create lower bounds for the problem; these lower bounds would then be used with branch-and-bound approaches. One method of doing this was to create aminimum spanning tree of the graph and then double all its edges, which produces the bound that the length of an optimal tour is at most twice the weight of a minimum spanning tree.[6]
In 1976,Christofides and Serdyukov (independently of each other) made a big advance in this direction:[10] theChristofides–Serdyukov algorithm yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution. As the algorithm was simple and quick, many hoped it would give way to a near-optimal solution method. However, this hope for improvement did not immediately materialize, and the Christofides–Serdyukov algorithm remained the method with the best worst-case scenario until 2011, when a (very) slightly improved approximation algorithm was developed for the subset of "graphical" TSPs.[11] In 2020, this tiny improvement was extended to the full (metric) TSP.[12][13]
Richard M. Karp showed in 1972 that theHamiltonian cycle problem wasNP-complete, which implies theNP-hardness of TSP. This supplied a mathematical 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 others managed to exactly solve instances with up to 2,392 cities, using cutting planes andbranch-and-bound.
In the 1990s,Applegate,Bixby,Chvátal, andCook developed the programConcorde 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 2006, Cook and others computed an optimal tour through an 85,900-city 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 guaranteed to be within 2–3% of an optimal tour.[14]
TSP can be modeled as anundirected weighted graph, such that cities are the graph'svertices, paths are the graph'sedges, and a path's distance is the edge's weight. It is a minimization problem starting and finishing at a specifiedvertex after having visited each othervertex exactly once. Often, the model is acomplete graph (i.e., each pair of vertices is connected by an edge). If no path exists between two cities, then adding a sufficiently long edge will complete the graph without affecting the optimal tour.
In thesymmetric TSP, the distance between two cities is the same in each opposite direction, forming anundirected graph. This symmetry halves the number of possible solutions. In theasymmetric TSP, paths may not exist in both directions or the distances might be different, forming adirected graph. Traffic congestion, one-way streets, and airfares for cities with different departure and arrival fees are real-world considerations that could yield a TSP problem in asymmetric form.
The TSP can be formulated as aninteger linear program.[17][18][19] Several formulations are known. Two notable formulations are the Miller–Tucker–Zemlin (MTZ) formulation and the Dantzig–Fulkerson–Johnson (DFJ) formulation. The DFJ formulation is stronger, though the MTZ formulation is still useful in certain settings.[20][21]
Common to both these formulations is that one labels the cities with the numbers and takes to be the cost (distance) from city to city. The main variables in the formulations are:
It is because these are 0/1 variables that the formulations become integer programs; all other constraints are purely linear. In particular, the objective in the program is to minimize the tour length
Without further constraints, the will effectively range over all subsets of the set of edges, which is very far from the sets of edges in a tour, and allows for a trivial minimum where all. Therefore, both formulations also have the constraints that, at each vertex, there is exactly one incoming edge and one outgoing edge, which may be expressed as the linear equations
These ensure that the chosen set of edges locally looks like that of a tour, but still allow for solutions violating the global requirement that there isone tour which visits all vertices, as the edges chosen could make up several tours, each visiting only a subset of the vertices; arguably, it is this global requirement that makes TSP a hard problem. The MTZ and DFJ formulations differ in how they express this final requirement as linear constraints.
In addition to the variables as above, there is for each a dummy variable that keeps track of the order in which the cities are visited, counting from city; the interpretation is that implies city is visited before city For a given tour (as encoded into values of the variables), one may find satisfying values for the variables by making equal to the number of edges along that tour, when going from city to city[22]
Because linear programming favors non-strict inequalities () over strict(), we would like to impose constraints to the effect that
Merely requiring wouldnot achieve that, because this also requires when which is not correct. Instead MTZ use the linear constraints
where the constant term provides sufficient slack that does not impose a relation between and
The way that the variables then enforce that a single tour visits all cities is that they increase by at least for each step along a tour, with a decrease only allowed where the tour passes through city That constraint would be violated by every tour which does not pass through city so the only way to satisfy it is that the tour passing city also passes through all other cities.
The MTZ formulation of TSP is thus the following integer linear programming problem:
The first set of equalities requires that each city is arrived at from exactly one other city, and the second set of equalities requires that from each city there is a departure to exactly one other city. The last constraint enforces that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities.
Label the cities with the numbers 1, ...,n and define:
Take to be the distance from cityi to cityj. Then TSP can be written as the following integer linear programming problem:
The last constraint of the DFJ formulation—called asubtour elimination constraint—ensures that no proper subset Q can form a sub-tour, so the solution returned is a single tour and not the union of smaller tours. Intuitively, for each proper subset Q of the cities, the constraint requires that there be fewer edges than cities in Q: if there were to be as many edges in Q as cities in Q, that would represent a subtour of the cities of Q. Because this leads to an exponential number of possible constraints, in practice it is solved withrow generation.[23]
The traditional lines of attack for the NP-hard problems are the following:
The most direct solution would be to try allpermutations (ordered combinations) and see which one is cheapest (usingbrute-force search). The running time for this approach lies within a polynomial factor of, thefactorial of the number of cities, so this solution becomes impractical even for only 20 cities.
One of the earliest applications ofdynamic programming is theHeld–Karp algorithm, which solves the problem in time.[24] This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach.
Improving these time bounds seems to be difficult. For example, it has not been determined whether a classicalexact algorithm for TSP that runs in time exists.[25] The currently best quantumexact algorithm for TSP due to Ambainis et al. runs in time.[26]
Other approaches include:
An exact solution for 15,112 German towns from TSPLIB was found in 2001 using thecutting-plane method proposed byGeorge Dantzig,Ray Fulkerson, andSelmer M. Johnson in 1954, based onlinear programming. The computations were performed on a network of 110 processors located atRice University andPrinceton University. The total computation time was equivalent to 22.6 years on a single 500 MHzAlpha 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 kilometres was found, and it was proven that no shorter tour exists.[29] In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved usingConcorde 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 usingConcorde TSP Solver, taking over 136 CPU-years; seeApplegate et al. (2006).
Variousheuristics andapproximation algorithms, which quickly yield good solutions, have been devised. These include themulti-fragment algorithm. 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.[14]
Several categories of heuristics are recognized.
Thenearest neighbour (NN) algorithm (agreedy algorithm) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. ForN cities randomly distributed on a plane, the algorithm on average yields a path 25% longer than the shortest possible path;[30] however, there exist many specially-arranged city distributions which make the NN algorithm give the worst route.[31] This is true for both asymmetric and symmetric TSPs.[32] Rosenkrantz et al.[33] showed that the NN algorithm has the approximation factor for instances satisfying the triangle inequality. A variation of the NN algorithm, called nearest fragment (NF) operator, which connects a group (fragment) of nearest unvisited cities, can find shorter routes with successive iterations.[34] The NF operator can also be applied on an initial solution obtained by the NN algorithm for further improvement in an elitist model, where only better solutions are accepted.
Thebitonic tour of a set of points is the minimum-perimetermonotone polygon that has the points as its vertices; it can be computed efficiently withdynamic programming.
Anotherconstructive heuristic, Match Twice and Stitch (MTS), performs two sequentialmatchings, 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.[35]
Thealgorithm of Christofides and Serdyukov follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weightperfect matching. This gives a TSP tour which is at most 1.5 times the optimal. It was one of the firstapproximation algorithms, and was in part responsible for drawing attention to approximation algorithms as a practical approach tointractable 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.[10]
This algorithm looks at things differently by using a result from graph theory which helps improve on the lower bound of the TSP which originated from doubling the cost of the minimum spanning tree. Given anEulerian graph, we can find anEulerian tour in time,[6] so if we had an Eulerian graph with cities from a TSP as vertices, then we can easily see that we could use such a method for finding an Eulerian tour to find a TSP solution. By thetriangle inequality, we know that the TSP tour can be no longer than the Eulerian tour, and we therefore have a lower bound for the TSP. Such a method is described below.
To improve the lower bound, a better way of creating an Eulerian graph is needed. By the triangle inequality, the best Eulerian graph must have the same cost as the best travelling salesman tour; hence, finding optimal Eulerian graphs is at least as hard as TSP. One way of doing this is by minimum weightmatching using algorithms with a complexity of.[6]
Making a graph into an Eulerian graph starts with the minimum spanning tree; all the vertices of odd order must then be made even, so a matching for the odd-degree vertices must be added, which increases the order of every odd-degree vertex by 1.[6] This leaves us with a graph where every vertex is of even order, which is thus Eulerian. Adapting the above method gives the algorithm of Christofides and Serdyukov:
The pairwise exchange or2-opt technique involves iteratively removing two edges and replacing them with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. Similarly, the3-opt technique removes 3 edges and reconnects them to form a shorter tour. These are special cases of thek-opt method. The labelLin–Kernighan is an often heard misnomer for 2-opt; Lin–Kernighan is actually the more generalk-opt method.
For Euclidean instances, 2-opt heuristics give on average solutions that are about 5% better than those yielded by Christofides' algorithm. If we start with an initial solution made with agreedy algorithm, then the average number of moves greatly decreases again and is; however, for random starts, the average number of moves is. While this is a small increase in size, the initial number of moves for small problems is 10 times as big for a random start compared to one made from a greedy heuristic. This is because such 2-opt heuristics exploit 'bad' parts of a solution such as crossings. These types of heuristics are often used withinvehicle routing problem heuristics to re-optimize route solutions.[30]
TheLin–Kernighan heuristic is a special case of theV-opt or variable-opt technique. It involves the following steps:
The most popular of thek-opt methods are 3-opt, as introduced by Shen Lin ofBell Labs in 1965. A special case of 3-opt is 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 2-opt without the combinatorial cost of the general 3-opt by restricting the 3-changes to this special subset where two of the removed edges are adjacent. This so-called two-and-a-half-opt typically falls roughly midway between 2-opt and 3-opt, both in terms of the quality of tours achieved and the time required to achieve those tours.
The variable-opt method is related to, and a generalization of, thek-opt method. Whereas thek-opt methods remove a fixed number (k) of edges from the original tour, the variable-opt 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 Lin–Kernighan method (mentioned above as a misnomer for 2-opt).Shen Lin andBrian 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 variable-opt methods were developed at Bell Labs in the late 1980s by David Johnson and his research team. These methods (sometimes calledLin–Kernighan–Johnson) build on the Lin–Kernighan method, adding ideas fromtabu search andevolutionary computing. The basic Lin–Kernighan technique gives results that are guaranteed to be at least 3-opt. The Lin–Kernighan–Johnson methods compute a Lin–Kernighan tour, and then perturb the tour by what has been described as a mutation that removes at least four edges and reconnects the tour in a different way, thenV-opting the new tour. The mutation is often enough to move the tour from thelocal minimum identified by Lin–Kernighan.V-opt 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 non-metric TSPs that other heuristics fail on. For many years, Lin–Kernighan–Johnson 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.
OptimizedMarkov chain algorithms which use local searching heuristic sub-algorithms can find a route extremely close to the optimal route for 700 to 800 cities.
TSP is a touchstone for many general heuristics devised for combinatorial optimization such asgenetic algorithms,simulated annealing,tabu search,ant colony optimization,river formation dynamics (seeswarm intelligence), and thecross entropy method.
This starts with a sub-tour such as theconvex hull and then inserts other vertices.[36]
Artificial intelligence researcherMarco Dorigo described in 1993 a method of heuristically generating "good solutions" to the TSP using asimulation of an ant colony calledACS (ant colony system).[37] It models behavior observed in real ants to find short paths between food sources and their nest, anemergent behavior resulting from each ant's preference to followtrail 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.
![1) An ant chooses a path among all possible paths and lays a pheromone trail on it. 2) All the ants are travelling on different paths, laying a trail of pheromones proportional to the quality of the solution. 3) Each edge of the best path is more reinforced than others. 4) Evaporation ensures that the bad solutions disappear. The map is a work of Yves Aubry [2].](/mt/?noimg=&dark=on&url=http%3a%2f%2fen.wikipedia.org%2fwiki%2fFile%3aAco_TSP.svg)
In themetric TSP, also known asdelta-TSP or Δ-TSP, the intercity distances satisfy thetriangle inequality.
A very natural restriction of the TSP is to require that the distances between cities form ametric to satisfy thetriangle inequality; that is, the direct connection fromA toB is never farther than the route via intermediateC:
The edges then build ametric on the set of vertices. When the cities are viewed as points in the plane, many naturaldistance functions are metrics, and so many natural instances of TSP satisfy this constraint.
The following are some examples of metric TSPs for various metrics.
The last two metrics appear, for example, in routing a machine that drills a given set of holes in aprinted circuit board. 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 slower of the two movements.
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, non-metric instance can be reduced to a metric one. This replaces the original graph with a complete graph in which the inter-city distance is replaced by theshortest path length betweenA andB in the original graph.
For points in theEuclidean plane, the optimal solution to the travelling salesman problem forms asimple polygon through all of the points, apolygonalization of the points.[38] Any non-optimal solution with crossings can be made into a shorter solution without crossings by local optimizations. TheEuclidean distance obeys the triangle inequality, so the Euclidean TSP forms a special case of metric TSP. However, even when the input points have integer coordinates, their distances generally take the form ofsquare roots, and the length of a tour is asum of radicals, making it difficult to perform thesymbolic computation needed to perform exact comparisons of the lengths of different tours.
Like the general TSP, the exact Euclidean TSP is NP-hard, but the issue with sums of radicals is an obstacle to proving that its decision version is in NP, and therefore NP-complete. A discretized version of the problem with distances rounded to integers is NP-complete.[39] With rational coordinates and the actual Euclidean metric, Euclidean TSP is known to be in the Counting Hierarchy,[40] a subclass of PSPACE. With arbitrary real coordinates, Euclidean TSP cannot be in such classes, since there are uncountably many possible inputs. Despite these complications, Euclidean TSP is much easier than the general metric case for approximation.[41] For example, the minimum spanning tree of the graph associated with an instance of the Euclidean TSP is aEuclidean minimum spanning tree, and so can be computed in expectedO(n logn) time forn 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.
In general, for anyc > 0, whered is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/c) times the optimal for geometric instances of TSP in
time; this is called apolynomial-time approximation scheme (PTAS).[42]Sanjeev Arora andJoseph S. B. Mitchell were awarded theGödel Prize in 2010 for their concurrent discovery of a PTAS for the Euclidean TSP.
In practice, simpler heuristics with weaker guarantees continue to be used.
In most cases, the distance between two nodes in the TSP network is the same in both directions. The case where the distance fromA toB is not equal to the distance fromB toA is called asymmetric TSP. A practical application of an asymmetric TSP is route optimization using street-level routing (which is made asymmetric by one-way streets, slip-roads, motorways, etc.).
Thestacker crane problem can be viewed as a special case of the asymmetric TSP. In this problem, the input consists of ordered pairs of points in a metric space, which must be visited consecutively in order by the tour. These pairs of points can be viewed as the nodes of an asymmetric TSP, with asymmetric distances reflecting the combined cost of traveling from the first point of a pair to its second and then from the second point of a pair to the first point of the next pair.
Solving an asymmetric TSP graph can be somewhat complex. The following is a 3×3 matrix containing all possible path weights between the nodesA,B andC. One option is to turn an asymmetric matrix of sizeN into a symmetric matrix of size 2N.[43]
| 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 secondghost node, linked to the original node with a "ghost" edge of very low (possibly negative) weight, here denoted −w. (Alternatively, the ghost edges have weight 0, and weight w is added to all other edges.) The original 3×3 matrix shown above is visible in the bottom left and the transpose of the original in the top-right. Both copies of the matrix have had their diagonals replaced by the low-cost hop paths, represented by −w. In the new graph, no edge directly links original nodes and no edge directly links ghost nodes.
| A | B | C | A′ | B′ | C′ | |
|---|---|---|---|---|---|---|
| A | −w | 6 | 5 | |||
| B | 1 | −w | 4 | |||
| C | 2 | 3 | −w | |||
| A′ | −w | 1 | 2 | |||
| B′ | 6 | −w | 3 | |||
| C′ | 5 | 4 | −w |
The weight −w of the "ghost" edges linking the ghost nodes to the corresponding original nodes must be low enough to ensure that all ghost edges must belong to any optimal symmetric TSP solution on the new graph (w = 0 is not always low enough). As a consequence, in the optimal symmetric tour, each original node appears next to its ghost node (e.g. a possible path is), and by merging the original and ghost nodes again we get an (optimal) solution of the original asymmetric problem (in our example,).
There is an analogous problem ingeometric measure theory which asks the following: under what conditions may a subsetE ofEuclidean space be contained in arectifiable curve (that is, when is there a curve with finite length that visits every point inE)? This problem is known as theanalyst's travelling salesman problem.
Suppose are independent random variables with uniform distribution in the square, and let be the shortest path length (i.e. TSP solution) for this set of points, according to the usualEuclidean distance. It is known[9] that, almost surely,
where is a positive constant that is not known explicitly. Since (see below), it follows frombounded convergence theorem that, hence lower and upper bounds on follow from bounds on.
Thealmost-sure limit as may not exist if the independent locations are replaced with observations from a stationary ergodic process with uniform marginals.[44]
where 0.522 comes from the points near the square boundary which have fewer neighbours, and Christine L. Valenzuela andAntonia J. Jones obtained the following other numerical lower bound:[51]
The problem has been shown to beNP-hard (more precisely, it is complete for thecomplexity class FPNP; seefunction problem), and thedecision problem version ("given the costs and a numberx, decide whether there is a round-trip route cheaper thanx") isNP-complete. Thebottleneck travelling salesman problem is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane withEuclidean 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 in the planar case there is an optimal tour that visits each city only once (otherwise, by thetriangle inequality, a shortcut that skips a repeated visit would not increase the tour length).
In the general case, finding a shortest travelling salesman tour isNPO-complete.[52] If the distance measure is ametric (and thus symmetric), the problem becomesAPX-complete,[53] andthe algorithm of Christofides and Serdyukov approximates it within 1.5.[54][55][10]
If the distances are restricted to 1 and 2 (but still are a metric), then the approximation ratio becomes 8/7.[56] In the asymmetric case withtriangle inequality, in 2018, a constant factor approximation was developed by Svensson, Tarnawski, and Végh.[57] An algorithm byVera Traub andJens Vygen [de] achieves a performance ratio of.[58] The best known inapproximability bound is 75/74.[59]
The corresponding maximization problem of finding thelongest travelling salesman tour is approximable within 63/38.[60] If the distance function is symmetric, then the longest tour can be approximated within 4/3 by a deterministic algorithm[61] and within by a randomized algorithm.[62]
The TSP, in particular theEuclidean variant of the problem, has attracted the attention of researchers incognitive psychology. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient, for graphs with 10–20 nodes, to 11% less efficient for graphs with 120 nodes.[63][64] The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic.[65][66][67] However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to affect performance in the task.[68][69][70] Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems,[71] and have also led to new insights into the mechanisms of human thought.[72] The first issue of theJournal of Problem Solving was devoted to the topic of human performance on TSP,[73] and a 2011 review listed dozens of papers on the subject.[72]
A 2011 study inanimal cognition titled "Let the Pigeon Drive the Bus," named after the children's bookDon't Let the Pigeon Drive the Bus!, examined spatial cognition in pigeons by studying their flight patterns between multiple feeders in a laboratory in relation to the travelling salesman problem. In the first experiment, pigeons were placed in the corner of a lab room and allowed to fly to nearby feeders containing peas. The researchers found that pigeons largely used proximity to determine which feeder they would select next. In the second experiment, the feeders were arranged in such a way that flying to the nearest feeder at every opportunity would be largely inefficient if the pigeons needed to visit every feeder. The results of the second experiment indicate that pigeons, while still favoring proximity-based solutions, "can plan several steps ahead along the route when the differences in travel costs between efficient and less efficient routes based on proximity become larger."[74] These results are consistent with other experiments done with non-primates, which have proven that some non-primates were able to plan complex travel routes. This suggests non-primates may possess a relatively sophisticated spatial cognitive ability.
When presented with a spatial configuration of food sources, theamoeboidPhysarum polycephalum adapts its morphology to create an efficient path between the food sources, which can also be viewed as an approximate solution to TSP.[75]
For benchmarking of TSP algorithms, TSPLIB[76] 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 actualprinted circuits.
![[2]](/mt/?noimg=&dark=on&url=http%3a%2f%2fopenclipart.org%2fclipart%2f%2fgeography%2fcarte_de_france_01.svg){kind=link}