Research On A Min-max Colored Traveling Salesman Problem And Its Application

The Colored Traveling Salesman Problem(CTSP)is a generalized Multiple Traveling Salesman Problem(MTSP),by the introduction of color to distinguish between the city to traveling salesman a variety of access to allow,to solve the problem of difficult to describe the difference of city accessibility by MTSP.However,the current study is limited to the shortest travel route to optimize the target,not taking into account the individual business distance or cost balance,which easily lead to uneven distribution of the load,the emergence of "short board effect".Therefore,this study presents a CTSP that minimizes the maximum individual path-Min-Max CTSP(MM-CTSP),which is expected to compensate for the above"short board" to achieve the effect of balancing individual tasks or loads as much as possible.This work mainly studies its mathematical modeling,heuristic solution and related applications.Specific contents and results are as follows:First,the 0-1 nonlinear integer programming model of MM-CTSP is established.MM-CTSP is proved to be NP-hard,and it is solved by LINGO nonlinear solver.The results show that LINGO can only solve very small problems.Second,for the problems with middle and larger scales,Genetic Algorithm(GA),Differential Evolution(DE)algorithm,Firefly Algorithm(FA),Artificial Bee Colony algorithm(ABC)and Population Incremental Learning(PBIL)algorithm are designed.Then,the five basic solving algorithms are improved by combining Greedy algorithm,Hill-Climbing algorithm,Simulated Annealing algorithm,Insertion algorithm(IN)and 2-opt,respectively.And they improves the convergence speed and local search ability of the algorithm.Third,a wide range of experiments are designed to perform a comprehensive performance comparison of the proposed algorithms.The five basic solution algorithms,five local search algorithms,and the basic algorithms with local operations are compared in terms of solution quality,time consumption and convergence speed,under the fixed function evaluation times and fixed running time respectively.The results show that FA owns the best performance in five basic algorithms.In five local search algorithms,the effect of 2-opt optimization is the best.In the algorithm with local operation,GA + IN owns the best performance.GA+2-opt and FA+IN are in the same performance.In larger scale problems,the solution qualities of FA+IN,GA+IN and GA+2-opt are better than other algorithms.FA+IN can achieve a better balance between solution quality and time consumption,while GA+IN and GA+2-opt cost more time consuming.Finally,the MM-CTSP is applied to solve the path planning of the dual-bridge water-jet cutting system.It is compared with the shortest path of the total path.The experimental results show that the MM-CTSP can effectively minimize the maximum working time,and improve the operating system operating efficiency.