巡回セールスマン問題（TSP）は、組合せ最適化の中でも最もよく知られたNP困難問題の一つであり、大規模インスタンスの厳密解を求めるには莫大な計算コストがかかる。この問題に対処するため、多くの研究者はグラフのスパース化（辺の間引き）を利用して問題サイズを削減してきた。しかし、従来のスパース化手法は固定されたヒューリスティックに依存しており、各インスタンス固有の構造情報を十分に活用できていない。
この課題に対して、中国の研究チームが提案したGES-TSP（Graph Edge Sparsification for TSP）は、学習ベースの新しいアプローチである。GES-TSPは、幾何学的な構造情報と組合せ最適化の技術を組み合わせることで、インスタンスごとに適応的なスパースグラフを生成する。具体的には、深層学習モデルが各TSPインスタンスの特徴を捉え、重要でない辺を除去したグラフを構築する。これにより、求解に必要な計算量を劇的に削減しつつ、最適性をほとんど損なわない。
実験では、MATILDAデータセットを用いて最大95%の辺を削減し、解の品質（最適解とのギャップ）は1%未満を達成した。さらに、TSPLIBベンチマークの大規模インスタンスでは、削減率が99%を超えてもギャップは1%未満に抑えられた。この結果は、GES-TSPが極めて高い効率と強力な汎化能力を兼ね備えていることを示している。
本研究は、機械学習と従来の最適化手法を融合させることで、TSP求解の効率化に新たな道を開いた。著者らのChen Tianfeng氏とLi Xianyue氏は、この手法をさらに発展させ、車両経路問題（VRP）などの関連問題への応用を目指している。論文はarXivプレプリント（識別番号2607.09708）として公開され、人工知能（cs.AI）、機械学習（cs.LG）、組合せ数学（math.CO）の各分野に提出されている。コードや追加資料は近日中に公開される予定であり、今後の研究発展への貢献が期待される。