Editing Travelling salesman problem (section)

==Special cases==

===Metric===
<!-- linked from redirect [[Metric TSP]] -->
In the ''metric TSP'', also known as ''delta-TSP'' or Δ-TSP, the intercity distances satisfy the [[triangle inequality]].

A very natural restriction of the TSP is to require that the distances between cities form a [[metric (mathematics)|metric]] to satisfy the [[triangle inequality]]; that is, the direct connection from ''A'' to ''B'' is never farther than the route via intermediate ''C'':
:<math>d_{AB} \le d_{AC} + d_{CB}</math>.

The edges then build a [[metric space|metric]] on the set of vertices. When the cities are viewed as points in the plane, many natural [[distance function]]s are metrics, and so many natural instances of TSP satisfy this constraint.

The following are some examples of metric TSPs for various metrics.
*In the Euclidean TSP (see below), 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 absolute values of the differences of their ''x''- and ''y''-coordinates. This metric is often called the [[Manhattan distance]] or city-block metric.
*In the [[maximum metric]], the distance between two points is the maximum of the absolute values of differences of their ''x''- and ''y''-coordinates.

The last two metrics appear, for example, in routing a machine that drills a given set of holes in a [[printed 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 <math>d_{AB}</math> is replaced by the [[shortest path]] length between ''A'' and ''B'' in the original graph.

===Euclidean===
<!-- linked from redirect [[Euclidean TSP]] -->
For points in the [[Euclidean plane]], the optimal solution to the travelling salesman problem forms a [[simple polygon]] through all of the points, a [[polygonalization]] of the points.<ref>{{cite journal
 | last1 = Quintas | first1 = L. V.
 | last2 = Supnick | first2 = Fred
 | doi = 10.2307/2313333
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2313333
 | mr = 188872
 | pages = 977–980
 | title = On some properties of shortest Hamiltonian circuits
 | volume = 72
 | year = 1965| issue = 9
 }}</ref> Any non-optimal solution with crossings can be made into a shorter solution without crossings by local optimizations. The [[Euclidean 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 of [[square root]]s, and the length of a tour is a [[sum of radicals]], making it difficult to perform the [[symbolic 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.{{sfnp|Papadimitriou|1977}} With rational coordinates and the actual Euclidean metric, Euclidean TSP is known to be in the Counting Hierarchy,{{sfnp|Allender|Bürgisser|Kjeldgaard-Pedersen|Mitersen|2007}} 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.{{sfnp|Larson|Odoni|1981}} For example, the minimum spanning tree of the graph associated with an instance of the 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.

In general, for any ''c'' > 0, where ''d'' 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

:<math>O{\left(n (\log n)^{O(c \sqrt{d})^{d-1}}\right)}</math>

time; this is called a [[polynomial-time approximation scheme]] (PTAS).{{sfnp|Arora|1998}} [[Sanjeev Arora]] and [[Joseph S. B. Mitchell]] were awarded the [[Gö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.

===Asymmetric===
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 optimization using street-level routing (which is made asymmetric by one-way streets, slip-roads, motorways, etc.).

The [[stacker 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.

====Conversion to symmetric====
Solving an asymmetric TSP graph can be somewhat complex. The following is a 3×3 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 2''N''.<ref>{{cite journal | last1 = Jonker | first1 = Roy | last2 = Volgenant | first2 = Ton | title = Transforming asymmetric into symmetric traveling salesman problems | journal = [[Operations Research Letters]] | volume = 2 | issue = 161–163| page = 1983 | doi = 10.1016/0167-6377(83)90048-2 | year = 1983 }}</ref>

:{| class="wikitable"
|- style="text-align:center;"
|+ Asymmetric path weights
! !! ''A'' !! ''B'' !! ''C''
|- style="text-align:center;"
! ''A''
| || 1 || 2
|- style="text-align:center;"
! ''B''
| 6 || || 3
|- style="text-align:center;"
! ''C''
| 5 || 4 ||
|}

To double the size, each of the nodes in the graph is duplicated, creating a second ''ghost 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.

:{| class="wikitable"
|- style="text-align:center;" class="wikitable"
|+ Symmetric path weights
! !! ''A'' !! ''B'' !! ''C'' !! ''A&prime;'' !! ''B&prime;'' !! ''C&prime;''
|- style="text-align:center;"
! ''A''
| || || || −''w'' || 6 || 5
|- style="text-align:center;"
! ''B''
| || || || 1 || −''w'' || 4
|- style="text-align:center;"
! ''C''
| || || || 2 || 3 || −''w''
|- style="text-align:center;"
! ''A&prime;''
| −''w'' || 1 || 2 || || ||
|- style="text-align:center;"
! ''B&prime;''
| 6 || −''w'' || 3 || || ||
|- style="text-align:center;"
! ''C&prime;''
| 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 <math>\scriptstyle{A \to A' \to C \to C' \to B \to B' \to A}</math>), and by merging the original and ghost nodes again we get an (optimal) solution of the original asymmetric problem (in our example, <math>\scriptstyle{A \to C \to B \to A}</math>).

===Analyst's problem===
There is an analogous problem in [[geometric measure theory]] which asks the following: under what conditions may a subset ''E'' of [[Euclidean space]] be contained in a [[rectifiable curve]] (that is, when is there a curve with finite length that visits every point in ''E'')? This problem is known as the [[analyst's traveling salesman theorem|analyst's travelling salesman problem]].

===Path length for random sets of points in a square===
Suppose <math>X_1,\ldots,X_n</math> are <math>n</math> independent random variables with uniform distribution in the square <math>[0,1]^2</math>, and let <math>L^\ast_n</math> be the shortest path length (i.e. TSP solution) for this set of points, according to the usual [[Euclidean distance]]. It is known{{sfnp|Beardwood|Halton|Hammersley|1959}} that, almost surely,

::<math>\frac{L^*_n}{\sqrt n}\rightarrow \beta\qquad\text{when }n\to\infty,</math>

where <math>\beta</math> is a positive constant that is not known explicitly. Since <math>L^*_n\le2\sqrt n+2</math> (see below), it follows from [[bounded convergence theorem]] that <math>\beta=\lim_{n\to\infty} \mathbb E[L^*_n]/\sqrt n</math>, hence lower and upper bounds on <math>\beta</math> follow from bounds on <math>\mathbb E[L^*_n]</math>.

The [[Almost surely|almost-sure]] limit <math>\frac{L^*_n}{\sqrt n}\rightarrow \beta</math> as <math>n\to\infty</math> may not exist if the independent locations <math>X_1,\ldots,X_n</math> are replaced with observations from a stationary ergodic process with uniform marginals.<ref name="as2016">{{citation
 | doi = 10.1214/15-AAP1142
 | last1 = Arlotto | first1 = Alessandro
 | last2 = Steele | first2 = J. Michael | author2-link = J. Michael Steele
 | journal = The Annals of Applied Probability 
 | pages = 2141–2168
 | title = Beardwood–Halton–Hammersley theorem for stationary ergodic sequences: a counterexample
 | volume = 26
 | issue = 4
 | year = 2016| arxiv = 1307.0221| s2cid = 8904077 }}</ref>

====Upper bound====
*One has <math>L^*\le 2\sqrt{n}+2</math>, and therefore <math>\beta\leq 2</math>, by using a naïve path which visits monotonically the points inside each of <math>\sqrt n</math> slices of width <math>1/\sqrt{n}</math> in the square.
*Few<ref>{{cite journal|last1=Few|first1=L.|title=The shortest path and the shortest road through n points|journal=[[Mathematika]]|date=1955|volume=2|issue=2|pages=141–144|doi=10.1112/s0025579300000784 }}</ref> proved <math>L^*_n\le\sqrt{2n}+1.75</math>, hence <math>\beta\le\sqrt 2</math>, later improved by Karloff (1987): <math>\beta\le0.984\sqrt2</math>.
* Fietcher<ref>{{cite journal|last1=Fiechter|first1=C.-N.|title=A parallel tabu search algorithm for large traveling salesman problems|journal=Disc. Applied Math.|date=1994|volume=51|issue=3|pages=243–267 |doi=10.1016/0166-218X(92)00033-I|doi-access=free}}</ref> empirically suggested an upper bound of <math>\beta\le 0.73\dots</math>.

====Lower bound====
*By observing that <math>\mathbb E[L^*_n]</math> is greater than <math>n</math> times the distance between <math>X_0</math> and the closest point <math>X_i\ne X_0</math>, one gets (after a short computation)

::<math>\mathbb E[L^*_n]\ge\tfrac{1}{2} \sqrt{n}.</math>

*A better lower bound is obtained by observing that <math>\mathbb E[L^*_n]</math> is greater than <math>n/2</math> times the sum of the distances between <math>X_0</math> and the closest and second closest points <math>X_i,X_j\ne X_0</math>, which gives{{sfnp|Beardwood|Halton|Hammersley|1959}}

::<math>\mathbb E[L^*_n]\ge \bigl(\tfrac14 + \tfrac38\bigr)\sqrt{n} = \tfrac{5}{8}\sqrt{n},</math>

*The currently-best{{When|date=April 2024}} lower bound is{{sfnp|Steinerberger|2015}}
::<math>\mathbb E[L^*_n]\ge \bigl(\tfrac58 + \tfrac{19}{5184}\bigr)\sqrt{n},</math>

*Held and Karp gave a polynomial-time algorithm that provides numerical lower bounds for <math>L^*_n</math>, and thus for <math>\beta(\simeq L^*_n/{\sqrt n})</math>, which seem to be good up to more or less 1%.<ref>{{cite journal|last1=Held|first1=M.|last2=Karp|first2=R.M.|title=The Traveling Salesman Problem and Minimum Spanning Trees|journal=Operations Research|date=1970|volume=18|issue=6|pages=1138–1162 |doi=10.1287/opre.18.6.1138 }}</ref><ref>{{cite journal
| last1=Goemans | first1=Michel X. | authorlink1=Michel Goemans
| last2=Bertsimas | first2=Dimitris J. | authorlink2=Dimitris Bertsimas
| title=Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem
| journal=[[Mathematics of Operations Research]]
| date=1991
| volume=16
| issue=1
| pages=72–89
| doi=10.1287/moor.16.1.72}}</ref> In particular, David S. Johnson obtained a lower bound by computer experiment:<ref>{{cite web|url=https://about.att.com/error.html|title=error |website=about.att.com}}</ref>

::<math>L^*_n\gtrsim 0.7080\sqrt{n}+0.522,</math>

where 0.522 comes from the points near the square boundary which have fewer neighbours, and Christine L. Valenzuela and [[Antonia J. Jones]] obtained the following other numerical lower bound:<ref>[http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf Christine L. Valenzuela and Antonia J. Jones] {{webarchive|url=https://web.archive.org/web/20071025205411/http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf |date=25 October 2007 }}</ref>
::<math>L^*_n\gtrsim 0.7078\sqrt{n}+0.551</math>.