Optimization Of Multiple Traveling Salesman Problem Based On Genetic Algorithm

Traveling Salesman Problem(TSP)is a classical NP-hard combinatorial optimization problem.As an extended model,Multiple Traveling Salesman Problem(MTSP)has a stronger practical significance.In the ideal situation,the traveling salesman problem and the multiple traveling salesman problem almost do not exist.This thesis introduces two more practically meaningful models,i.e.,Multiple Traveling Salesman Problem with Limited Capacity(LCMTSP)and Uncertain Multiple Traveling Salesman Problem(UMTSP)models.The Genetic Algorithms(GA)is designed to solve these two models.In this thesis,the LCMTSP problem model is firstly studied,and the capacity constraint condition is added to the MTSP model to control the city number of each traveling salesman.In view of the complexity of the problem,the random method and suboptimal selection method are adopted in the population initialization process for traditional Genetic Algoriyhm(GA)in this thesis.Moreover,the minimum crossover rule is added to the traditional crossover operator,and the traditional local search process is integrated with the DI operator and the 3-opt operator.This improved GA is denoted as IGA.The experimental results prove the feasibility and effectiveness as well as the higher computational efficiency of IGA for LCMTSP.Due to the unreliability of the ideal multiple traveling salesman problem in the real environment,this thesis sums up the uncertainty factors in the real situation as a kind of road condition coefficient,and builds a model for Uncertainty Multiple Traveling Salesman Problem(UMTSP).A GA for UMTSP,namely GA-UMTSP is designed and used to solve UMTSP.The experimental results obtained by GA-UMTSP for the basic MTSP problem and UMTSP problem are compared.The experimental results prove the practical significance of the UMTSP problem model and the feasibility and practicality of GA-UMTSP.