論文の概要: An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services

• arxiv url: http://arxiv.org/abs/2203.15127v1
• Date: Mon, 28 Mar 2022 22:15:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-30 16:46:46.935419
• Title: An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services
• Title（参考訳）: トランジットサービスのための確率的トリップ要求を用いた動的車両ルーティング問題のオンライン解法
• Authors: Michael Wilbur, Salah Uddin Kadir, Youngseo Kim, Geoffrey Pettet, Ayan Mukhopadhyay, Philip Pugliese, Samitha Samaranayake, Aron Laszka and Abhishek Dubey
• Abstract要約: 動的車両ルーティング問題(DVRP)を解決するための完全オンライン手法を提案する。 時間的に疎いため、パラトランジットリクエストのバッチ化は困難である。 我々はモンテカルロ木探索を用いて任意の状態に対する行動を評価する。
• 参考スコア（独自算出の注目度）: 5.649212162857776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions), causing estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse - our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.
• Abstract（参考訳）: パラトランジットとマイクロトランジットを運用する多くの交通機関は、不確実性の下での厳密な組合せとシーケンシャルな意思決定問題を解決することを必要とする、リアルタイムで到着する旅行要求に応答する必要がある。 長期的には著しく非効率となる決定を避けるため、非筋電ユーティリティ機能を最適化したり、リクエストをまとめて筋電ユーティリティ機能を最適化したりすることで、車両を要求に割り当てるべきである。 前者のアプローチは通常オフラインだが、後者はオンラインで実行できる。 このようなアプローチをパラトランジットサービスに適用する場合の2つの大きな問題を指摘した。 まず、時間的に疎いため、パラトランジットリクエストのバッチ化が困難である。 第二に、交通機関が活動する環境(例えば交通条件)が動的に変化し、オフラインで学習された推定が停滞する。 これらの課題に対処するため,建設に伴う環境動態の変化に頑健な時間窓や確率的移動要求を伴う動的車両ルーティング問題(DVRP)を解決するための完全オンラインアプローチを提案する。 私たちの問題は、パラトランジットサービスのアプリケーションによって動機付けられています。 我々はDVRPをマルコフ決定過程として定式化し、モンテカルロ木探索を用いて任意の状態に対する行動を評価する。 非ミオピック効用関数を最適化しながら確率的要求を計算することは計算的に難しい;実際、そのような問題に対する作用空間は、実際、難解に大きい。 大きなアクション空間に取り組むために、我々は、木探索に有望なアクションをサンプリングできるヒューリスティックを設計するために、問題の構造を利用する。 実世界の実世界データを用いた実験の結果,提案手法は性能とロバスト性の両方において,既存の最先端手法よりも優れていることがわかった。

関連論文リスト

• A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
  タスク・アンド・モーション・プランニング(タスク・アンド・モーション・プランニング、TAMP)は、自動化された計画問題の解決策を見つけるための問題である。 本稿では,TAMP問題のモデル化とベンチマークを行うための,汎用的でオープンソースのフレームワークを提案する。 移動エージェントと複数のタスク状態依存障害を含むTAMP問題を解決する革新的なメタ技術を導入する。
  論文  参考訳（メタデータ） (2024-08-11T14:57:57Z)
• A Reinforcement Learning Approach for Dynamic Rebalancing in Bike-Sharing System [11.237099288412558]
  自転車シェアリングシステムはエコフレンドリーな都市移動を提供し、交通渋滞と健康的な生活様式の緩和に貢献している。 駅間で自転車を再分配するための車両を用いた効果的な再バランス戦略の開発は、オペレーターにとって非常に重要である。 本稿では,複数の車両との動的再バランス問題に対する時間的強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-05T23:46:42Z)
• Multi-Agent Deep Reinforcement Learning for Dynamic Avatar Migration in AIoT-enabled Vehicular Metaverses with Trajectory Prediction [70.9337170201739]
  本稿では,その歴史データに基づいて,知的車両の将来の軌跡を予測するモデルを提案する。 提案アルゴリズムは,予測なしでアバタータスクの実行遅延を約25%削減できることを示す。
  論文  参考訳（メタデータ） (2023-06-26T13:27:11Z)
• Combinatorial Optimization enriched Machine Learning to solve the Dynamic Vehicle Routing Problem with Time Windows [5.4807970361321585]
  最適化層を組み込んだ新しい機械学習パイプラインを提案する。 最近,EURO Meets NeurIPS Competition at NeurIPS 2022において,このパイプラインを波による動的車両ルーティング問題に適用した。 提案手法は,提案した動的車両経路問題の解法において,他の全ての手法よりも優れていた。
  論文  参考訳（メタデータ） (2023-04-03T08:23:09Z)
• Preference-Aware Delivery Planning for Last-Mile Logistics [3.04585143845864]
  最適化手法と機械学習手法の両方の長所を組み合わせた,学習可能なパラメータを持つ新しい階層的経路を提案する。 Amazon Last Mile Research Challengeが提供する実際のデリバリデータセットを使用することで、最適化と機械学習コンポーネントの両方を持つことの重要性を実証する。
  論文  参考訳（メタデータ） (2023-03-08T02:10:59Z)
• Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit [5.8521525578624916]
  オンライン予約によるオフライン車両ルーティング問題の新しい定式化について紹介する。 この問題は、大量の要求を考えるという複雑さに直面しているため、非常に困難である。 本稿では,任意の時間アルゴリズムとリアルタイム決定のための学習ベースのポリシーを組み合わせた新しい計算手法を提案する。
  論文  参考訳（メタデータ） (2022-04-25T23:17:34Z)
• Value Function is All You Need: A Unified Learning Framework for Ride Hailing Platforms [57.21078336887961]
  DiDi、Uber、Lyftなどの大型配車プラットフォームは、都市内の数万台の車両を1日中数百万の乗車要求に接続している。 両課題に対処するための統合価値に基づく動的学習フレームワーク(V1D3)を提案する。
  論文  参考訳（メタデータ） (2021-05-18T19:22:24Z)
• Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work! [0.0]
  リアルタイム、インスタントモビリティ、デリバリーサービスの需要が増加している。 動的車両ルーティング問題(SDVRP)には、予測リアルタイムルーティングアクションが必要です。 sdvrpsの解決には,両コミュニティの共同作業が必要である。
  論文  参考訳（メタデータ） (2021-02-28T13:26:35Z)
• Multi-intersection Traffic Optimisation: A Benchmark Dataset and a Strong Baseline [85.9210953301628]
  交通信号の制御は、都市部の交通渋滞の緩和に必要不可欠である。 問題モデリングの複雑さが高いため、現在の作業の実験的な設定はしばしば矛盾する。 エンコーダ・デコーダ構造を用いた深層強化学習に基づく新規で強力なベースラインモデルを提案する。
  論文  参考訳（メタデータ） (2021-01-24T03:55:39Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  複数の自動誘導車両 (AGV) が共通作業空間をナビゲートし, 様々な作業を行う。 一つのアプローチは、Action Dependency Graph (ADG)を構築し、そのルートに沿って進むとAGVの順序を符号化する。 ワークスペースが人間やサードパーティロボットのような動的障害によって共有されている場合、AGVは大きな遅延を経験することができる。 本稿では,各AGVの経路完了時間を最小限に抑えるために,非循環ADGを繰り返し修正するオンライン手法を提案する。
  論文  参考訳（メタデータ） (2020-10-11T14:39:50Z)
• Multi-Agent Routing Value Iteration Network [88.38796921838203]
  疎結合グラフの学習値に基づいてマルチエージェントルーティングを行うことができるグラフニューラルネットワークに基づくモデルを提案する。 最大25ノードのグラフ上で2つのエージェントでトレーニングしたモデルでは,より多くのエージェントやノードを持つ状況に容易に一般化できることが示されている。
  論文  参考訳（メタデータ） (2020-07-09T22:16:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。