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

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