論文の概要: Solving the vehicle routing problem with deep reinforcement learning
- arxiv url: http://arxiv.org/abs/2208.00202v1
- Date: Sat, 30 Jul 2022 12:34:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-02 14:23:26.512371
- Title: Solving the vehicle routing problem with deep reinforcement learning
- Title（参考訳）: 深層強化学習による車両経路問題の解法
- Authors: Simone Foa and Corrado Coppola and Giorgio Grani and Laura Palagi
- Abstract要約: 本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。
第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。
広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, the applications of the methodologies of Reinforcement Learning
(RL) to NP-Hard Combinatorial optimization problems have become a popular
topic. This is essentially due to the nature of the traditional combinatorial
algorithms, often based on a trial-and-error process. RL aims at automating
this process. At this regard, this paper focuses on the application of RL for
the Vehicle Routing Problem (VRP), a famous combinatorial problem that belongs
to the class of NP-Hard problems. In this work, first, the problem is modeled
as a Markov Decision Process (MDP) and then the PPO method (which belongs to
the Actor-Critic class of Reinforcement learning methods) is applied. In a
second phase, the neural architecture behind the Actor and Critic has been
established, choosing to adopt a neural architecture based on the Convolutional
neural networks, both for the Actor and the Critic. This choice resulted in
effectively addressing problems of different sizes. Experiments performed on a
wide range of instances show that the algorithm has good generalization
capabilities and can reach good solutions in a short time. Comparisons between
the algorithm proposed and the state-of-the-art solver OR-TOOLS show that the
latter still outperforms the Reinforcement learning algorithm. However, there
are future research perspectives, that aim to upgrade the current performance
of the algorithm proposed.
- Abstract（参考訳）: 近年,NP-Hard Combinatorial 最適化問題に対する強化学習(RL)の方法論の適用が注目されている。
これは本質的には従来の組合せアルゴリズムの性質によるもので、しばしば試行錯誤プロセスに基づいている。
rlはこのプロセスの自動化を目指している。
本稿では,NP-Hard 問題に属する有名な組合せ問題である Vehicle Routing Problem (VRP) に対する RL の適用に焦点をあてる。
本稿では,まず,マルコフ決定過程(mdp)として問題をモデル化し,その後,ppo法(強化学習手法のアクタ批判クラスに属する)を適用する。
第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、アクターと批評家の両方に対して、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することを選んだ。
この選択は、異なるサイズの問題に効果的に対処する結果となった。
広範囲のインスタンスで実施された実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
提案したアルゴリズムと最先端の解法OR-TOOLSを比較すると、後者は強化学習アルゴリズムよりも優れていることがわかる。
しかし,提案アルゴリズムの現在の性能向上を目的とした今後の研究展望がある。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
我々は、中間的監督に訴えることなく、入出力ペアからのみニューラルネットワーク推論を学ぶことに集中する。
我々は、アルゴリズムの軌跡にアクセスできることなく、モデルの中間計算を正規化できる自己教師対象を構築する。
CLRSic Algorithmic Reasoning Benchmarkのタスクにおいて,提案手法はトラジェクトリを教師する手法と競合することを示す。
論文 参考訳（メタデータ） (2023-06-23T09:57:44Z) - Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。
私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。
以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
論文 参考訳（メタデータ） (2023-05-18T13:59:02Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Reinforcement Learning to Solve NP-hard Problems: an Application to the
CVRP [0.0]
古典的最適化問題の解法として強化学習(Reinforcement Learning, RL)を応用した。
最も有望なRLアプローチの2つを、ベンチマークインスタンスのセットで従来の問題解決手法と比較する。
最良解を返さないにもかかわらず、RLアプローチは従来の解法よりも多くの利点があることがわかった。
論文 参考訳（メタデータ） (2022-01-14T11:16:17Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳（メタデータ） (2021-07-15T02:13:03Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳（メタデータ） (2021-03-10T03:16:12Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳（メタデータ） (2021-01-08T18:55:07Z) - Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。
高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。
我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
論文 参考訳（メタデータ） (2020-11-09T10:57:21Z) - Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。
強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
論文 参考訳（メタデータ） (2020-03-07T16:19:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。