The travelling salesman problem is a classical problem in operations research that involves a travelling salesman who has to visit N number of cities. Here we are faced with the problem of determining the shortest path that he requires to traverse. This problem does not have a polynomial time solution as the complexity of determining the shortest path increases as a function of factorial N for large values of N.

A computer that is assigned the task of finding out the shortest path from a set of different possible tours will not be able to compute the shortest path for very large values of the number of cities. The complexity of algorithms are classified as exponential, polynomial, logarithmic etc., the complexity of the TSP is a function of factorial (n).

Let us illustrate with an example. For a tour of 3 cities the no of possible combinations is 6. Here in the list below is shown the no of possible tours vs the no of cities in the tour

4 city tour = no. of possible tours is 24

5 city tour = the no. of possible tours is 120

6 city tour = the no. of possible tours is 720

7 city tour = the no. of possible tours is 5040

8 city tour = the number of possible tours is 40320

9 city tour = the number of possible tours is 362880

10 city tour = the number of possible tours is 3628800

As it can be seen easily the number of computations required by a computer to determine the shortest path increases to 362880 for a tour of just 9 cities and for a 50 city tour the complexity increases to 3.04141E+64.

So a computer just cannot process so many instructions within finite time for larger and real life requirements. The processing power available in modern day computers would take trillions of years to find a solution to Travelling Salesman Problem for an input value (no of cities) say equal to 100.

The TSP can be solved using Linear Programming/Integer Linear Programming formulations and using Simplex or Cutting Plane methods.

Instead of using a brute force technique one can reduce the number of possible tours by using dynamic programming. One can also solve the TSP using heuristics.

The TSP is considered to NP -Hard or in other words there is no general solution to this problem unless it is proved that P =NP.



Source by Srinivasa Gopal