郑州大学学报（工学版）2024，Vol.45Issue(4)：62-69,94,9.DOI:10.13705/j.issn.1671-6833.2024.01.019
基于Spark的双阶段SA及GA求解MTSP
Solving MTSP with Two-stage SA and GA Based on Spark
摘要
Abstract
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.关键词
多旅行商问题/并行/遗传算法/分组编码/局部优化算子Key words
MTSP/parallel/genetic algorithm/group encoding/local optimization operator分类
信息技术与安全科学引用本文复制引用
孙鉴,刘品,李昊,陈攀..基于Spark的双阶段SA及GA求解MTSP[J].郑州大学学报（工学版）,2024,45(4):62-69,94,9.基金项目
国家自然科学基金资助项目(62062002) （62062002）
宁夏自然科学基金资助项目(2022AAC03289,2022AAC03245,2022AAC03261) （2022AAC03289,2022AAC03245,2022AAC03261）
