A New Hybrid Algorithm for Solving TSP

The traveling salesman problem (TSP) is one of the typical NP—Hard problems in combinatorial optimization. This paper proposes a new algorithm named hybrid NN&IN heuristics algorithm based on analyzing the advantages and disadvantages of NN (the nearest neighbor) and IN (insertion) algorithm for solving the traveling salesman problem. In addition, the paper also analyzes the rationality and parameter setting of the hybrid algorithm and proved that it has good performance with respect to the quality of solution and the speed of computation by using probabilistic method. Finally, many benchmark examples from TSPLIB (traveling salesman problem library) were solved with NN, NN&IN, IN algorithms respectively. The experimental results show that the hybrid algorithm is more effective and efficient than both NN and IN algorithm.