**The Problem**

The traveling salesman problem (TSP) is a typical example of a very hard combinatorial optimization problem. The problem is to find the shortest tour that passes through each vertex in a given graph exactly once. The TSP problem is classified as an NP-complete problem. There are some intuitive methods to find the approximate solutions, but all of these methods have exponential complexity, they take too much computing time or require too much memory. Mathematically TSP can be expressed as:

*min [f(T),T = (T[1],T[2],T[3],… …,T[n])]*

The search space for the TSP is a set of permutations of n cities. Any single permutation of n cities yields a solution (which is a complete tour of n cities). The optimal solution is a permutation which yields the minimum distance of the tour. The size of the search space is n!. This massive search space quickly becomes unsearchable as the number of vertices or nodes in the map increases.

Number of Nodes (cities) | Number of Possibilities | Computation Time |
---|---|---|

5 | 12 | 12 μs |

10 | 181440 | 0.18 ms |

15 | 43 billion | 12 hours |

20 | 60E15 | 1928 years |

25 | 3.1E23 | 9.8 billion years |

Advertisements