Research On Stochastic Heuristic Algorithm For Traveling Salesman Problem

Given a set of cities along with the cost of travel between each pair of them,the traveling salesman problem,or TSP for short,is to find the cheapest way of visiting all the cities and returning to the starting point.Traveling salesman problem is a classic combinatorial optimization problem,which has been discussed for many years since 1930 s.Actually,from the early traveling salesman sales to the current genome sequencing and so on,it all involves travelling salesman problem,which has a wide range of application scenarios.A better solution to the problem of traveling salesman will bring great economic value to enterprises and the society.The traveling salesman problem is an NP(non-deterministic polynomial)problem,which cannot be solved exactly in the polynomial time.However,the problem model is simple and easy to understand.It can be considered as a traveling salesman problem,when other NP problems are necessary to be solved as priority.Therefore,the solution of traveling salesman problem will promote the development of the theory to the NP problem.The traditional tree algorithm for the TSP is based on the minimum spanning tree.However,the optimal circle path may not be based on the minimum spanning tree like the traditional tree algorithm,which may lead to the failure to obtain a better solution,no matter how the minimum spanning tree is traversed.Based on this,in this paper,an improved algorithm was put forward in accordance with the idea of traditional tree algorithm,and carried on the experiment comparison,analyzed the performance of the algorithm,and finally,designed the corresponding web program.The main work of this paper is as follows:(1)An improved algorithm,multi-spanning tree algorithm(MSTA),was proposed based on the traditional tree algorithm.It could generate multiple spanning trees instead of original one tree,and then traverse the spanning trees to obtain the travel path.The theoretical analysis is also carried out to prove the feasibility and effectiveness of the multi-spanning tree algorithm in terms of the time complexity and space complexity.(2)Three different data sets,including C-TSP data set,small data set and large data set,were selected to compare nine algorithms,including genetic algorithm,ant colony algorithm,traditional tree algorithm,multiple spanning tree algorithm,particle swarm optimization algorithm,2-OPT method,nearest neighbor method,greedy method and simulated annealing algorithm,the performance of various algorithms is evaluated comprehensively by using three indexes of running time,algorithm stability and algorithm result.After analysis,the multi-spanning tree algorithm can effectively solve the problem of Chinese traveling salesman.The bionic algorithm has a good performance on the small data sets.And the experimental results of the multi-spanning tree algorithm and the nearest neighbor algorithm are relatively good on the large data sets.(3)A web application program based on the multi-spanning tree algorithm is designed by using python language.Taking the actual data of the logistics distribution system as an example,the system functions are demonstrated and the practical value of the research on the algorithm is verified.