Fugu-MT 論文翻訳(概要): DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems

論文の概要: DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems

arxiv url: http://arxiv.org/abs/2405.17272v1
Date: Mon, 27 May 2024 15:33:16 GMT
ステータス: 処理完了
システム内更新日: 2024-05-28 14:43:44.313871
Title: DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems
Title（参考訳）: DPN:ミニマックス車両ルーティング問題におけるニューラルソルバーの分離とナビゲーション
Authors: Zhi Zheng, Shunyu Yao, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, Ke Tang,
Abstract要約: 本稿では、分割とナビゲーションのための異なる埋め込みを学習する、新しいアテンションベースのパーティション・アンド・ナビゲーション・エンコーダ(P&N)を提案する。エージェント置換対称損失関数(APS)を開発した。
参考スコア（独自算出の注目度）: 26.48767051423456
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The min-max vehicle routing problem (min-max VRP) traverses all given customers by assigning several routes and aims to minimize the length of the longest route. Recently, reinforcement learning (RL)-based sequential planning methods have exhibited advantages in solving efficiency and optimality. However, these methods fail to exploit the problem-specific properties in learning representations, resulting in less effective features for decoding optimal routes. This paper considers the sequential planning process of min-max VRPs as two coupled optimization tasks: customer partition for different routes and customer navigation in each route (i.e., partition and navigation). To effectively process min-max VRP instances, we present a novel attention-based Partition-and-Navigation encoder (P&N Encoder) that learns distinct embeddings for partition and navigation. Furthermore, we utilize an inherent symmetry in decoding routes and develop an effective agent-permutation-symmetric (APS) loss function. Experimental results demonstrate that the proposed Decoupling-Partition-Navigation (DPN) method significantly surpasses existing learning-based methods in both single-depot and multi-depot min-max VRPs. Our code is available at
Abstract（参考訳）: min-maxの車両ルーティング問題(min-max VRP)は、いくつかのルートを割り当て、最長ルートの長さを最小化することを目的として、与えられたすべての顧客を横断する。近年,強化学習(RL)に基づく逐次計画手法は,解法効率と最適性に優位性を示した。しかし、これらの手法は、学習表現における問題固有の特性を利用することができず、最適経路の復号化にはあまり効果がない。本稿では,Min-max VRPの逐次計画過程を,異なる経路の顧客分割と各経路の顧客ナビゲーション(パーティションとナビゲーション)の2つの複合最適化タスクとして考察する。 min-max VRPインスタンスを効果的に処理するために,パーティション・アンド・ナビゲーション・エンコーダ(P&Nエンコーダ)を提案する。さらに、復号経路に固有の対称性を利用し、効果的なエージェント置換対称損失関数(APS)を開発する。実験結果から,DPN法が従来の学習手法よりはるかに優れていることが示された。私たちのコードは利用可能です

関連論文リスト

RouteFinder: Towards Foundation Models for Vehicle Routing Problems [18.158173261177186]
車両ルーティング問題(英: Vehicle Routing Problems、VRP)は、現実世界に重大な影響を及ぼす最適化問題である。個々のVRPの変種を解決するための学習の進歩にもかかわらず、統一されたアプローチは欠如している。本稿ではVRPの基礎モデルを開発するためのフレームワークであるRouteFinderを紹介する。
論文参考訳（メタデータ） (2024-06-21T09:34:26Z)
An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。まず,方向対応型注意モデル(DaAM)を提案する。第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文参考訳（メタデータ） (2024-03-11T02:17:42Z)
Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文参考訳（メタデータ） (2023-10-22T02:46:37Z)
A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
論文参考訳（メタデータ） (2023-09-02T11:01:16Z)
Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
本稿では,VRPにおけるサイズと分布の両面での一般化を考慮した,挑戦的かつ現実的な設定について検討する。提案するメタラーニングフレームワークは,推論中に新しいタスクに迅速に適応する能力を持つモデルを効果的に学習することを可能にする。
論文参考訳（メタデータ） (2023-05-31T06:14:34Z)
Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
論文参考訳（メタデータ） (2022-03-03T03:46:18Z)
Learning Space Partitions for Path Planning [54.475949279050596]
PlaLaMは2次元ナビゲーションタスクにおける既存の経路計画手法よりも優れており、特に難解な局所最適化の存在下では優れている。これらは高マルチモーダルな実世界のタスクに移行し、コンパイラフェーズでは最大245%、分子設計では最大0.4の強いベースラインを0-1スケールで上回ります。
論文参考訳（メタデータ） (2021-06-19T18:06:11Z)
Waypoint Planning Networks [66.72790309889432]
本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。 WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
論文参考訳（メタデータ） (2021-05-01T18:02:01Z)
Integrated Decision and Control: Towards Interpretable and Efficient Driving Intelligence [13.589285628074542]
自動走行車のための解釈可能かつ効率的な意思決定・制御フレームワークを提案する。駆動タスクを階層的に構造化されたマルチパス計画と最適追跡に分解する。その結果,オンライン計算の効率性や交通効率,安全性などの運転性能が向上した。
論文参考訳（メタデータ） (2021-03-18T14:43:31Z)
Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文参考訳（メタデータ） (2021-02-23T15:33:57Z)
Using Deep Reinforcement Learning Methods for Autonomous Vessels in 2D Environments [11.657524999491029]
本研究では,Q-Learningとニューラル表現を組み合わせた深層強化学習を用いて不安定性を回避する。当社の方法論では,Q-Learningを深く使用して,アジャイル方法論のローリングウェーブプランニングアプローチと組み合わせています。実験の結果,VVNの長距離ミッションの平均性能は55.31倍に向上した。
論文参考訳（メタデータ） (2020-03-23T12:58:58Z)

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

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