論文の概要: Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees

• arxiv url: http://arxiv.org/abs/2505.24627v1
• Date: Fri, 30 May 2025 14:21:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-02 19:47:52.994151
• Title: Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees
• Title（参考訳）: 拘束強度の異なる車両経路問題に対するニューラルコンビネーション最適化の再考
• Authors: Fu Luo, Yaoxin Wu, Zhi Zheng, Zhenkun Wang,
• Abstract要約: 最近のニューラル最適化(NCO)手法は、ドメイン固有の専門知識を必要としない、有望な問題解決能力を示している。 本稿では,キャパシティ制約の厳密度が異なるNCO性能を実験的に解析するために,キャパシティ制約付き車両ルーティング問題(CVRP)を例に挙げる。 本研究では,制約のきつい度合いを明示的に考慮した効率的なトレーニング手法を開発し,汎用的な解法を学習するためのマルチエキスパートモジュールを提案する。
• 参考スコア（独自算出の注目度）: 9.589351848592928
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent neural combinatorial optimization (NCO) methods have shown promising problem-solving ability without requiring domain-specific expertise. Most existing NCO methods use training and testing data with a fixed constraint value and lack research on the effect of constraint tightness on the performance of NCO methods. This paper takes the capacity-constrained vehicle routing problem (CVRP) as an example to empirically analyze the NCO performance under different tightness degrees of the capacity constraint. Our analysis reveals that existing NCO methods overfit the capacity constraint, and they can only perform satisfactorily on a small range of the constraint values but poorly on other values. To tackle this drawback of existing NCO methods, we develop an efficient training scheme that explicitly considers varying degrees of constraint tightness and proposes a multi-expert module to learn a generally adaptable solving strategy. Experimental results show that the proposed method can effectively overcome the overfitting issue, demonstrating superior performances on the CVRP and CVRP with time windows (CVRPTW) with various constraint tightness degrees.
• Abstract（参考訳）: 最近のニューラルコンビナトリ最適化(NCO)手法は、ドメイン固有の専門知識を必要としない、有望な問題解決能力を示している。 既存のNCO法の多くは、一定の制約値を持つトレーニングとテストデータを使用し、NCO法の性能に対する制約厳密性の影響についての研究を欠いている。 本稿では,キャパシティ制約の厳密度が異なるNCO性能を実験的に解析するために,キャパシティ制約付き車両ルーティング問題(CVRP)を例に挙げる。 分析の結果,既存のNCO法は容量制約を過度に満たし,制約値の小さな範囲でのみ満足できるが,他の値では不十分であることがわかった。 既存のNCO手法の欠点に対処するため,制約のきつい度合いを明確に考慮した効率的なトレーニング手法を開発し,汎用的な解法戦略を学ぶためのマルチエキスパートモジュールを提案する。 実験の結果,提案手法は,時間窓(CVRPTW)によるCVRPおよびCVRPの性能を,様々な制約の厳密度で評価し,オーバーフィッティング問題を効果的に克服できることが示唆された。

関連論文リスト

• CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention [21.554370739508528]
  本稿では,車両経路問題に対する制約対応デュアルアテンションモデル(CaDA)を提案する。 CaDAは、異なる問題変種を効率的に表現する制約プロンプトを組み込んでいる。 より広範なグラフ情報を取得するためのグローバルブランチを備えたデュアルアテンション機構を備えている。
  論文  参考訳（メタデータ） (2024-11-30T04:11:36Z)
• Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization [7.85458999849461]
  我々は,拡散モデルをゼロから直接訓練する,教師なしCOフレームワークであるIC/DCを提案する。 私たちは、問題固有の制約を順守しながら、ソリューションのコストを最小限に抑えるために、自己監督的な方法でモデルをトレーニングします。 並列マシンスケジューリング問題(PMSP)と非対称トラベリングセールスマン問題(ATSP)における既存のNCO手法と比較して、IC/DCは最先端の性能を達成する
  論文  参考訳（メタデータ） (2024-10-15T06:53:30Z)
• Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization [53.15874572081944]
  ディープラーニングフレームワークにおける計算可能性について,2つの観点から検討する。 根底にある問題が十分に解決された場合でも、ディープニューラルネットワークを訓練する際のアルゴリズム上の制限を示す。 最後に、分類と深層ネットワークトレーニングの定量化バージョンにおいて、計算可能性の制限は発生せず、一定の程度まで克服可能であることを示す。
  論文  参考訳（メタデータ） (2024-08-12T15:02:26Z)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver [15.842155380912002]
  本稿では,ニューラル・ルーティング・ソルバの大規模一般化のための新しいインスタンス・コンディション・アダプタ・モデルを提案する。 提案手法は,非常に高速な推論時間で有望な結果が得られることを示す。
  論文  参考訳（メタデータ） (2024-05-03T08:00:19Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep Unrolling(ディープ・アンローリング)は、トレーニング可能なニューラルネットワークの層に切り捨てられた反復アルゴリズムをアンロールする、新たな学習最適化手法である。 アンロールネットワークの収束保証と一般化性は、いまだにオープンな理論上の問題であることを示す。 提案した制約の下で訓練されたアンロールアーキテクチャを2つの異なるアプリケーションで数値的に評価する。
  論文  参考訳（メタデータ） (2023-12-25T18:51:23Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。 本稿では,CVRPの車両容量制約を回避できる最短経路を最小化する目的機能を備えた,CVRP用の新しいバイナリエンコーディングを提案する。 本稿では,量子交換演算子Ansatzの変種に基づく符号化の有効性について論じる。
  論文  参考訳（メタデータ） (2023-08-17T05:14:43Z)
• Solving Continuous Control via Q-learning [54.05120662838286]
  深いQ-ラーニングの簡単な修正は、アクター批判的手法による問題を大幅に軽減することを示します。 バンバン動作の離散化と値分解、協調マルチエージェント強化学習(MARL)としての単一エージェント制御のフレーミングにより、このシンプルな批判のみのアプローチは、最先端の連続アクター批判法の性能と一致する。
  論文  参考訳（メタデータ） (2022-10-22T22:55:50Z)
• Chance-Constrained Control with Lexicographic Deep Reinforcement Learning [77.34726150561087]
  本稿では,レキシックなDeep Reinforcement Learning(DeepRL)に基づく確率制約マルコフ決定プロセスを提案する。 有名なDeepRLアルゴリズムDQNの辞書版も提案され、シミュレーションによって検証されている。
  論文  参考訳（メタデータ） (2020-10-19T13:09:14Z)

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

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