Travelling salesman problem

Given finitely many locations and pairwise travel costs, find a cyclic visiting order minimizing the sum of its costs. For Euclidean distance this becomes the Euclidean travelling salesman tour problem.

Minimizing ${\sum }_{ij}{c}_{ij}{x}_{ij}$ over binary variables with one outgoing and one incoming edge at every graph vertex, and $x_{ii}=0$, is an assignment problem. Its feasible solutions are cycle covers of a directed graph, whereas a travelling salesman problem requires one Hamiltonian cycle. The relaxed minimum is therefore a lower bound on the tour cost. If its optimum contains a proper subtour $C$, every tour omits at least one edge of $C$. Branching into subproblems that respectively forbid each edge of $C$ preserves every possible tour. Solving each child assignment problem and pruning those whose bounds exceed the best tour yields a finite branch and bound algorithm. Equality also permits pruning when only one optimum is wanted.

A 2-opt tour move removes two boundary arcs and reverses the intervening block to reconnect one tour. Such moves define a local-search neighbourhood; block reversals of length two include adjacent swaps and hence connect permutation schedules. For directed costs the asymmetric 2-opt reversal cost must include every reversed internal arc, not just the boundary changes.

A 2-opt schedule move reverses a consecutive block $v_p,\dots ,v_q$, reconnecting its boundary arcs. With directed costs, its change isOmitting the internal sum is valid only for symmetric costs. A simulated annealing step accepts an increase with probability $\exp (-\Delta /T)$; a strictly positive temperature permits escape from local minima.

Add a dummy job $0$. Give the arc $0\to i$ cost equal to job $i$'s initial setup, the arc $i\to j$ its changeover cost, and every arc $i\to 0$ zero cost. A Hamiltonian cycle through the dummy represents a schedule, starting just after $0$ and ending just before it. The total processing time is constant on a single machine, so minimizing cycle cost minimizes completion time. Dropping subtour elimination constraints gives an assignment problem lower bound.

Binary arc variables with one outgoing and one incoming arc at each vertex describe a cycle cover of a directed graph. For every nonempty proper vertex subset $S$, the displayed inequality forbids a directed cycle confined to $S$. Together these inequalities make the cycle cover one Hamiltonian cycle. They can be generated as violated cuts or used in branch and bound, rather than all being stored initially.

Use binary directed-edge variables $x_{ij}$, one incoming and one outgoing edge at each city, and integer order variables $1\le u_i\le n-1$ for cities other than a distinguished city. The constraints $u_i-u_j+(n-1)x_{ij}\le n-2$ for distinct nondistinguished cities force order increase along every selected edge away from the distinguished city. Summing around any cycle avoiding that city gives a contradiction, so the degree equations describe a single tour. There are $O(n^2)$ nonzero constraint entries apart from the degree equations, also totaling $O(n^2)$ entries. With costs at most $2^n$, the objective requires $O(n^3)$ bits and the remaining sparse constraint encoding $O(n^2\log n)$ bits. Omitting zero matrix entries is essential for this particular size bound.

Find a maximum-weight Hamiltonian cycle in a complete weighted graph or complete directed graph. Nonnegative weights admit a cycle-cover patching half-approximation for Max-TSP without a triangle inequality. For integer weights, changing $c_{ij}$ to $M-c_{ij}$, with $M\ge \max c_{ij}$, changes an $n$-vertex tour's weight from $C$ to $nM-C$. Consequently the strict-threshold decision version is NP-complete: minimum-tour threshold $C\le L$ becomes maximum-tour threshold $C^{\prime }>nM-L-1$.

Solve the maximum-weight assignment problem forbidding fixed points, obtaining a cycle cover of a directed graph whose weight bounds every Hamiltonian cycle above. Remove a lightest edge from each graph cycle. Each graph cycle has at least two edges, so at least half its nonnegative weight survives. Connect the resulting disjoint graph paths cyclically; completeness supplies the connectors and their nonnegative weights cannot reduce the retained sum. The Hungarian algorithm and linear-time patching give a polynomial time approximation algorithm. Negative weights invalidate a universal multiplicative half guarantee: when every weight is $-1$, every tour has weight $-n<(-n)/2$.

This is the travelling salesman problem on a complete graph with nonnegative symmetric distances satisfying the triangle inequality. Repeated visits can be shortcut without increasing cost. Assigning distance one to edges of an input graph and two to its nonedges creates a metric instance with a tour of cost at most the number of vertices exactly when the graph has a Hamiltonian cycle. Thus the metric problem remains NP-hard.

Double every edge of a minimum spanning tree to obtain a connected even-degree multigraph, traverse an Euler circuit, and shortcut repeated vertices. The triangle inequality prevents any shortcut from increasing cost. Deleting an edge of an optimal tour gives a spanning tree, so the minimum spanning tree has cost at most the optimal tour. The returned tour therefore costs at most twice optimum and is computable in polynomial time. In the relative-error convention this is an error-one approximation.

Compute a minimum spanning tree, then a minimum-weight perfect matching on its odd-degree vertices. Their multiset union is connected with even degrees, so it has an Euler circuit. Shortcut repeated vertices to obtain a metric tour. The tree costs at most the optimal tour, and shortcutting the optimal tour to its odd-degree subset gives a cyclic order whose alternating matchings show that the added matching costs at most half the optimum. The result is a polynomial-time $3/2$-approximation algorithm for symmetric metric instances.

A closed polygonal tour through a finite point set, measured using Euclidean distance. Write $\mathrm{TS}(X)$ for the minimum length over cyclic visiting orders. A two-point tour traverses its segment twice; a one-point tour has length zero. The triangle inequality allows repeated visits to be shortcut when estimating this minimum.

For every configuration $x$ in the unit square there are nonnegative weights $a_i(x)$ such that ${\sum }_i{a}_i(x{)}^2\le 16$ andUse the sums of the two incident edge lengths in a tour from the squared edge bound for tours in the unit square. Runs of missing vertices can be added by the cheaper of two out-and-back detours. This connects Euclidean travelling salesman tours to Talagrand's convex distance inequality.

Every finite point set in the unit square admits a cyclic visiting order with ${\sum }_i\Vert x_{i+1}-x_i{\Vert }^2\le 4$. Split the square into two right triangles, apply the quadratic path bound in a right triangle, and remove auxiliary corners using the law of cosines. The Cauchy-Schwarz inequality then gives $\mathrm{TS}(X)\le 2\sqrt{|X|}$. The tour minimizing ordinary length need not minimize the sum of squared lengths.

Given finitely many points in a right triangle with hypotenuse endpoints $a,b$, there is a path from $a$ to $b$ visiting them all with sum of squared edge lengths at most $\Vert a-b{\Vert }^2$. Repeated altitude subdivision reduces to cells containing one point. Joining the child paths preserves the squared-cost bound by the Pythagorean theorem; deleting an auxiliary right-angle vertex preserves it by the law of cosines.