Traveling Salesman Problem

Approximation Algorithms

Applet By Kreimer Natasha.

Problem:

A traveling salesman has to travel through a bunch of cities, in such a way that the expenses on traveling are minimized. This is the infamous Traveling Salesman Problem (aka TSP) problem (formal defintion). It belongs to a family of problems, called NP-complete problem. It is conjectured that all those problems requires exponential time to solve them. In our case, this means that to find the optimal solution you have to go through all possible routes, and the numbers of routes increases exponential with the numbers of cities.

If you want to get a notion of what numbers we are talking about look at this:
the number of routes with 50 cities is (50-2)!, which is

12,413,915,592,536,072,670,862,289,047,373,375,038,521,486,354,677,760,000,000,000

An alternative approach would be to compute a solution which is not optimal, but is guarenteed to be close the optimal solution. We present here an applet that implements such an approximation algorithm for the Euclidean TSP problem.

In our case we have points in the plane (i.e. cities) and the cost of the traveling between two points is the distance between them. In other words, we have a map with cities, any two of which are connected by a direct straight road (yeh, sure!) and we want to find a shortest tour for our poor traveling salesman, who "wants" to visit every city.

The applet implements the following approximation algorithms:

• x2 Algorithm - returns tour which is no worse than twice as long as an optimal tour.
• x1.5 Algorithm - returns tour which is no worse than one and half as long as an optimal tour.
• Iterative algorithn - Generate an arbitrary tour, and try iteratively to improve it locally. This algorithm does not have a performance guarantee. This algorithm can be run independently on input points or can be applied on output tours of above constant ratio bound algorithms.

The solution generated by those algorithms can be further improved by applying on it:

• Iterative algorithm for removing intersections in the tour - whenever there is an intersection, the tour can improved by "flipping" the tour.
• The iterative algorithm.

Description of Algorithms

x2 Algorithm:

• find Minimum Spanning Tree (MST).
• perform preoder tree walk on MST, and construct a list of the vertices as we encounter them. (i.e. each vertex will appear only one - corresponding to its first encounter)
• the output tour is hamiltonian cycle that visits the vertices in order of this list.

The running time of this algorithm is O(n2log(n)) time ,since the input is a complete graph (n is the number of inserted points).

The lenght of the resulting tour is at most twice of the optimal tour, since its lenght is at most twice that of the MST, and the optimal tour is longer than the MST.

x1.5 Algorithm:

• find Minimum Spanning Tree (MST).
• find minimum weighted matching between odd vertices of MST.
• find an Euler tour in resulting graph and create list of vertices that represents it.
• find Hamilton cycle (which is in fact TSP tour) by visiting vertices in order of created list when only first appearance of vertex in list is encountered and any other appearance is skipped.
The approximation ratio bound is 1.5, although the argument here is a bit more complicated.
Note: This applet doesn't actually implement minimum weighted matching but uses an approximation method (which can be used directly on the input points by clicking "Match points").

Iterative Algorithm:

We generated an arbitrary initial solution, by visiting all points in order they were inserted.
Then in each iteration:

1. Select two random cities
2. Interchange the two cities predecessors
3. Calculate the weight of resulting tour.
4. If new weight is smaller then old one - if so, replace the old tour by the new tour, else undo (2).

Removing Intersections Scheme:

This algorithm is applied on already computed TSP tour. It performs a loop which stops only after all intersections have been removed (which must happen after at most n2times).
Each loop goes through all the pairs of edges in the tour and checks if they intersect.
- If so then two new edges will replace them. New edges created by interchanging the original edge's endpoints. To preserve TSP tour completeness the path between the original edges is reversed.

The Applet:

How to use the applet?
Source code