論文の概要: Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP
- arxiv url: http://arxiv.org/abs/2510.20169v1
- Date: Thu, 23 Oct 2025 03:30:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 03:08:17.232949
- Title: Empowering Targeted Neighborhood Search via Hyper Tour for Large-Scale TSP
- Title（参考訳）: 大規模TSPのためのハイパーツアーによるターゲット近傍探索の強化
- Authors: Tongkai Lu, Shuai Ma, Chongyang Tao,
- Abstract要約: トラベルセールスマン問題(TSP)は古典的なNPハード問題であり、学術と産業の両方から大きな注目を集めている。
大規模TSPインスタンスを対象としたHyper Tour Guided Neighborhood Search (HyperNS)法を提案する。
- 参考スコア（独自算出の注目度）: 28.92346104523666
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Traveling Salesman Problem (TSP) is a classic NP-hard problem that has garnered significant attention from both academia and industry. While neural-based methods have shown promise for solving TSPs, they still face challenges in scaling to larger instances, particularly in memory constraints associated with global heatmaps, edge weights, or access matrices, as well as in generating high-quality initial solutions and insufficient global guidance for efficiently navigating vast search spaces. To address these challenges, we propose a Hyper Tour Guided Neighborhood Search (HyperNS) method for large-scale TSP instances. Inspired by the ``clustering first, route second" strategy, our approach initially divides the TSP instance into clusters using a sparse heatmap graph and abstracts them as supernodes, followed by the generation of a hyper tour to guide both the initialization and optimization processes. This method reduces the search space by focusing on edges relevant to the hyper tour, leading to more efficient and effective optimization. Experimental results on both synthetic and real-world datasets demonstrate that our approach outperforms existing neural-based methods, particularly in handling larger-scale instances, offering a significant reduction in the gap to the optimal solution.
- Abstract（参考訳）: トラベルセールスマン問題(TSP)は古典的なNPハード問題であり、学術と産業の両方から大きな注目を集めている。
ニューラルネットワークの手法はTSPの解決を約束しているが、大規模なインスタンス、特にグローバルなヒートマップ、エッジウェイト、アクセスマトリックスに関連するメモリ制約、高品質な初期ソリューションの生成、巨大な検索スペースを効率的にナビゲートするためのグローバルガイダンスの不足といった課題に直面している。
これらの課題に対処するため,大規模TSPインスタンスを対象としたHyper Tour Guided Neighborhood Search(HyperNS)手法を提案する。
この手法は,まずスパースヒートマップグラフを用いてTSPインスタンスをクラスタに分割し,それらをスーパーノードとして抽象化し,初期化と最適化プロセスの両方をガイドするハイパーツアーを生成する。
この手法は,ハイパーツアーに関連するエッジに着目して探索空間を削減し,より効率的かつ効率的な最適化を実現する。
合成と実世界の両方のデータセットに対する実験結果から、我々のアプローチは既存のニューラルベース手法、特に大規模インスタンスの処理において優れており、最適解のギャップを著しく減らすことが示されている。
関連論文リスト
- GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales [16.177833864654172]
本稿では,旅行セールスマン問題の解法として,GELDというニューラルネットワークを用いた新しい解法を提案する。
GELDは軽量なグローバルビュー推論(GE)とヘビーウェイトなローカルビューデコーダ(LD)を統合し、埋め込み表現を充実させる。
合成データセットと実世界のデータセットの両方で実施された大規模な実験は、GELDが7つの最先端モデルより優れていることを示した。
論文 参考訳（メタデータ） (2025-06-07T03:00:05Z) - ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
スケーラブルで効果的なグラフ学習のためのマルチホップノード機能を適応的に融合する新しいフレームワークであるScaleGNNを提案する。
予測精度と計算効率の両面で,ScaleGNNは最先端のGNNよりも一貫して優れていることを示す。
論文 参考訳（メタデータ） (2025-04-22T14:05:11Z) - Destroy and Repair Using Hyper Graphs for Routing [14.391263435675587]
ハイパーグラフに基づくDestroy-and-Repairフレームワークを提案する。
このフレームワークは連続した連続したエッジをハイパーエッジに減らし、モデルが破壊された部分により多くの注意を払って、すべてのノードを符号化する複雑さを減らします。
論文 参考訳（メタデータ） (2025-02-22T10:04:58Z) - Hierarchical Neural Constructive Solver for Real-world TSP Scenarios [27.986011761759567]
本稿では,産業環境に関連する現実的なトラベリングセールスマン問題(TSP)について紹介する。
我々の階層的アプローチは、古典的モデルと最近のトランスモデルの両方と比較して優れたパフォーマンスをもたらす。
論文 参考訳（メタデータ） (2024-08-07T06:44:47Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。
近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。
本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
論文 参考訳（メタデータ） (2023-04-19T03:48:32Z) - Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。
提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。
大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
論文 参考訳（メタデータ） (2022-11-02T14:35:13Z) - A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。
GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
論文 参考訳（メタデータ） (2020-07-09T17:23:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。