旅行商問題（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）等多個學科領域。其開源代碼和附加材料預計將在後續更新中公佈，為學術界和工業界提供重要參考。