Research And Application Of Traveling Salesman Problem

Travelling Salesman Problem(TSP)is a classic combinatorial optimization problems,which is widely used in practice.At the same time TSP is a NP-hard problem.Therefore,we can only solve the small-scale TSP,for large-scale TSP solver,scholars keep searching a best approximation algorithm which can converge to the optimal solution quickly.In addition,according to the problems in different fields of application,many extension problems are derived from TSP,this thesis mainly discusses the two types of TSP extension problem: multiple traveling salesman problems(MTSP),and the dynamic traveling salesman problem(DTSP).For the extension of these two types of TSP,the improved genetic algorithm and its fusion algorithm are proposed.The main research work and innovation are as follows:(1)MTSP is a computationally complex combinatorial optimization problem.We propose the two phase heuristic algorithm(TPHA)for MTSP.In the first phase,we improve the k-means algorithm by adding the capacity constraints to divide all cities into m city sets according to the locations of cities.In the second phase,the route planning algorithm based on genetic algorithm(GA)is designed to realize the ideal route for each city set.Particularly,we combine the roulette wheel method and the elitist strategy to design the selection operation of GA.Experimental results show that TPHA can realize the workload balance and the minimization of the overall traveling distance of salesmen,and has the better performance in solving MTSP than the route planning algorithm based on GA.(2)DTSP is an extension of TSP.It is analyzed that DTSP is caused by the change of the number of cities and the change of the cost value.The mathematical model of DTSP is pointed out,and the simulation model based on TSPLIB is established to reproduce the complex situation of DTSP.This thesis presents a genetic algorithm based on two sides correction method(TSC-GA),this algorithm combines the global search ability of GA and the fast convergence ability of the two sides correction method,which makes it possible to find a satisfactory solution in a short time.Through the realization of the algorithm in the simulation platform to verify the algorithm,the solution quality and solving speed are greatly improved.(3)A prototype system is constructed based on Baidu map,MTSP will be used in tourism route planning,the system through the GPS module to locate the location of tourists,then the route planning module is used to cluster the selected scenic spots for the path planning,schedule a tour for a few days’ trip.DTSP will be used in the supermarket distribution of the scene,the supermarket distribution according to the vehicle arrived at a supermarket distribution point,according to the real-time traffic information,adjust the route,save the delivery time.