A Heuristic Algorithm for Solving MTSP Problems is Developed Based on the K-means Clustering Algorithm and the CNGA Algorithm
This article focuses on the MinMaxMTSP problem and seeks to minimize the maximum length of the loops traveled by all travel agents,aiming to minimize the length of the longest journey a-mong all travel salesman journeys.This article proposes a heuristic algorithm called KCNGA,which combines clustering algorithm and genetic algorithm to generate excellent gene fragments through pre-liminary calculations of heuristic algorithm,which can effectively improve the convergence speed of sub-sequent calculations.By grouping cities to reduce the size of the problem,computational efficiency has been improved and the complexity of the problem has been simplified.Meanwhile,by applying heuristic algorithms to each subset,the quality of understanding can be improved.This algorithm has strong spe-cificity for solving MinMaxMTSP problems.In this paper,we conducted grouping experiments using KCNGA algorithm and GA algorithm with different travel quotients on some datasets in the tsplib data-set,and proved that KCNGA algorithm has accuracy and fast convergence in solving MinMaxMTSP problems.
万方数据
维普
