GES-TSP：面向旅行商问题的图边稀疏化方法
提出一种基于学习的图边稀疏化方法GES-TSP，用于高效求解大规模欧几里得旅行商问题。通过融合几何结构与组合优化，自适应生成稀疏图，在MATILDA数据集上可修剪高达95%的边，解差距保持在1%以内，并在TSPLIB基准上展现出强泛化能力。
旅行商问题（TSP）是组合优化领域中最经典的NP-hard问题之一，其大规模实例的精确求解一直面临着计算开销巨大的挑战。为了提升求解效率，研究人员通常采用图稀疏化方法，通过移除部分不重要的边来减小问题规模。然而，传统的稀疏化方法多依赖固定启发式规则，无法针对每个实例的结构特点进行动态调整，从而限制了其性能。
针对这一局限，来自中国的研究团队提出了一种名为GES-TSP（Graph Edge Sparsification for TSP）的新型学习驱动方法。该方法的核心创新在于将几何结构信息与组合优化技术深度融合：通过深度学习模型，GES-TSP能够自适应地为每个TSP实例生成一个稀疏化图，在保留关键边的同时大幅削减边数，从而显著加速后续的求解过程。
实验在MATILDA和TSPLIB两大基准数据集上进行。在MATILDA数据集上，GES-TSP成功修剪了高达95%的边，而求解质量与最优解的差距始终保持在1%以内。更令人印象深刻的是，在TSPLIB的大规模实例上，该方法的修剪率甚至超过了99%，同时最优性差距仍低于1%。这充分证明了GES-TSP在保持解质量的同时，能极大提升计算效率。
此外，GES-TSP展现出强大的泛化能力，能有效应对不同规模、不同分布的TSP实例。论文作者Tianfeng Chen和Xianyue Li表示，未来工作将探索将该方法扩展到更广泛的图优化问题中，如车辆路径问题（VRP）或旅行商问题的变体。该研究不仅为TSP求解提供了新思路，也为其他学习算法与组合优化融合的探索树立了标杆。
该论文以arXiv预印本形式发布，编号2607.09708，并同时提交至人工智能（cs.AI）、机器学习（cs.LG）和组合数学（math.CO）等多个学科领域。其开源代码和附加材料预计将在后续更新中公布，为学术界和工业界提供重要参考。