Hierarchical Genetic Algorithm for the Multi-Solution Traveling Salesman Problem
IEEE Transactions on Evolutionary Computation · 2026-04 · 30 (2) · 732-746
DOI: 10.1109/tevc.2025.3565947 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Evolutionary Computation, 2026-04. Verfasst von Caitong Yue und 6 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 49 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Henan Province, Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications Open Foundation.
Abstract (Originalsprache)
The traveling salesman problem (TSP), a classic combinatorial optimization problem, has been extensively studied for many years. Recently, the Multi-solution Traveling Salesman Problem (MSTSP) has received increasing attention and achieved significant progress. Compared to the traditional TSP, MSTSP can identify more optimal solutions, providing more satisfactory solutions in urgent situations or according to user preferences. However, research on MSTSP remains relatively limited. Most existing algorithms primarily focus on the traditional TSP and pay little attention to the search for multiple solutions. As a result, there are very few algorithms specifically designed for MSTSP. This article proposes a hierarchical genetic algorithm of “preprocessing – approximate search – precise search.” In the preprocessing stage, simple evolution of the initial population is performed to enhance the reliability of critical edges. In the approximate search, individual generation strategy is designed to achieve global rapid convergence. A new environment selection mechanism is designed for the deletion and retention of multimodal solutions. In the precise search, individual clustering and regeneration strategy, and a local search strategy based on jump operator are designed to find more multimodal solutions. The hierarchical approach, which progresses sequentially, can discover more multimodal solutions while also achieving the global optimal solution. To validate the proposed algorithm’s performance, comprehensive experiments are conducted on multi-solution optimization test suite, and compared it with the latest algorithms. Experimental results show that the proposed algorithm outperforms compared algorithms.
Förderung
- National Natural Science Foundation of China
- Natural Science Foundation of Henan Province
- Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications Open Foundation
- Key Research and Development Program of Henan Province
- Open Project of Longmen Laboratory
Zitieren
APA
Yue, C., Shen, Y., Liang, J., Yu, K., Li, M., Ma, T., & Song, H. (2026). Hierarchical Genetic Algorithm for the Multi-Solution Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 30(2), 732-746. https://doi.org/10.1109/tevc.2025.3565947
Vancouver
Yue C, Shen Y, Liang J, Yu K, Li M, Ma T, et al. Hierarchical Genetic Algorithm for the Multi-Solution Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation. 2026;30(2):732-746. doi:10.1109/tevc.2025.3565947
BibTeX
@article{Yue2026,
author = {Yue, Caitong and Shen, Yuxi and Liang, Jing and Yu, Kunjie and Li, Mengmeng and Ma, Tianlei and Song, Hui},
title = {Hierarchical Genetic Algorithm for the Multi-Solution Traveling Salesman Problem},
journal = {IEEE Transactions on Evolutionary Computation},
year = {2026},
volume = {30},
number = {2},
pages = {732--746},
doi = {10.1109/tevc.2025.3565947}
}
EUVIMED