論文の概要: Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting

• arxiv url: http://arxiv.org/abs/2508.17087v1
• Date: Sat, 23 Aug 2025 17:00:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:45.335562
• Title: Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting
• Title（参考訳）: 学習経路生成と最適分割によるMin-Max多重トラベリングセールスマン問題の解法
• Authors: Wen Wang, Xiangchen Wu, Liang Wang, Hao Hu, Xianping Tao, Linghao Zhang,
• Abstract要約: Min-Max Multiple Traveling Salesmen Problemは、複数のセールスマンのツアーをコーディネートすることで、最長ツアーの長さを最小化することを目的としている。 NPハードの性質のため、正確な解法は$P ne NP$という仮定の下で非現実的になる。 我々は,強化学習と最適分割アルゴリズムを統合した2段階のフレームワークである textbfGenerate-and-Split (GaS) を提案する。
• 参考スコア（独自算出の注目度）: 8.941535841606584
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This study addresses the Min-Max Multiple Traveling Salesmen Problem ($m^3$-TSP), which aims to coordinate tours for multiple salesmen such that the length of the longest tour is minimized. Due to its NP-hard nature, exact solvers become impractical under the assumption that $P \ne NP$. As a result, learning-based approaches have gained traction for their ability to rapidly generate high-quality approximate solutions. Among these, two-stage methods combine learning-based components with classical solvers, simplifying the learning objective. However, this decoupling often disrupts consistent optimization, potentially degrading solution quality. To address this issue, we propose a novel two-stage framework named \textbf{Generate-and-Split} (GaS), which integrates reinforcement learning (RL) with an optimal splitting algorithm in a joint training process. The splitting algorithm offers near-linear scalability with respect to the number of cities and guarantees optimal splitting in Euclidean space for any given path. To facilitate the joint optimization of the RL component with the algorithm, we adopt an LSTM-enhanced model architecture to address partial observability. Extensive experiments show that the proposed GaS framework significantly outperforms existing learning-based approaches in both solution quality and transferability.
• Abstract（参考訳）: 本研究は,最長ツアーの長さを最小限に抑えるため,複数のセールスマンを対象としたツアーの調整を目的とした,Min-Max Multiple Traveling Salesmen Problem(m^3$-TSP)に対処する。 NPハードの性質のため、正確な解法は$P \ne NP$という仮定の下で非現実的になる。 その結果、学習に基づくアプローチは、高品質な近似解を迅速に生成する能力によって、注目を集めている。 これらのうち、2段階の手法は学習ベースコンポーネントと古典的解法を結合し、学習目的を単純化する。 しかし、このデカップリングはしばしば一貫した最適化を妨害し、ソリューションの品質を低下させる可能性がある。 そこで本稿では,強化学習(RL)と最適分割アルゴリズムを統合した新しい2段階フレームワークである「textbf{Generate-and-Split} (GaS)」を提案する。 分割アルゴリズムは、都市数に関してほぼ直線的なスケーラビリティを提供し、任意の経路に対してユークリッド空間における最適な分割を保証する。 アルゴリズムとRLコンポーネントの協調最適化を容易にするため,部分観測可能性に対処するLSTM拡張モデルアーキテクチャを採用した。 大規模な実験により,提案したGaSフレームワークは,ソリューションの品質と転送性の両方において,既存の学習ベースアプローチよりも大幅に優れていることがわかった。

関連論文リスト

• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。 提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T17:14:18Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• 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)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。