TSP (TRAVELING SALESMAN PROBLEM)

By GrMikeD

E-mail: GrMikeD@usa.net

Web Page: http://students.ceid.upatras.gr/~miatidis

Introduction

The TSP (Traveling Salesman Problem) is considered as one of the most difficult to solve problems and belongs to the category of the NP Complete problems. The situation it deals with is as follows:

A salesman has to visit n cities, each one exactly once. He starts from one of them (base city) and after visiting all the other, he returns to his base. We know the transport cost between any two of the cities. We want to find the optimal path for his visits. When we say the optimal we mean the path with the lowest cost.

This is a famous problem of the graph theory where the vertices of the graph represent the cities and the nodes, represent the paths between them. When there is no node connecting two vertices, it means that there is no way to reach one city from the other. Here, we assume that only one path can connect two cities and no more (the graph is simple).

For this problem we have implemented two algorithms. One is the heuristic and the other is the exhaustive. The heuristic algorithm does not always give us the best solution but is very quick and low costing. Contrary to the heuristic algorithm, the exhaustive always gives us the best solution but is very slow and resource - consuming. For example if we use 20 cities as input and run the exhaustive algorithm on the most powerful and modern computing system, it will spend 770 centuries to give us the solution! In practice, we find that for input n>=10, the algorithm is very slow.

Analysis of the Heuristic Algorithm

This algorithm is based on the “greedy method”. As we have mentioned earlier, this algorithm succeeds in approaching a fast solution rather than the optimal solution. In some cases, it is possible that it will give us a solution very distant from the optimal one. Its basic advantage is that it is very quick. The basic idea of the algorithm is as follows: we start from the base city and after calculating its distance with its neighboring cities we select the city with the smallest distance. We then continue the same way for the next city and all the others until we have visited all the cities. We should emphasize that because we have assumed that a city might not be connected with another, this algorithm may come across a dead end. In such a case, it   finishes unsuccessfully.

Lets suppose that the salesman has to visit n cities. For the first city the algorithm makes (n-1) comparisons. After selecting the second city, it makes other (n-2) comparisons (as we have already selected one and it cannot be selected again) and so goes on until we reach the (n-1) city when the algorithm finishes. We can say that the complexity of the algorithm is:

 δ_n = (n-1) + (n-2) + (n-3) +…+ 0 + c= (n²- n)/2 + c .

As we can see the complexity is polynomial Ο (n²).

Analysis of the Exhaustive Algorithm

Here we start from the base city and we try all the possible paths that exist. We calculate their costs and we output the path with the lowest cost. In the implemented algorithm, we take a couple of the paths and find the lowest costing one. After we compare it with another one and find the lowest costing between them. We go on the same way until we have compared and with the last one.

It is obvious that the number of the possible paths is the number of the permutations of the n cities that is (n-1)! . We also find that for each of the    (n-1)! comparisons we make 2n operations approximately. We can say that the complexity of the algorithm is:

δ_n = (n-1)!(2n) + c = 2n! + c

As we can see the complexity is factorial Ο (n!).

Practical Calculations

Here are some practical results taken from the TspSolver program:

As we can see, for the heuristic algorithm, the flops and time values remain in low levels. In contrast, for the exhaustive algorithm they increase very quickly as the input n value increases. For values of n over 9 the exhaustive algorithm is extremely slow.