Optimization Research Of Traveling Salesman Problem Based On Improved Ant Colony Algorithm

Traveling Salesman Problem(TSP)has always been a research hotspot of combinatorial optimization problems in the field of operations research.Its basic characteristics are easy to describe and difficult to solve,so it is a typical NP-hard Problem.Problems such as production planning and scheduling,production scheduling,integrated circuit design,logistics scheduling and transportation,computer network wiring and so on can be abstracted into the TSP model to solve.In view of above fact,the study of traveling salesman problem is of great significance.In recent years,great progress has been made in the study of classical traveling salesman problem.The solving time of traveling salesman problem is decreasing and the quality of solution is improving.However,the explosion of the solution space caused by the increase of the scale of the traveling salesman problem is one of the most serious problem.Under the reasonable time cost,most of the traveling salesman problem still can only search for the approximate optimal solution,and cannot converge to the optimal optimal solution.Under this background,In this paper,the main research contents is improving low precision and slow speed of solving TSP.(1)In order to solve the problem that ant colony algorithm can not accurately distinguish the contribution of different subpaths in the process of path construction,this paper take advantage of ant colony algorithm with strengthened negative feedback mechanism to solve TSP.Besides,subpaths length is viewed as a factor in the process of incremental calculation to improve its pheromone incremental calculation,which would clearly distinguish different subpaths' s contribution in the building process of global optimal solution and would provide more precise guidance.At the same time,according to the randomness of the ant colony algorithm when selecting points,the improved variable neighborhood search algorithm is combined to optimize the output results of the strengthened subpath identifying ant colony algorithm,so that it can quickly converge to the global optimal.(2)Given that ant colony algorithm repeatedly searches part of mutual subpaths and wastes computational resources when solving traveling salesman problem.In order to solve this problems,three local optimal solutions were compared and decomposed to extract the fragments that may exist in the global optimal solution,and these fragments are reorganized by using the strengthened subpath identifying ant-colony algorithm.At the same time,the variable neighborhood search algorithm is used for optimization to obtain a better solution.Finally,the above algorithm is tested on a standard test example.Experimental results show that the above solutions have obvious advantages in running time compared with other solutions.However,compared with the strengthened subpath identifying ant colony algorithm,the accuracy of the solution is reduced.