GES-TSP：基于图边稀疏化的旅行商问题高效求解新方法

大规模旅行商问题（TSP）的精确求解计算成本高昂，研究者常采用图稀疏化方法提升效率。传统方法多依赖固定启发式规则，难以充分利用实例特定的结构信息。近日，研究团队在arXiv发表论文《GES-TSP: Graph Edge Sparsification for TSP》，提出一种基于学习的图边稀疏化方法GES，专门针对欧几里得TSP设计。该方法融合几何结构信息与组合优化技术，能够针对不同问题实例自适应生成稀疏化图，大幅缩减图规模并加速求解过程。实验表明，在MATILDA数据集上，GES方法可剪除高达95%的边，同时将解与最优值的差距控制在1%以内。在TSPLIB基准测试中，该方法展现出强泛化能力：部分大规模实例的剪枝率超过99%，最优性差距仍低于1%。该研究为组合优化问题的高效求解提供了新的技术思路，特别适用于需要快速获得近似最优解的实际应用场景。