Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Large language model-enhanced ant colony optimization for multi-solution traveling salesman problems
Taixin CAI, Fengfeng WEI
Journal of Computer Applications    2026, 46 (6): 1712-1720.   DOI: 10.11772/j.issn.1001-9081.2025050646
Abstract128)   HTML0)    PDF (1197KB)(50)       Save

In Combinatorial Optimization (CO) problems, Multi-Solution Traveling Salesman Problem (MSTSP) aims to acquire a set of distinct globally optimal paths, and plays a critical role in scenarios such as logistics scheduling and tour route planning. As a traditional approach for solving path optimization problems, ACO (Ant Colony Optimization) suffers from bottlenecks including pheromone premature convergence and imbalance between solution quality and diversity. To address these challenges, a Large Language Model (LLM)-enhanced ACO for MSTSP (L-ACO) was proposed to integrate LLMs into traditional ACO through a multi-layer prompt engineering strategy: during the solution construction stage, the city topological features were parsed, so as to construct high-quality diverse initial paths; in the perturbation optimization stage, new paths were generated on the basis of the paths in solution pool and their statistical information, so as to escape from the local optimum. Additionally, a multi-dimensional evaluation system was developed to assess solution quality, diversity, and LLM effectiveness comprehensively. Experimental results on 25 MSTSP benchmark instances demonstrate that compared to traditional ACO, L-ACO improves the Structural Diversity Index (SDI) by 0.08 and the Quality-Quantity Composite Index (QQCI) by 13% relatively, indicating that L-ACO effectively optimize the convergence in multi-solution scenarios compared to traditional ACO.

Table and Figures | Reference | Related Articles | Metrics