Abstract: In the traditional traveling salesman problem (TSP) models,the number of sub-tour elimination constraints exponentially increases with an increase in the size of the problem,which considerably limits the efficiency of solving the TSP.Based on the TSP relaxation problems,a method has been proposed in this study to effectively generate sub-tour elimination constraints.Further,the proposed method achieves an accurate and quick solution of TSP by solving the linear integer programming series.The numerical results denote that when compared with the Cplex direct solution,the proposed method can obtain the optimal solution of TSP more rapidly.

Key words: traveling salesman problem, sub-tour elimination constraints, relaxation method, linear integer programming