Solving MTSP with Two-stage SA and GA Based on Spark
摘要
A two-stage KSAGA algorithm combining Spark-based simulated annealing and genetic algorithms was proposed for the single-depot multiple traveling salesman problem with minimum total path length. In the first stage, the multiple traveling salesman problem was split into multiple single traveling salesman problems by k means clustering, and the traversal order of cities in the group was optimized using the simulated annealing algo rithm. In the second stage, the classification of cities was optimized by genetic algorithm, and the cross-variance operator as well as the hybrid local optimization operator were designed based on the chromosome grouping encoding method to improve the search space and convergence speed of the algorithm. As the number of cities increased and the computational scale became larger, the characteristics of genetic algorithm were used to realize the parallelism of the algorithm in order to speed up the algorithm operation efficiency. Finally, the solution quality of KSAGA was compared with that of ACO, GA, SPKSA, ALNS and NSGA-Ⅱ and the convergence speed of GA and NSGA-Ⅱ by selecting some datasets of TSPLIB for simulation experiments. The results showed that KSAGA could converge quickly in solving the single-depot multiple traveling salesman problem, and the solution quality was greatly im proved compared with other algorithms. Meanwhile, the advantage of KSAGA was more obvious as the number of cities and the number of travelers increased.