Research On General Colored Traveling Salesman Problem And Its Algorithm

Colored Traveling Salesman Problem(CTSP)is a generalization of Traveling Salesman Problem(TSP)and Multiple Traveling Salesman Problem(MTSP).It introduces colors to distinguish the accessibility of cities among multiple salesmen.CTSP is suitable for modeling and solving the real-world optimization scheduling problems which involve the multiple tasks with different accessibilities of multiple machines.Based on the complete graph,three kinds of CTSPs have been proposed,i.e.,Radial CTSP(R-CTSP),Serial CTSP(S-CTSP)and general CTSP(GCTSP).To further generalize GCTSP so as to model the engineering problems based on complex networks,this paper intends to restate GCTSP over hypergraphs instead of complete graphs,and thus propose three GCTSPs defined by hypergraphs.Furthermore,three efficient methods are developed according to the characteristics and difficulties of these models.The main research contents and work are listed as follows:1)The concept of city partition and the cost function upon the partition is proposed according to hypergraphs.Then,GCTSP is redefined over hypergraphs for the first time,and some basic properties are discussed.It is concluded that GCTSP can be transformed into R-CTSP,S-CTSP and MTSP under certain conditions.On the basis of GCTSP,we take into account the emergence of“short board effect” and the priority constraints that may appear in the scheduling system,respectively.In this way,a Bi-objective CTSP(BCTSP)and a Precedence-constrained CTSP(PCTSP)are proposed.Moreover,we discuss the NP intractability of BCTSP,and count the number of partitions on PCTSP.2)Considering that a key to large-scale TSP cases is to construct a city network of an extremely low density,we propose a Delaunay-Triangulation-based Variable Neighborhood Search(DVNS)to solve large-scale GCTSP cases.DVNS can quickly create a low-density Delaunay triangulation by using divide & conquer method.Specifically,a Greedy Multi-Insertion(GMI)is studied,and it employs Delaunay edges as the candidate insertion objects to perturb the current solution.Moreover,DVNS are equipped with 2-Opt and 3-Opt to optimize the local search procedure in turn.21 GCTSP cases with regular or random city color distribution are designed to test the performances of DVNS and the other six algorithms.The simulation results implemented on a PC show that DVNS can obtain satisfactory solutions in GCTSP cases with up to 33,000+ cities or up to 240 salesmen within120(s),and that DVNS is superior to the six comparison algorithms in terms of solution quality and convergence rate.3)A population-based Bi-objective VNS(BVNS)is proposed for solving BCTSP.It contains four main operators,including: Probability-based Insertion(PI),Population-based Multi-Insertion operator(PMI),Color-preserving Exchange(CE)and 2-opt.The first operator is to construct different neighborhoods of the current solution,while the latter three are employed to perform local search.Specifically,PMI continues to utilize Delaunay triangulation to determine the candidates for insertion,and CE improves the exploration ability of BVNS by decreasing the undesirable intersections among salesmen' routes.In addition,25 BCTSP cases are designed to test the performance of BVNS.Particularly,the Pareto fronts obtained by BVNS are compared with those of the accurate algorithm ?-constraint in five small-scale data sets.The simulation results demonstrate that BVNS is effective for solving both small-scale and large-scale BCTSP cases,and that BVNS produces better values of Hypervolume and Inverted Generational Distance than the other four algorithms.4)Since PCTSP is asymmetric and Delaunay triangulation cannot handle asymmetric models,a PVNS(POPMUSIC-based VNS)is developed to address PCTSP.It consists of four parts,i.e.,Constraint-preserving Multi-insertion(CMI),Constraint-preserving Exchange Mutation(CEM),Constraint-preserving-2-exchange(C2-ex)and Path-preserving-3-exchange(P3-ex).CMI utilizes the POPMUSIC method to determine candidate edges.Based on the simulation experiments,we reveal the key roles of the four operators on the exploration ability of PVNS.Furthermore,the comparison among PVNS,LKH3 and the other 5 algorithms on 34 test cases implies that PVNS outperforms the other six algorithms in most cases.Particularly,automated hyper-parameter tuning usually achieves much better practical performances than manual hyper-parameter tuning,and therefore we use the irace package to tune all the parameters of PVNS and related algorithms.This paper establishes three GCTSPs by employing hypergraphs as the description tool,and designs three efficient VNS to address these models.Currently,they have been applied to model and solve the complex practical problems which own various accessibility of tasks among executing individuals,such as: the scheduling problems of multi-AGV in E-commerce warehouses.The work aforementioned has further enriched the theoretical system of CTSP and broadened the prospects of CTSP in practical engineering applications.