論文の概要: Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem

• arxiv url: http://arxiv.org/abs/2507.21386v1
• Date: Mon, 28 Jul 2025 23:38:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-30 17:08:55.373388
• Title: Efficient Neural Combinatorial Optimization Solver for the Min-max Heterogeneous Capacitated Vehicle Routing Problem
• Title（参考訳）: Min-max不均一キャパシタン化車両ルーティング問題に対する効率的なニューラルコンビネーション最適化法
• Authors: Xuan Wu, Di Wang, Chunguo Wu, Kaifang Qi, Chunyan Miao, Yubin Xiao, Jian Zhang, You Zhou,
• Abstract要約: 既存のNCOソルバは、通常、各デコードステップを訪問するために車両とその次のノードを選択するが、多くの場合、ミオピック復号決定を行い、MMHCVRPの重要な特性を見落としている。 これらの制約に対処するため,効率的なNCO解法ECHOを提案する。 ECHOは、さまざまな車両やノードで最先端のNCOソルバより優れており、スケールと分散パターンの両方にわたって、良好なパフォーマンスの一般化を示している。
• 参考スコア（独自算出の注目度）: 44.53289422887474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Numerous Neural Combinatorial Optimization (NCO) solvers have been proposed to address Vehicle Routing Problems (VRPs). However, most of these solvers focus exclusively on single-vehicle VRP variants, overlooking the more realistic min-max Heterogeneous Capacitated Vehicle Routing Problem (MMHCVRP), which involves multiple vehicles. Existing MMHCVRP solvers typically select a vehicle and its next node to visit at each decoding step, but often make myopic decoding decisions and overlook key properties of MMHCVRP, including local topological relationships, vehicle permutation invariance, and node symmetry, resulting in suboptimal performance. To better address these limitations, we propose ECHO, an efficient NCO solver. First, ECHO exploits the proposed dual-modality node encoder to capture local topological relationships among nodes. Subsequently, to mitigate myopic decisions, ECHO employs the proposed Parameter-Free Cross-Attention mechanism to prioritize the vehicle selected in the preceding decoding step. Finally, leveraging vehicle permutation invariance and node symmetry, we introduce a tailored data augment strategy for MMHCVRP to stabilize the Reinforcement Learning training process. To assess the performance of ECHO, we conduct extensive experiments. The experimental results demonstrate that ECHO outperforms state-of-the-art NCO solvers across varying numbers of vehicles and nodes, and exhibits well-performing generalization across both scales and distribution patterns. Finally, ablation studies validate the effectiveness of all proposed methods.
• Abstract（参考訳）: 車両ルーティング問題(VRP)に対処するために、多くのニューラルコンビネーション最適化(NCO)の解法が提案されている。 しかし、これらの解法のほとんどは、より現実的なMMHCVRP(Min-max Heterogeneous Capacitated Vehicle Routing Problem)を見渡して、単車用VRPのみに焦点を当てている。 既存のMMHCVRPソルバは、通常、各デコードステップで車両とその次のノードを選択するが、しばしば、局所的トポロジ的関係、車両の置換不変性、ノード対称性を含む、MMHCVRPの重要な特性を心筋復号化決定および見落とし、最適性能をもたらす。 これらの制約に対処するため,効率的なNCO解法ECHOを提案する。 まず、ECHOは提案したデュアルモードノードエンコーダを利用して、ノード間の局所的トポロジ的関係をキャプチャする。 その後、筋電図決定を緩和するため、ECHOは提案されたパラメータフリークロスアテンション機構を使用して、前回の復号ステップで選択した車両を優先する。 最後に,車両の変分不変性とノード対称性を活用することで,MMHCVRPのためのデータ拡張戦略を導入し,強化学習学習プロセスの安定化を図る。 ECHOの性能を評価するため,我々は広範囲な実験を行った。 実験の結果,ECHOは車両やノードの多種多様で最先端のNCOソルバよりも優れており,スケールと分布パターンの双方にわたって高い性能の一般化を示すことがわかった。 最後に、アブレーション研究は全ての提案手法の有効性を検証した。

関連論文リスト

• Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation [10.153136816705542]
  POCCOはサブプロブレムのためのモデル構造を適応的に選択できる新しいプラグイン・アンド・プレイフレームワークである。 そこで本研究では,勝利と敗退の間のペアワイズな選好を学習する選好駆動最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-10T15:25:06Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。 WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
  論文  参考訳（メタデータ） (2024-07-18T02:46:06Z)
• DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems [26.48767051423456]
  本稿では、分割とナビゲーションのための異なる埋め込みを学習する、新しいアテンションベースのパーティション・アンド・ナビゲーション・エンコーダ(P&N)を提案する。 エージェント置換対称損失関数(APS)を開発した。
  論文  参考訳（メタデータ） (2024-05-27T15:33:16Z)
• Ensemble Kalman Filtering Meets Gaussian Process SSM for Non-Mean-Field and Online Inference [47.460898983429374]
  我々は,非平均場(NMF)変動推定フレームワークにアンサンブルカルマンフィルタ(EnKF)を導入し,潜在状態の後方分布を近似する。 EnKFとGPSSMのこの新しい結婚は、変分分布の学習における広範なパラメータ化の必要性をなくすだけでなく、エビデンスの下限(ELBO)の解釈可能でクローズドな近似を可能にする。 得られたEnKF支援オンラインアルゴリズムは、データ適合精度を確保しつつ、モデル正規化を組み込んで過度適合を緩和し、目的関数を具現化する。
  論文  参考訳（メタデータ） (2023-12-10T15:22:30Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• 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)
• Greedy based Value Representation for Optimal Coordination in Multi-agent Reinforcement Learning [64.05646120624287]
  LVDとMVDの結合Q値関数を導出する。 最適な整合性を確保するために、最適なノードは独自のSTNである必要がある。 本手法は,様々なベンチマーク実験において,最先端のベースラインよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-22T08:14:50Z)
• Multi-Agent Deep Reinforcement Learning in Vehicular OCC [14.685237010856953]
  我々は車載OCCにおけるスペクトル効率最適化手法を提案する。 我々は最適化問題をマルコフ決定プロセス(MDP)としてモデル化し、オンラインで適用可能なソリューションの利用を可能にする。 提案手法の性能を広範囲なシミュレーションにより検証し,提案手法の様々な変種とランダムな手法との比較を行った。
  論文  参考訳（メタデータ） (2022-05-05T14:25:54Z)
• RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
  入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。 この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。 ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
  論文  参考訳（メタデータ） (2021-10-27T05:37:12Z)
• Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem [13.389057146418056]
  現実のシナリオにおける車両は、その能力(または走行速度)に影響を与える異なる特徴を持つ異種である可能性が高い 異種艦隊制約を考慮した車両選択デコーダと経路構成を考慮したノード選択デコーダとを併用した注意機構に基づくDRL手法を提案し,各ステップで車両とノードの両方を自動的に選択して解を構築することを学習する。
  論文  参考訳（メタデータ） (2021-10-06T10:05:19Z)

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

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