論文の概要: Dynamic Vehicle Routing Problem: A Monte Carlo approach
- arxiv url: http://arxiv.org/abs/2006.09996v1
- Date: Mon, 15 Jun 2020 23:10:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 02:29:29.336998
- Title: Dynamic Vehicle Routing Problem: A Monte Carlo approach
- Title（参考訳）: 動的車両ルーティング問題:モンテカルロのアプローチ
- Authors: Micha{\l} Okulewicz and Jacek Ma\'ndziuk
- Abstract要約: 動的車両問題(DVRP)における着信要求の動的性質に直接アプローチするモンテカルロ法(MCTree)を提案する。
また,従来の2相マルチスワーム粒子群最適化 (2MPSO) アルゴリズムを用いてMCTree+PSOをハイブリダイズした。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we solve the Dynamic Vehicle Routing Problem (DVRP). DVRP is a
modification of the Vehicle Routing Problem, in which the clients' requests
(cities) number and location might not be known at the beginning of the working
day Additionally, all requests must be served during one working day by a fleet
of vehicles with limited capacity. In this work we propose a Monte Carlo method
(MCTree), which directly approaches the dynamic nature of arriving requests in
the DVRP. The method is also hybridized (MCTree+PSO) with our previous
Two-Phase Multi-swarm Particle Swarm Optimization (2MPSO) algorithm.
Our method is based on two assumptions. First, that we know a bounding
rectangle of the area in which the requests might appear. Second, that the
initial requests' sizes and frequency of appearance are representative for the
yet unknown clients' requests. In order to solve the DVRP we divide the working
day into several time slices in which we solve a static problem. In our Monte
Carlo approach we randomly generate the unknown clients' requests with uniform
spatial distribution over the bounding rectangle and requests' sizes uniformly
sampled from the already known requests' sizes. The solution proposal is
constructed with the application of a clustering algorithm and a route
construction algorithm.
The MCTree method is tested on a well established set of benchmarks proposed
by Kilby et al. and is compared with the results achieved by applying our
previous 2MPSO algorithm and other literature results. The proposed MCTree
approach achieves a better time to quality trade-off then plain heuristic
algorithms. Moreover, a hybrid MCTree+PSO approach achieves better time to
quality trade-off then 2MPSO for small optimization time limits, making the
hybrid a good candidate for handling real world scale goods delivery problems.
- Abstract（参考訳）: 本研究では,DVRP(Dynamic Vehicle Routing Problem)を解く。
DVRPは、クライアントの要求(都市)番号と場所が作業日の始めに分かっていないかもしれない車両ルーティング問題の修正であり、また、すべての要求は、限られた能力の車両群によって1日の作業日に提供されなければならない。
本研究では,dvrpにおける到着要求の動的性質に直接アプローチするモンテカルロ法(mctree)を提案する。
また,従来の2相マルチスワーム粒子群最適化 (2MPSO) アルゴリズムを用いてMCTree+PSOをハイブリダイズした。
この方法は2つの仮定に基づいている。
まず、リクエストが現れる可能性のある領域の境界長方形が分かっていることです。
第二に、初期リクエストのサイズと出現頻度が未知のクライアントの要求に代表されるということです。
DVRPを解くために、作業日をいくつかの時間スライスに分割し、静的な問題を解決する。
モンテカルロのアプローチでは、未知のクライアントの要求をランダムに生成し、有界矩形上の均一な空間分布と、すでに知られている要求のサイズから一様にサンプリングした要求のサイズを推定する。
提案手法はクラスタリングアルゴリズムとルート構築アルゴリズムを適用して構築する。
mctree法はkilbyらによって提案されたベンチマークでテストされ、これまでの2mpsoアルゴリズムや他の文献結果を適用して得られた結果と比較される。
提案した MCTree アプローチは,高品質なトレードオフ,そして平易なヒューリスティックアルゴリズムを実現する。
さらに、MCTree+PSOのハイブリッド手法は、2MPSOを最小限の最適化時間で高品質なトレードオフを実現し、現実の商品の配送問題に対処するための良い候補となる。
関連論文リスト
- Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle
Routing Problem with Time Windows [58.891409372784516]
本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。
RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
論文 参考訳（メタデータ） (2023-06-04T09:18:02Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi
Dispatch [9.35511513240868]
H-TD2はモデルフリーで適応的な意思決定アルゴリズムであり、動的な都市環境下で多数の自動タクシーを協調する。
計算複雑性と個別のタクシー政策の限定された部分最適化とのトレードオフを明示的に制御するために、2つの行動の間のトリガ条件を記述・規定する。
最近の強化学習ディスパッチ法とは異なり、このポリシ推定はトレーニング外ドメインイベントに適応し、堅牢である。
論文 参考訳（メタデータ） (2021-05-05T15:42:31Z) - SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems [4.777801093677586]
我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。
RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。
この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
論文 参考訳（メタデータ） (2021-04-04T17:12:24Z) - A Generic Network Compression Framework for Sequential Recommender
Systems [71.81962915192022]
シークエンシャルレコメンデーションシステム(SRS)は,ユーザの動的関心を捉え,高品質なレコメンデーションを生成する上で重要な技術となっている。
CpRecと呼ばれる圧縮されたシーケンシャルレコメンデーションフレームワークを提案する。
大規模なアブレーション研究により、提案したCpRecは実世界のSRSデータセットにおいて最大4$sim$8倍の圧縮速度を達成できることを示した。
論文 参考訳（メタデータ） (2020-04-21T08:40:55Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳（メタデータ） (2020-04-16T16:20:53Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z) - Modeling and solving the multimodal car- and ride-sharing problem [0.0]
マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。
車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。
カラム生成に基づく2層分解アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-15T09:43:55Z) - Learning NP-Hard Multi-Agent Assignment Planning using GNN: Inference on
a Random Graph and Provable Auction-Fitted Q-learning [24.956507498394497]
本稿では,学習に基づくアルゴリズムを用いて,時間依存報酬を用いたマルチエージェント・マルチタスクNPハードプランニング問題をほぼ最適に解決する可能性について検討する。
論文 参考訳（メタデータ） (2019-05-29T04:02:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。