Abstract: In combinatorial optimization problems, the Multi-Solution Traveling Salesman Problem (MSTSP) aims to acquire a set of distinct globally optimal paths, which plays a critical role in scenarios such as logistics scheduling and tourism route planning. As a traditional approach for solving path optimization problems, the Ant Colony Optimization (ACO) algorithm was found to suffer from bottlenecks including premature pheromone convergence and imbalance between solution quality and diversity. To address these challenges, a Large Language Model (LLM)-Enhanced Ant Colony Optimization (L-ACO) was proposed, which integrates LLM into traditional ACO through a two-stage strategy with multi-layer prompt engineering: during the seed generation stage, city topological features were parsed to construct high-quality diverse initial paths; in the perturbation optimization stage, new paths were generated based on existing solution pools and their statistical information to escape local optima. Additionally, a multidimensional evaluation framework was developed to comprehensively assess solution quality, diversity, and LLM effectiveness. Testing on 25 MSTSP benchmark instances demonstrated that L-ACO improved the structural diversity index by 8 percentage points and the quality-quantity comprehensive metric by 13% relative to traditional ACO. These results indicate that L-ACO effectively mitigates convergence issues in multi-solution scenarios compared to conventional implementations.

Key words: combinatorial optimization, multi-solution traveling salesman problem, ant colony optimization, large language model, prompt engineering

摘要： 组合优化问题中，多解旅行商问题（Multi-Solution Traveling Salesman Problem, MSTSP）的目标是获取一组互异的全局最优路径，在物流调度、旅游线路规划等场景具有关键价值。作为求解路径优化问题的传统方法，蚁群算法（Ant Colony Optimization, ACO）存在信息素早熟收敛、质量与多样性失衡的瓶颈。针对上述挑战，提出一种大语言模型（Large Language Model, LLM）增强的蚁群算法（L-ACO），采用多层提示工程策略将LLM双阶段集成于传统ACO：种子生成阶段，解析城市拓扑特征构建高质量多样化初始路径；扰动优化阶段，针对解池路径及其统计信息生成新路径，跳出局部最优。此外，构建多维评价体系综合检验求解质量、多样性、LLM有效性。在25项MSTSP基准实例测试中，L-ACO的结构多样性指标相对传统ACO提升了8个百分点；质量-数量综合指标相对提升13%，表明L-ACO改善了传统ACO在多解场景下的收敛问题。

关键词: 组合优化, 多解旅行商问题, 蚁群算法, 大语言模型, 提示工程