Home Bookmarks Papers Blog

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:

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


Description of Algorithms

x2 Algorithm:

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:

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
Back to the Workshop home page