Research On Evolutionary Multi-objective Optimization And Decision Making For Solving Multiple Traveling Salesman Problem

As an extension of the classic Travel Salesman Problem,the Multiple Traveling Salesman Problem can simulate many practical problems in life by adding certain constraints,such as logistics planning,uav patrol,task scheduling,etc.The Multiple Traveling Salesman Problem has been proved to be a NP-hard problem.The accurate method cannot meet the solution needs of large-scale problems,while the heuristic algorithm can obtain the solution with better quality in a short time,which makes the researchers' attention to the solution method of this problem more inclined to the latter.In the case of the Multiple Traveling Salesman Problem,the increase in the number of salespersons is not intended to reduce the cost of the total distance,but is usually used as a measure to equalize the workload among the salespersons or to reduce the time spent serving each customer.Most of the existing literature discusses this problem from two aspects: one is to minimize the total cost by reducing the total distance,and the other is to minimize the longest route among salespersons to balance the workload between salespersons.However,balancing the workload and reducing the length of the total distance are two conflicting objectives,so this thesis analyzes and solves the problem from the perspective of multi-objective optimization.NSGA-? is a popular one among many evolutionary multi-objective optimization algorithms.It has been applied to many practical problems and achieved good results.Based on the NSGA-II algorithm framework,this thesis solves the Multiple Traveling Salesman Problem by designing the chromosome,crossover operator,and mutation operator in the genetic algorithm to obtain a Pareto front with well-diversity and wellconvergent.Considering the real life,most optimization problems have no obvious weight and preference relationship between different goals,so this thesis further integrates decision-making methods based on NSGA-?,and proposes an evolutionary multiobjective decision-making algorithm,through the knee point to guide the course of evolution,the algorithm in operation after the completion of the program to output a more satisfactory solution.This method avoids the trouble of solving the evenly distributed Pareto front and the selection pressure generated by the decision maker in the face of huge Pareto front,making the whole solution process without the participation of the decision maker.By using the existing calculation results as a reference,the feasibility of the proposed algorithm is proved by comparison.