Solving MTSP with Two-stage SA and GA Based on Spark
[1]SUN Jian,LIU Pin,LI Hao,et al.Solving MTSP with Two-stage SA and GA Based on Spark[J].Journal of Zhengzhou University (Engineering Science),2024,45(04):62-69.[doi:10.13705/ j.issn.1671-6833.2024.01.019]
Copy
Journal of Zhengzhou University (Engineering Science)[ISSN
1671-6833/CN
41-1339/T] Volume:
45
Number of periods:
2024 04
Page number:
62-69
Column:
Public date:
2024-06-16
- Title:
- Solving MTSP with Two-stage SA and GA Based on Spark
- Keywords:
- MTSP; parallel; genetic algorithm; group encoding; local optimization operator
- CLC:
- TP301.6
- DOI:
- 10.13705/ j.issn.1671-6833.2024.01.019
- 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.
- References:
-
[1] 苏守宝, 赵威, 李智. 求解加权MTSP问题的CUDA 并行群智能方法[J]. 郑州大学学报(工学版), 2021, 42(6): 34-41. SU S B, ZHAO W, LI Z. CUDA-based parallel swarm intelligence method for solving weighted MTSP[J]. Jour nal of Zhengzhou University (Engineering Science), 2021, 42(6): 34-41.[2] MOHAMMAD S, MAJID Y, NARGES M. An effective genetic algorithm for solving the multiple traveling sales man problem[J]. Journal of Optimization in Industrial Engineering, 2011, 4: 73-79.[3] YANG S, SHAO Y F, ZHANG K. An effective method for solving multiple travelling salesman problem based on NSGA-Ⅱ[J]. Systems Science & Control Engineering, 2019, 7(2): 108-116.[4] HARRATH Y, SALMAN A F, ALQADDOUMI A, et al. A novel hybrid approach for solving the multiple traveling salesmen problem[J]. Arab Journal of Basic and Applied Sciences, 2019, 26(1): 103-112.[5] 董建华, 王国胤, 雍熙, 等. 基于Spark的标准化PCA算 法[J]. 郑州大学学报(工学版), 2017, 38(5): 7-12.DONG J H, WANG G Y, YONG X, et al. Normalized PCA algorithm based on Spark[J]. Journal of Zhengzhou University (Engineering Science), 2017, 38(5): 7-12.[6] ZHENG J Z, HONG Y W, XU W C, et al. An effective iterated two-stage heuristic algorithm for the multiple trav eling salesmen problem[J]. Computers & Operations Re search, 2022, 143: 105772.[7] 冯兴杰, 王文超. Hadoop与Spark应用场景研究[J]. 计算机应用研究, 2018, 35(9): 2561-2566.FENG X J, WANG W C. Survey on Hadoop and Spark application scenarios[J]. Application Research of Com puters, 2018, 35(9): 2561-2566.[8] 孙鉴, 刘凇佐, 武晓晓, 等. 基于Spark的并行模拟退 火算法求解TSP[J]. 电子测量技术, 2022, 45(4): 53-58.SUN J, LIU S Z, WU X X, et al. Solving TSP based on Spark-based parallel simulated annealing algorithm[J]. E lectronic Measurement Technology, 2022, 45(4): 53-58.[9] AL-FURHUD M A,AHMED H Z. Genetic algorithms for the multiple travelling salesman problem[J]. Internation al Journal of Advanced Computer Science and Applica tions, 2020, 11(7): 553-560.[10]杨帅. 求解多旅行商问题的进化多目标优化和决策算 法研究[D]. 武汉: 武汉科技大学, 2021.YANG S. Research on evolutionary multi-objective opti mization and decision making for solving multiple trave ling salesman problem[D]. Wuhan: Wuhan University of Science and Technology, 2021.[11]孙冰, 王川, 杨强, 等. 面向多起点均衡多旅行商问 题的进化算法[J]. 计算机工程与设计, 2023, 44 (7): 2030-2038.SUN B, WANG C, YANG Q, et al. Improved evolution ary algorithm for balanced multiple traveling salesmen problem with multiple starting points[J]. Computer Engi neering and Design, 2023, 44(7): 2030-2038.[12]王勇臻, 陈燕, 于莹莹. 求解多旅行商问题的改进分 组遗传算法[J]. 电子与信息学报, 2017, 39(1): 198-205.WANG Y Z, CHEN Y, YU Y Y. Improved grouping ge netic algorithm for solving multiple traveling salesman problem[J]. Journal of Electronics & Information Tech nology, 2017, 39(1): 198-205.[13] PAN J J, WANG D W. An ant colony optimization algo rithm for multiple travelling salesman problem[C]∥First International Conference on Innovative Computing, Infor mation and Control. Piscataway: IEEE, 2006: 210-213.[14] KIRÁLY A, ABONYI J. A novel approach to solve multi ple traveling salesmen problem by genetic algorithm[J]. Computational Intelligence in Engineering, 2010, 313: 141-151.[15]孙鉴, 李昊, 刘凇佐, 等. 基于Spark的并行k均值聚 类模拟退火算法求解MMTSP[J]. 电子测量技术, 2022, 45(20): 53-60.SUN J, LI H, LIU S Z, et al. Spark-based parallel k means clustering simulated annealing algorithm to solve MMTSP[J]. Electronic Measurement Technology, 2022, 45(20): 53-60.[16] HUANG K Y, MA J B, LIU X Y. Research on vehicle route planning with capacity limitation based on adaptive large-scale neighborhood search algorithm[C]∥2021 6th International Symposium on Computer and Information Processing Technology (ISCIPT). Piscataway: IEEE, 2021: 6-10.[17] YOUSEFIKHOSHBAKHT M, DIDEHVAR F, RAHMATI F. Modification of the ant colony optimization for solving the multiple traveling salesman problem[J]. Romanian Journal of Information Science and Technology, 2013, 16 (1): 65-80.
- Similar References:
Memo
-
Last Update:
2024-06-14