EUVIMEDEUVIMED entdecken
Crossref

Hierarchical Genetic Algorithm for the Multi-Solution Traveling Salesman Problem

Caitong Yue, Yuxi Shen, Jing Liang, Kunjie Yu, Mengmeng Li, Tianlei Ma, Hui Song

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →