精选今天0 投票
GES-TSP：用图边稀疏化技术高效求解旅行商问题
旅行商问题（TSP）是组合优化领域的经典难题，其精确求解在大规模实例下计算成本极高。传统图稀疏化方法多依赖固定启发式规则，难以充分利用实例特有的结构信息。针对这一瓶颈，研究团队提出了一种名为 GES（Graph Edge Sparsification） 的学习型稀疏化方法，专为欧几里得 TSP 设计。
GES 的核心思路是将几何结构信息与组合优化技术深度融合，通过模型学习为不同实例自适应生成稀疏化图。与传统方法不同，GES 能够根据问题特征动态剪枝，大幅减少图中冗余边数量，从而显著加速求解过程。实验结果表明，在 MATILDA 数据集上，该方法可剪除高达 95% 的边，同时保证求解结果与最优解的差距控制在 1% 以内。更令人印象深刻的是，在 TSPLIB 基准中的部分大规模实例上，剪枝率甚至超过 99%，而最优性差距仍然低于 1%。
这一成果揭示了数据驱动方法在传统组合优化中的巨大潜力。与手工设计的启发式规则相比，学习型方法能够捕捉更高层的结构模式，从而在保持近似精度的同时实现极致的计算压缩。对于物流、电路设计、路径规划等依赖 TSP 求解的实际应用而言，GES 提供了一种兼顾效率与质量的新思路，有望推动大规模 TSP 精确求解走向实用化。
未来，该团队的工作方向可能包括将 GES 扩展到其他图优化问题（如 VRP、最大割等），或进一步结合强化学习提升稀疏化策略的自适应性。