論文の概要: Off-line approximate dynamic programming for the vehicle routing problem
with stochastic customers and demands via decentralized decision-making
- arxiv url: http://arxiv.org/abs/2109.10200v1
- Date: Tue, 21 Sep 2021 14:28:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-22 14:14:28.511739
- Title: Off-line approximate dynamic programming for the vehicle routing problem
with stochastic customers and demands via decentralized decision-making
- Title（参考訳）: 確率的顧客による車両経路問題に対するオフライン近似動的計画法と分散意思決定による要求
- Authors: Mohsen Dastpak and Fausto Errico
- Abstract要約: 本稿では,顧客の位置と需要が不確実な車両経路問題(VRP)の変種について検討する。
目的は、車両の容量と時間制限を満たしながら、提供された要求を最大化することである。
本稿では,Replay MemoryやDouble Q Networkといった最先端のアクセラレーション技術を用いたQラーニングアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: This paper studies a stochastic variant of the vehicle routing problem (VRP)
where both customer locations and demands are uncertain. In particular,
potential customers are not restricted to a predefined customer set but are
continuously spatially distributed in a given service area. The objective is to
maximize the served demands while fulfilling vehicle capacities and time
restrictions. We call this problem the VRP with stochastic customers and
demands (VRPSCD). For this problem, we first propose a Markov Decision Process
(MDP) formulation representing the classical centralized decision-making
perspective where one decision-maker establishes the routes of all vehicles.
While the resulting formulation turns out to be intractable, it provides us
with the ground to develop a new MDP formulation of the VRPSCD representing a
decentralized decision-making framework, where vehicles autonomously establish
their own routes. This new formulation allows us to develop several strategies
to reduce the dimension of the state and action spaces, resulting in a
considerably more tractable problem. We solve the decentralized problem via
Reinforcement Learning, and in particular, we develop a Q-learning algorithm
featuring state-of-the-art acceleration techniques such as Replay Memory and
Double Q Network. Computational results show that our method considerably
outperforms two commonly adopted benchmark policies (random and heuristic).
Moreover, when comparing with existing literature, we show that our approach
can compete with specialized methods developed for the particular case of the
VRPSCD where customer locations and expected demands are known in advance.
Finally, we show that the value functions and policies obtained by our
algorithm can be easily embedded in Rollout algorithms, thus further improving
their performances.
- Abstract（参考訳）: 本稿では,顧客の位置と需要が不確実な車両経路問題(VRP)の確率的変種について検討する。
特に、潜在的な顧客は事前に定義された顧客セットに制限されず、特定のサービス領域に継続的に空間的に分散されます。
目的は、車両の容量と時間制限を満たしながら、提供された要求を最大化することである。
私たちはこの問題を、確率的顧客と要求(vrpscd)によるvrpと呼んでいる。
そこで我々はまず,一台の意思決定者が全車両の経路を確立するという古典的中央集権的意思決定の視点を表現したマルコフ決定プロセス(MDP)を提案する。
結果として得られる定式化は難航するが、車両が自律的に独自のルートを確立する分散型意思決定フレームワークを表すVRPSCDの新しいMDP定式化を開発するための基盤を提供する。
この新しい定式化により、状態とアクション空間の次元を減らすためのいくつかの戦略を開発することができ、結果としてかなり扱いやすい問題になってしまう。
本稿では,Reinforcement Learningによる分散化問題を解くとともに,Replay MemoryやDouble Q Networkといった最先端のアクセラレーション技術を用いたQ学習アルゴリズムを開発した。
計算結果から,本手法は一般に採用されている2つのベンチマークポリシー(ランダムとヒューリスティック)をかなり上回る結果となった。
また,既存の文献と比較すると,顧客の位置や期待需要が事前に分かっているvrpscdの特定のケースで開発された専門的な手法と競合できることを示す。
最後に,本アルゴリズムで得られた値関数とポリシーをロールアウトアルゴリズムに簡単に組み込むことができ,性能が向上することを示す。
関連論文リスト
- Dynamic Demand Management for Parcel Lockers [0.0]
本研究では,逐次決定分析と強化学習に根ざしたアルゴリズム手法を編成するソリューションフレームワークを開発する。
これらのテクニックを組み合わせるための革新的なアプローチは、この2つの意思決定タイプ間の強い相互関係に対処する上で有効です。
本手法は筋電図のベンチマークを13.7%上回り、業界に触発された政策を12.6%上回る結果となった。
論文 参考訳（メタデータ） (2024-09-08T11:38:48Z) - Decentralized Semantic Traffic Control in AVs Using RL and DQN for Dynamic Roadblocks [9.485363025495225]
車両自体にセマンティックエンコーディングの責務を委譲するセマンティックトラフィック制御システムを提案する。
このシステムは、強化学習(RL)エージェントから得られる意思決定を処理し、意思決定プロセスの合理化を行う。
論文 参考訳（メタデータ） (2024-06-26T20:12:48Z) - Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文 参考訳（メタデータ） (2023-10-22T02:46:37Z) - No-Regret Learning in Two-Echelon Supply Chain with Unknown Demand
Distribution [48.27759561064771]
我々は[Cachon and Zipkin, 1999]で導入された2つのエケロンサプライチェーンモデルについて, 2つの異なる設定で検討する。
両設定の最適在庫決定に対する後悔と収束の両面において良好な保証を達成するアルゴリズムを設計する。
私たちのアルゴリズムは、オンライングラディエントDescentとOnline Newton Stepをベースとしています。
論文 参考訳（メタデータ） (2022-10-23T08:45:39Z) - Reinforcement Learning with a Terminator [80.34572413850186]
我々は, TerMDP のパラメータを学習し, 推定問題の構造を活用し, 状態ワイドな信頼境界を提供する。
我々はこれらを用いて証明可能な効率のよいアルゴリズムを構築し、終端を考慮し、その後悔を抑える。
論文 参考訳（メタデータ） (2022-05-30T18:40:28Z) - SABER: Data-Driven Motion Planner for Autonomously Navigating
Heterogeneous Robots [112.2491765424719]
我々は、データ駆動型アプローチを用いて、異種ロボットチームをグローバルな目標に向けてナビゲートする、エンドツーエンドのオンラインモーションプランニングフレームワークを提案する。
モデル予測制御(SMPC)を用いて,ロボット力学を満たす制御入力を計算し,障害物回避時の不確実性を考慮した。
リカレントニューラルネットワークは、SMPC有限時間地平線解における将来の状態の不確かさを素早く推定するために用いられる。
ディープQ学習エージェントがハイレベルパスプランナーとして機能し、SMPCにロボットを望ましいグローバルな目標に向けて移動させる目標位置を提供する。
論文 参考訳（メタデータ） (2021-08-03T02:56:21Z) - H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi
Dispatch [9.35511513240868]
H-TD2はモデルフリーで適応的な意思決定アルゴリズムであり、動的な都市環境下で多数の自動タクシーを協調する。
計算複雑性と個別のタクシー政策の限定された部分最適化とのトレードオフを明示的に制御するために、2つの行動の間のトリガ条件を記述・規定する。
最近の強化学習ディスパッチ法とは異なり、このポリシ推定はトレーニング外ドメインイベントに適応し、堅牢である。
論文 参考訳（メタデータ） (2021-05-05T15:42:31Z) - AdaPool: A Diurnal-Adaptive Fleet Management Framework using Model-Free
Deep Reinforcement Learning and Change Point Detection [34.77250498401055]
本稿では,車いすによる乗り合い環境における日中パターンを認識・適応できる適応型モデルフリー深部強化手法を提案する。
本論文では, 配車における適応論理に加えて, 動的かつ需要に応じた車両通行者マッチングと経路計画の枠組みを提案する。
論文 参考訳（メタデータ） (2021-04-01T02:14:01Z) - Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。
このアプローチは多くの実装と最適化の課題をもたらします。
提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
論文 参考訳（メタデータ） (2021-03-18T14:26:26Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。
深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
論文 参考訳（メタデータ） (2020-03-19T13:10:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。