Research On Multiple Traveling Salesman Problem Based On Improved Genetic Algorithm

Genetic Algorithm(GA)is a heuristic search algorithm which simulates the natural evolution process to search for the optimal solutions.Due to its inherent hidden parallelism,good global optimization ability and strong robustness,this algorithm is widely used to solve complex combinatorial optimization problems,such as Traveling salesman problem(TSP)and Multiple Traveling Salesman Problem(MTSP).TSP is a classical NP-hard combinatorial optimization problem,and MTSP is a generalization of TSP.Compared with TSP,MTSP has more practical applications,but relatively few research results.Therefore,this dissertation studies the Genetic Algorithm for solving MTSP and different models of MTSP.The main research work is as follows:(1)Firstly,an improved genetic algorithm involving reproductive mechanism of invasive weed optimization and a local optimization mutation operator,called RLGA,is proposed for the multiple traveling salesman problem with single-depot and closed path.The proposed algorithm uses the fitness-based reproductive mechanism of the invasive weed optimization algorithm to generate population and carries out genetic operation so as to improve the search efficiency of the algorithm.In addition,a hybrid local optimization operator is proposed as a mutation operator to improve the local search ability of the algorithm.The experimental results show that RLGA can converge to the optimal solution quickly for the multiple traveling salesman problem with balanced workload,and the precision of the solution is remarkably improved.(2)To overcome the shortcoming that multiple traveling salesman problem with closed path and fixed depot cannot seek for the best depot,a depot-optimizable closed path multiple traveling salesman problem model is proposed.The depot in this model is not prespecified in advance,but can be optimized in the solution process.Furthermore,an addressable improved partheno-genetic algorithm with the reproductive mechanism of the invasive weed optimization,called RAIPGA,is proposed for the new model,and a new encoding method is designed to generate individuals with random depot in the population initialization so as to optimize them during the algorithm process.In RAIPGA,the reproductive mechanism of invasive weed optimization is utilized to generate offspring which can produce the same depot as the parent in order to accelerate the convergence speed.In addition,the improved partheno-genetic operation is employed to simultaneously optimize the position of the depot and path.Finally,a mixed selection operator is used to perform selection on the population and to avoid premature convergence of the algorithm.Simulation results show that RAIPGA has good performance in finding the best depot and the shortest path,and it can be well applied to the tourism route planning problem.(3)To solve the multiple traveling salesman problem model with multiple depots and closed path,a fuzzy C-means clustering based partheno-genetic algorithm,called FCMPGA,is proposed.Firstly,the proposed algorithm classifies all the cities into several classes according to the Euclidean distance and city’s subordinative degree,and then each class is associated with a TSP which is then solved by the improved partheno-genetic algorithm,so that not only the search space of the algorithm is greatly reduced,thus making the reduced search space be more adequately explored,but also the optimal solution of the problem is obtained more quickly.Experimental results show that the algorithm exhibits good performance on problem sets with different sizes,especially on large-size problems the performance of the algorithm is more superior and the convergence speed is faster.