旅行販売問題に対する効率的なグラフ畳み込みネットワーク技術

本論文では、2Dユークリッドグラフ上の旅行販売問題を近似的に解決するための新しい学習ベースのアプローチを紹介します。深いグラフ畳み込みネットワークを用いて、効率的なTSPグラフ表現を構築し、高度に並列化されたビームサーチを介して非自己回帰的な方法でツアーを出力します。我々のアプローチは、固定サイズのグラフインスタンスにおける解の質、推論速度、サンプル効率の点で最近提案されたすべての自己回帰的ディープラーニング技術を上回っています。特に、50ノードでは最適性ギャップの平均を0.52％から0.01％に、100ノードでは2.26％から1.39％に削減しました。最後に、TSPに対する他の学習ベースのアプローチを改善しているにもかかわらず、我々のアプローチは標準的なオペレーションズリサーチソルバーには及びません。