論文の概要: RP-DQN: An application of Q-Learning to Vehicle Routing Problems
- arxiv url: http://arxiv.org/abs/2104.12226v1
- Date: Sun, 25 Apr 2021 18:28:35 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-28 04:42:04.363909
- Title: RP-DQN: An application of Q-Learning to Vehicle Routing Problems
- Title(参考訳): RP-DQN:Qラーニングの車両ルーティング問題への応用
- Authors: Ahmad Bdeir, Simon Boeder, Tim Dernedde, Kirill Tkachuk, Jonas K.
Falkner, Lars Schmidt-Thieme
- Abstract要約: 提案手法は,CVRP上でノードを逐次挿入してソリューションを構築する自動回帰ポリシーの最先端性能を実現する。
我々は、mdvrpに機械学習手法で取り組み、この問題タイプが、他のmlメソッドよりも我々のアプローチから大きな利益を得られることを実証した。
- 参考スコア(独自算出の注目度): 2.6750287043724303
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In this paper we present a new approach to tackle complex routing problems
with an improved state representation that utilizes the model complexity better
than previous methods. We enable this by training from temporal differences.
Specifically Q-Learning is employed. We show that our approach achieves
state-of-the-art performance for autoregressive policies that sequentially
insert nodes to construct solutions on the CVRP. Additionally, we are the first
to tackle the MDVRP with machine learning methods and demonstrate that this
problem type greatly benefits from our approach over other ML methods.
- Abstract(参考訳): 本稿では,従来の手法よりも複雑なモデルを用いた状態表現を改良し,複雑なルーティング問題に対処する新しい手法を提案する。
これを時間差からトレーニングすることで実現します。
特にQ-Learningが採用されている。
提案手法は,CVRP上でノードを逐次挿入してソリューションを構築する自動回帰ポリシーの最先端性能を実現する。
さらに、機械学習メソッドでmdvrpに最初に取り組み、この問題タイプが、他のmlメソッドよりも我々のアプローチのメリットが大きいことを実証します。
関連論文リスト
- 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) - Solving the vehicle routing problem with deep reinforcement learning [0.0]
本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。
第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。
広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
論文 参考訳(メタデータ) (2022-07-30T12:34:26Z) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳(メタデータ) (2022-07-04T14:31:47Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z) - SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems [4.777801093677586]
我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。
RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。
この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
論文 参考訳(メタデータ) (2021-04-04T17:12:24Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳(メタデータ) (2021-02-23T15:33:57Z) - Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。
これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。
より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
論文 参考訳(メタデータ) (2020-12-24T14:18:56Z) - Logistic Q-Learning [87.00813469969167]
MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。
提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
論文 参考訳(メタデータ) (2020-10-21T17:14:31Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳(メタデータ) (2020-06-17T20:19:25Z) - Deep Unfolding Network for Image Super-Resolution [159.50726840791697]
本稿では,学習に基づく手法とモデルに基づく手法の両方を活用する,エンドツーエンドのトレーニング可能なアンフォールディングネットワークを提案する。
提案するネットワークは, モデルベース手法の柔軟性を継承し, 一つのモデルを用いて, 異なるスケール要因に対する, 曖昧でノイズの多い画像の超解像化を行う。
論文 参考訳(メタデータ) (2020-03-23T17:55:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。