Travelling salesman problem

Travelling salesman problem is a problem of combinatorial optimization. The goal of the travelling salesman is to find a cycle in a complete weighted graph, which goes through all its vertices and its cost is minimal. More formally: to find a minimal Hamiltonian circuit in a complete weighted graph.

Motivation

There are many cities in the given country and the travelling salesman has to visit all of them and return to his family in the original city. There are roads built among all the cities on the map and the salesman wants to choose such a path that will be cheapest for him.

Complexity

The problem is NP-complete and strongly NP-hard, which means that if $P \\neq NP$ holds, than for the travelling salesman problem does not exist any k-approximation algorithm – there is no algorithm, which is polynomial and always return a solution, which is in the worst case k times suboptimal.

ILP formulation

The asymmetric travelling salesman problem can be formulated using integer linear programming. Asymmetric means that the weight of path from $A \\rightarrow B$ may be different than $B \\rightarrow A$ .

$\\min \\sum_{i=1}^{n} \\sum_{j=1}^{n} x_{ij} \\cdot c_{ij}$
Subject to:
$\\sum_{i = 1}^{n} x_{ij} = 1 \\hspace{20mm} j \\in \\{1, \\cdots, n\\}$
$\\sum_{j = 1}^{n} x_{ij} = 1 \\hspace{20mm} i \\in \\{1, \\cdots, n\\}$
$s_{i} + c_{ij} - (1-x_{i, j}) \\cdot M \\leq s_{j} \\hspace{20mm} i \\in \\{1, \\cdots, n\\} \\;\\; j \\in \\{2, \\cdots, n\\}$
$x_{ij} \\in \\{0, 1\\}$

The first two conditions guarantee that each node will be visited exactly once. The third one non-divisibility of the resulting Hamiltonian path (the path can not form more than one cycle).

Metric travelling salesman

Metric travelling salesman is a modification of the original problem, in which the distances within the graph respect the triangle inequality. This simplification, which resembles many real problems (distances on a map also respect the triangle inequality), makes it possible to construct k-approximation algorithms.

2-approximation algorithm

Problem of the metric travelling salesman problem can be easily solved (2-approximated) in a polynomial time. At first the algorithm constructs a minimum spanning tree of the graph. From the definition of a minimal spanning tree it arises that $price(spanning \\; tree) \\leq price(optimal \\; solution)$ , because the spanning tree contains $\\vert V \\vert - 1$ edges, while the cycle $\\vert V \\vert$ .

Then the algorithm traverses the spanning tree from arbitrary node using depth first search and memorizes all traverses through individual nodes – from the nature of depth first search it comes that some nodes will be processed more than once.

In the last step – compression of paths – the algorithm walks through the list of nodes created in the previous step and removes duplicities (keeps in the list only first occurrences of each node). This way a cycle is created. Because the graph respects triangle inequality, the weight of the path is no more than twice as long as the original spanning tree.

$price(cycle) \\leq 2 \\cdot price(spanning \\; tree) \\leq 2 \\cdot price(optimal \\; solution)$

Example

2-approximation algorithm - example

The left part of the illustration shows a graph and its minimum spanning tree, which can be constructed using Kruskal's algorithm. Then the spanning tree was traversed using depth first search from node . The algorithm returned the following sequence of nodes: A, B, A, D, E, D, A, C, A . In the last step the paths were contracted in order to create a cycle A, B, D, E, C .

Christofides algorithm

Christofides algorithm solves the problem of metric travelling salesman in such a way that the resulting cycle is at most 1.5 times longer than the optimal one. This improvement is paid back by substantially more difficult implementation in comparison to the 2-approximation algorithm. Also experiments using real data show that these two algorithms produce in average comparable solutions.

Similarly to the 2-approximation algorithm the Christofides procedure at first constructs a minimal spanning tree of the graph. Than it traverses from the arbitrary node using depth first search and constructs a new complete graph from nodes with odd degree. Then the procedure finds minimum perfect matching of graph and adds edges from into the spanning tree. The graph $K \\cup P$ is now Eulerian (there exists a trail which goes through all nodes of this graph). Finally the procedure finds Eulerian trail – the resulting path corresponds with the order of first visits of each node.