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 · 2025
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 paper 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.