实验技术与管理2025，Vol.42Issue(12)：79-84,6.DOI:10.16791/j.cnki.sjg.2025.12.009
聚类策略下大规模旅行商问题求解模型及实验
Solution framework and experimental validation for the large-scale traveling salesman problem using clustering strategies
摘要
Abstract
[Objective]Integrating theory and practice is essential for training professionals who are proficient in AI within the emerging engineering education(3E)framework.To connect abstract AI principles with hands-on implementation,the large-scale Traveling salesman problem(TSP),a classic NP-hard challenge demonstrating the impracticality of exact methods at scale and the inconsistency of heuristic solutions,was implemented in the present AI experiment.The developed approach provides a valuable opportunity for students learning AI.To address the high complexity,slow convergence,and poor scalability of existing approaches when applied to TSP instances with thousands of nodes,a novel cluster-based TSP framework,termed ClusterTSP,is proposed.[Methods]In the proposed methodology,large-scale TSP instances are strategically decomposed into smaller subproblems using a clustering algorithm.This decomposition significantly reduces the computational burden compared to solving a single,large instance.This"divide and conquer"strategy,aligning with efficient algorithm design principles,enables sophisticated optimization of the resulting subproblems.Following decomposition,ClusterTSP utilizes the representational power of deep learning,specifically employing Pointerformer,a cutting-edge method with notable TSP success,for optimizing these smaller problems.Leveraging the Transformer network and its attention mechanisms,Pointerformer efficiently learns complex sequential dependencies to generate high-quality TSP tours.By applying Pointerformer to clustered subproblems,the deep learning ability is harnessed for identifying near-optimal local routes.This integration within a decomposition framework mitigates scalability issues common in end-to-end deep learning for very large TSPs.To construct a high-quality final tour that encompasses all the nodes of the original TSP instance,ClusterTSP incorporates a carefully orchestrated sequence of post-processing algorithms.These algorithms are designed to effectively merge the optimized subproblem solutions and further refine the resulting global path.Initially,an efficient multi-entry/exit greedy algorithm is employed in constructing an initial global tour by intelligently connecting the optimized sub-tours generated by Pointerformer.This greedy approach provides a computationally inexpensive yet reasonably good starting point for subsequent optimization.Subsequently,a cluster boundary optimization algorithm is applied to specifically address the connections between nodes residing in different clusters,aiming to smooth transitions and eliminate potential suboptimal edges introduced by the initial decomposition.Finally,a 2-opt local search algorithm,a widely recognized and effective local technique for TSP optimization,is implemented to iteratively improve the overall tour quality by systematically exploring small perturbations to the current solution and accepting those that lead to a shorter path.The synergistic interplay of these post-processing algorithms ensures enhanced solution quality by combining Pointerformer's localized optimization with the global coherence enforced by refinement steps.[Results]Extensive experiments on large-scale TSP instances(node size≥103)demonstrate that ClusterTSP exhibits significant advantages in terms of accuracy,efficiency,and scalability compared to the state-of-the-art deep learning benchmarks,including ACO,DRL_PtrNet,and Pointerformer.The solution-quality advantage becomes more pronounced with increasing problem size,and ClusterTSP effectively addresses the scalability limitations of traditional deep learning methods for large-scale scenarios.[Conclusions]Beyond its technical contributions,this study adopts a research-led teaching initiative,actively engaging students in the entire process of developing and evaluating an algorithm.This immersive experience fosters a deeper understanding of theoretical concepts,enhances practical skills,and significantly improves students'independent problem-solving abilities,exemplifying the emphasis of the"3E"initiative on integrating theory and practice in AI education within an experimental teaching context.关键词
新工科/人工智能/大规模旅行商问题/聚类策略/强化学习Key words
emerging engineering education/artificial intelligence/large-scale traveling salesman problem/cluster strategy/reinforcement learning分类
信息技术与安全科学引用本文复制引用
JIAO Dongbin,CHEN Zhiqing,WANG Fanghua,LIU Ying,YANG Weibo,YAN Shi..聚类策略下大规模旅行商问题求解模型及实验[J].实验技术与管理,2025,42(12):79-84,6.基金项目
国家自然科学基金联合基金重点项目(U22B2040) （U22B2040）
甘肃省自然科学基金项目(24JRRA430) （24JRRA430）
兰州大学大学生创新创业训练计划(20240250041) （20240250041）
