Research And Application Of Approximation Algorithm For Multiple Traveling Salesman Problem

the multiple traveling salesman problem (M-TSP) is one of the typical problems on the field of combinatorial optimization, deriving from the Traveling salesman problem,which is a significance research issue on the field of artificial intelligence. the characteristics of Multiple traveling salesman problem conform many practical problems, and the uncertainty of Multi-objective Traveling Salesman problem that we confront,requires system adjust mission planning timely, and the computation complexity should be as low as possible. Also the limited computing system is not enough to achieve the complexity process.So studing a new method to resolve this promblem is necessary.Based on the model of the processing and analysis of community structure, designing a kind of Multi-objective Traveling Salesman problem Mission Planning Algorithm and promoting to A kind of mission planning algorithm with multidepot multisalesmen problem, obtaining remarkable optimization results applied in Ad hoc network.The major work of this paper can be summarized as follows:a kind of Multi-objective Traveling Salesman problem Mission Planning Algo-rithm with Balanced Paths.The paper presents a mission planning algorithm for Multi-objective traveling salesman problem with an objective to balance the length of traveling path and make the sum of path optimization.The travel mission involves several cities that need to be passed by traveling salesman.This algorithm is based upon the "attractors" of systems science.In this paper,combining with the neigh-boring points and the shortest path algorithm,we design a heuristic algorithm for solving the problem which balancing the length of traveling path and making the sum of path optimization,At the same time,the computation time complexity of the algorithm is lower than the past.A kind of mission planning algorithm with multidepot multisalesmen problem. This paper presents a new solving method for multidepot multisalesmen problem based on K-means clustering algorithm. Algorithm defines the node attract and classies the set of the tour node according node attract matrix,then applies the heuristic algorithm of single traveling salesman to solve it.The experiments results with multidepot multisalesmen problem show that this mission planning algorithm can be effectively applied in solving such problemsmulti-path routing algorithm of Ad hoc networks based on multiple travel-ing salesman problem. Traveling salesman problem multi-path routing algorithm (TSPMR algorithm), is a multi-path routing of expansion Leach algorithm,mul-tiple clusters in the whole network, determine the cluster head to reduce energy consumption by collecting and transporting information, executing multi-path rout-ing to ensure routing stability within the cluster.