論文の概要: Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2602.23579v1
• Date: Fri, 27 Feb 2026 01:07:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-02 19:48:24.19164
• Title: Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem
• Title（参考訳）: min-max多重トラベリングセールスマン問題に対する強化学習による構成, マージ, 解, 適応
• Authors: Guillem Rodríguez-Corominas, Maria J. Blesa, Christian Blum,
• Abstract要約: 旅行セールスマン問題 (Multiple Traveling Salesman Problem, MTSP) は、旅行セールスマン問題を、共通の補給所で開始・終了するmツアーに拡張する。 min-max版では、作業負荷のバランスを反映して、最長のツアーを最小限にすることが目的である。 本稿では,RL-CMSA (Construct, Merge, Solve & Adapt with Reinforcement Learning) というハイブリッドアプローチを提案する。
• 参考スコア（独自算出の注目度）: 1.388970969945297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Multiple Traveling Salesman Problem (mTSP) extends the Traveling Salesman Problem to m tours that start and end at a common depot and jointly visit all customers exactly once. In the min-max variant, the objective is to minimize the longest tour, reflecting workload balance. We propose a hybrid approach, Construct, Merge, Solve & Adapt with Reinforcement Learning (RL-CMSA), for the symmetric single-depot min-max mTSP. The method iteratively constructs diverse solutions using probabilistic clustering guided by learned pairwise q-values, merges routes into a compact pool, solves a restricted set-covering MILP, and refines solutions via inter-route remove, shift, and swap moves. The q-values are updated by reinforcing city-pair co-occurrences in high-quality solutions, while the pool is adapted through ageing and pruning. This combination of exact optimization and reinforcement-guided construction balances exploration and exploitation. Computational results on random and TSPLIB instances show that RL-CMSA consistently finds (near-)best solutions and outperforms a state-of-the-art hybrid genetic algorithm under comparable time limits, especially as instance size and the number of salesmen increase.
• Abstract（参考訳）: マルチプルトラベリングセールスマン問題 (Multiple Traveling Salesman Problem, MTSP) は、トラベルセールスマン問題(Traveing Salesman Problem)を、共通のデポで開始・終了するmツアーに拡張し、すべての顧客を正確に1度訪問する。 min-max版では、作業負荷のバランスを反映して、最長のツアーを最小限にすることが目的である。 本稿では,RL-CMSA (Construct, Merge, Solve & Adapt with Reinforcement Learning) というハイブリッドアプローチを提案する。 この方法は、学習したq-値によって導かれる確率的クラスタリングを用いて様々な解を反復的に構築し、ルートをコンパクトプールにマージし、制限されたセットカバーMILPを解き、ルート間除去、シフト、スワップ移動による解を洗練する。 q値は高品質のソリューションで都市とペアの共起を補強することで更新され、プールは老朽化や刈り取りによって適応される。 この厳密な最適化と強化誘導工事の組み合わせは、探索と搾取のバランスを保っている。 ランダムおよびTSPLIBインスタンスの計算結果から、RL-CMSAは(ほぼ)最良解を一貫して見つけ、特にインスタンスサイズやセールスマン数の増加など、同等の時間制限下で最先端のハイブリッド遺伝的アルゴリズムより優れることが示された。

関連論文リスト

• Assignment-Routing Optimization: Solvers for Problems Under Constraints [0.0]
  我々は、アイテムを1対1でプレースホルダーに割り当てなければならないJRA(Joint Routing-Assignment)問題について検討する。 よりリッチな制約付きパッケージング計画シナリオに適した解法を開発した。 以上の結果から, ロボット包装, 運動計画, 複合物流におけるMIPに基づくJRA最適化の実用性を強調した。
  論文  参考訳（メタデータ） (2025-12-21T06:32:31Z)
• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) プルーニング手法は階層的に動作し、階層ごとのプルーニングエラーを最小限に抑え、完全な再トレーニングを回避する。 既存の手法は、刈り上げ対象の重量相互作用を無視する欲求凸に依存する。 提案手法は, 層ごとのプルーニング誤差を大幅に低減し, 最先端のGPTアーキテクチャにおいて高いベースラインを達成し, メモリ効率を保っている。
  論文  参考訳（メタデータ） (2025-10-15T16:13:44Z)
• Solving the Min-Max Multiple Traveling Salesmen Problem via Learning-Based Path Generation and Optimal Splitting [8.941535841606584]
  Min-Max Multiple Traveling Salesmen Problemは、複数のセールスマンのツアーをコーディネートすることで、最長ツアーの長さを最小化することを目的としている。 NPハードの性質のため、正確な解法は$P ne NP$という仮定の下で非現実的になる。 我々は,強化学習と最適分割アルゴリズムを統合した2段階のフレームワークである textbfGenerate-and-Split (GaS) を提案する。
  論文  参考訳（メタデータ） (2025-08-23T17:00:57Z)
• Collab: Controlled Decoding using Mixture of Agents for LLM Alignment [90.6117569025754]
  人間のフィードバックからの強化学習は、大規模言語モデルを整合させる効果的な手法として現れてきた。 制御された復号化は、再訓練せずに推論時にモデルを整列するメカニズムを提供する。 本稿では,既存の既成のLCMポリシを活用するエージェントベースのデコーディング戦略の混合を提案する。
  論文  参考訳（メタデータ） (2025-03-27T17:34:25Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  提案するSEQUOIAは,動作空間に対する長期報酬を直接最適化するRLアルゴリズムである。 我々は,複数介入,経路制約,二部間マッチング,容量制約という,制約を伴う4つの新しいレスレス・バンディット問題に対して,SEQUOIAを実証的に検証した。
  論文  参考訳（メタデータ） (2025-03-01T21:25:21Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem [0.9790236766474201]
  本稿では,Multiple Traveling Salesman Problem (mTSP) を解くためのハイブリッド遺伝的アルゴリズムを提案する。 新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。 我々のアルゴリズムは、ベンチマークセットに対してテストした場合に、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回ります。
  論文  参考訳（メタデータ） (2023-07-14T01:57:10Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems [41.57773395100222]
  深部強化学習(DRL)モデルはNP-hard Combinatorial Optimization問題を解決する上で有望な結果を示している。 本稿では,DIMESという新しいアプローチを提案することによって,大規模最適化におけるスケーラビリティの課題に対処する。 コストのかかる自己回帰的復号法や離散解の反復的洗練に苦しむ従来のDRL法とは異なり、DIMESは候補解の基底分布をパラメータ化するためのコンパクトな連続空間を導入する。 DIMESは、トラベリングセールスマン問題や最大独立セット問題のための大規模なベンチマークデータセットにおいて、最近のDRLベースの手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-08T23:24:37Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection [0.0]
  トラベリング・サレスパーソン・プロブレム(TSP)は、最もよく知られたNPハード最適化問題の1つである。 我々は、不正確なTSPソルバの任意の動作に対処することで、既存のベンチマーク研究を拡張した。 その結果、解法の性能ランキングは、集中した近似品質に大きく依存していることが判明した。
  論文  参考訳（メタデータ） (2020-05-27T11:36:53Z)

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

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