Editing Travelling salesman problem (section)

===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>).