論文の概要: Deep Policy Dynamic Programming for Vehicle Routing Problems
- arxiv url: http://arxiv.org/abs/2102.11756v1
- Date: Tue, 23 Feb 2021 15:33:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-24 14:06:33.722890
- Title: Deep Policy Dynamic Programming for Vehicle Routing Problems
- Title(参考訳): 自動車ルーティング問題に対するDeep Policy Dynamic Programming
- Authors: Wouter Kool, Herke van Hoof, Joaquim Gromicho and Max Welling
- Abstract要約: 本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
- 参考スコア(独自算出の注目度): 89.96386273895985
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Routing problems are a class of combinatorial problems with many practical
applications. Recently, end-to-end deep learning methods have been proposed to
learn approximate solution heuristics for such problems. In contrast, classical
dynamic programming (DP) algorithms can find optimal solutions, but scale badly
with the problem size. We propose Deep Policy Dynamic Programming (DPDP), which
aims to combine the strengths of learned neural heuristics with those of DP
algorithms. DPDP prioritizes and restricts the DP state space using a policy
derived from a deep neural network, which is trained to predict edges from
example solutions. We evaluate our framework on the travelling salesman problem
(TSP) and the vehicle routing problem (VRP) and show that the neural policy
improves the performance of (restricted) DP algorithms, making them competitive
to strong alternatives such as LKH, while also outperforming other `neural
approaches' for solving TSPs and VRPs with 100 nodes.
- Abstract(参考訳): ルーティング問題は、多くの実用的な応用を伴う組合せ問題の一種である。
近年,このような問題に対する近似解ヒューリスティックスを学ぶために,エンドツーエンドのディープラーニング手法が提案されている。
対照的に、古典的動的プログラミング (DP) アルゴリズムは最適解を見つけることができるが、問題のサイズに悪影響を及ぼす。
学習したニューラルヒューリスティックの強みとDPアルゴリズムの強みを組み合わせることを目的としたDeep Policy Dynamic Programming(DPDP)を提案する。
DPDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
我々は、旅行セールスマン問題(TSP)と車両ルーティング問題(VRP)の枠組みを評価し、ニューラルネットワークが(制限された)DPアルゴリズムの性能を改善し、LKHのような強力な代替品と競合し、TSPやVRPを100ノードで解くための他の「神経的アプローチ」よりも優れていることを示す。
関連論文リスト
- 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 [22.596169773500094]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文 参考訳(メタデータ) (2023-10-22T02:46:37Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。
シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
論文 参考訳(メタデータ) (2022-09-15T07:22:58Z) - Solving the vehicle routing problem with deep reinforcement learning [0.0]
本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。
第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。
広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
論文 参考訳(メタデータ) (2022-07-30T12:34:26Z) - Processing Network Controls via Deep Reinforcement Learning [0.0]
論文は、理論上の正当化と、高度なポリシー勾配アルゴリズムの実用化に関するものである。
政策改善バウンダリは、APGアルゴリズムの理論的正当性において重要な役割を果たす。
論文 参考訳(メタデータ) (2022-05-01T04:34:21Z) - Neural Stochastic Dual Dynamic Programming [99.80617899593526]
我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。
$nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
論文 参考訳(メタデータ) (2021-12-01T22:55:23Z) - Deep Reinforcement Learning for Field Development Optimization [0.0]
本研究の目的は,畳み込みニューラルネットワーク(CNN)深部強化学習(DRL)アルゴリズムをフィールド開発最適化問題に適用することである。
近似ポリシー最適化 (PPO) アルゴリズムは2つのCNNアーキテクチャで様々な層と構成を持つ。
両ネットワークは、ハイブリッド粒子群最適化(PSO-MADS)アルゴリズムと比較して満足な結果をもたらすポリシーを得た。
論文 参考訳(メタデータ) (2020-08-05T06:26:13Z) - Learning High-Level Policies for Model Predictive Control [54.00297896763184]
Model Predictive Control (MPC)は、ロボット制御タスクに対する堅牢なソリューションを提供する。
ニューラルネットワークの高レベルポリシーを学習するための自己教師付き学習アルゴリズムを提案する。
提案手法は, 標準的なMPCでは困難な状況に対処できることを示す。
論文 参考訳(メタデータ) (2020-07-20T17:12:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。