Abstract:

The traveling salesman problem （TSP） is a typical combination optimization problem, and possesses a practical application value. However, there is no effective corresponding solution to it today. So, in this paper, the traditionally affirmative methods and popular meta-heuristic methods are discussed. The advantages and disadvantages of each method are discussed. The future research direction of the TSP problem is also given.

Key words: traveling salesman problem, dynamic program, brand and bound, genetic algorithm, Gou Tao algorithm