Research On The Colored Traveling Salesman Problem With Naturally-inspired Heuristic Algorithm

The traveling salesman problem(TSP)is the most representative problem in combinatorial optimization problem(COP),its application areas involve transportation,information science,communication network and so on.This paper focuses on a new variant of TSP,that is,the colored traveling salesman problem(CTSP).The CTSP is the generalization of multi-traveling salesman problem(mTSP),and the difficulty of solving is greater.As the CTSP is a problem of NP,with the increase of the scale,it can only be solved by heuristic algorithm and meta-heuristic algorithm.Therefore,we attempts to study all kinds of natural heuristic algorithms to solve it,specifically,the main work of this paper:Firstly,we summarize the research status and development process of CTSP,and then give the definition of the problem.On the basis of the small and medium scale test data,a large-scale test case is added,which enriches the test data set of CTSP.And then gives the general design of the solution coding method,the solution generate method,the solution update method,the algorithm's shutdown conditions,etc.,lay the foundation for the application of the natural heuristic algorithm in this problem.Finally,the most popular genetic algorithm,ant colony algorithm,artificial bee colony algorithm and Ito algorithm are used to solve the problem,and the validity and performance of those algorithms are compared and analyzed.Then obtain the general recommendations of CTSP.The innovation of this paper can be summarized as follows:1.Design a general model for solving CTSP.Through the analysis of related problems and related algorithms,we give the representation of the solution,the construction method and the stopping condition to the CTSP problem,which facilitate the application of other natural heuristic algorithms to the problem.2.Expand the scale of the problem.Based on the original test case,we design the larger scale test case,laying the foundation for the further study of the CTSP.3.Extend the solution algorithm.Based on the analysis of existing mTSP and CTSP,this paper designs and implements genetic algorithm(GA),ant colony algorithm(ACO),artificial bee colony algorithm(ABC),discrete ITO algorithm(ITO),and solves the problem.