Abstract:

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.

Key words: Combinatorial Optimization (CO), Multi-Solution Traveling Salesman Problem (MSTSP), Ant Colony Optimization (ACO), Large Language Model (LLM), prompt engineering

摘要：

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

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