論文の概要: Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

• arxiv url: http://arxiv.org/abs/2603.07422v2
• Date: Tue, 10 Mar 2026 15:21:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-11 15:25:23.708587
• Title: Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests
• Title（参考訳）: プロンプト確認による車両の動的ルーティング問題
• Authors: Amutheezan Sivagnanam, Ayan Mukhopadhyay, Samitha Samaranayake, Abhishek Dubey, Aron Laszka,
• Abstract要約: オンデマンド交通サービスを運営する交通機関は、乗客の乗車要求にリアルタイムで応答する必要がある。 機関は、要求が受け入れられるかどうかを迅速に確認し、承認された要求が約束通り提供されることを保証する必要がある。 本稿では,迅速な確認と連続的な最適化を備えた動的車両ルーティングの新たな問題定式化を提案する。
• 参考スコア（独自算出の注目度）: 14.333071743393786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transit agencies that operate on-demand transportation services have to respond to trip requests from passengers in real time, which involves solving dynamic vehicle routing problems with pick-up and drop-off constraints. Based on discussions with public transit agencies, we observe a real-world problem that is not addressed by prior work: when trips are booked in advance (e.g., trip requests arrive a few hours in advance of their requested pick-up times), the agency needs to promptly confirm whether a request can be accepted or not, and ensure that accepted requests are served as promised. State-of-the-art computational approaches either provide prompt confirmation but lack the ability to continually optimize and improve routes for accepted requests, or they provide continual optimization but cannot guarantee serving all accepted requests. To address this gap, we introduce a novel problem formulation of dynamic vehicle routing with prompt confirmation and continual optimization. We propose a novel computational approach for this vehicle routing problem, which integrates a quick insertion search for prompt confirmation with an anytime algorithm for continual optimization. To maximize the number requests served, we train a non-myopic objective function using reinforcement learning, which guides both the insertion and the anytime algorithms towards optimal, non-myopic solutions. We evaluate our computational approach on a real-world microtransit dataset from a public transit agency in the U.S., demonstrating that our proposed approach provides prompt confirmation while significantly increasing the number of requests served compared to existing approaches.
• Abstract（参考訳）: オンデマンド交通サービスを運営する交通機関は、乗客の乗車要求にリアルタイムで応答する必要がある。 公共交通機関との議論に基づき、事前に予約された場合(例えば、所望の乗車時間に先立って数時間前に旅行依頼が到着するなど)は、依頼が受理可能か否かを迅速に確認し、受理された要求が約束通りに提供されることを保証しなくてはならない。 最先端の計算手法は、迅速な確認を提供するが、受理された要求に対する経路を継続的に最適化し改善する能力がないか、連続的な最適化を提供するが、受理された全ての要求を保証できない。 このギャップに対処するために、高速な確認と連続的な最適化を伴う動的車両ルーティングの新たな問題定式化を導入する。 本稿では,車載経路問題に対する新しい計算手法を提案する。これは,迅速な挿入探索と即時確認と,連続的な最適化のための任意のアルゴリズムを統合するものである。 提案手法は, 挿入アルゴリズムと任意のアルゴリズムの両方を, 最適で非明視的解へと誘導する強化学習を用いて, 非明視的目的関数を訓練する。 米国における公共交通機関による実世界のマイクロトランジットデータセットに対する計算手法の評価を行い,提案手法が提案手法を即時確認し,既存手法と比較して要求数を大幅に増加させることを示した。

関連論文リスト

• FastLane: Efficient Routed Systems for Late-Interaction Retrieval [58.060096779432094]
  FastLaneは、クエリを最も情報的な表現に動的にルーティングする新しい検索フレームワークである。 Approximate Nearest Neighbor Search (ANNS)で遅延処理モデルをブリッジすることで、FastLaneはスケーラブルで低レイテンシな検索を可能にする。
  論文  参考訳（メタデータ） (2026-01-10T02:22:01Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。 本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。 このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
  論文  参考訳（メタデータ） (2025-04-08T15:21:01Z)
• Safe Model-Based Multi-Agent Mean-Field Reinforcement Learning [48.667697255912614]
  平均場強化学習は、同一エージェントの無限集団と相互作用する代表エージェントのポリシーに対処する。 モデルベースの平均場強化学習アルゴリズムであるSafe-M$3$-UCRLを提案する。 本アルゴリズムは,低需要領域におけるサービスアクセシビリティを確保しつつ,重要な領域における需要を効果的に満たす。
  論文  参考訳（メタデータ） (2023-06-29T15:57:07Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• Offline Vehicle Routing Problem with Online Bookings: A Novel Problem Formulation with Applications to Paratransit [5.8521525578624916]
  オンライン予約によるオフライン車両ルーティング問題の新しい定式化について紹介する。 この問題は、大量の要求を考えるという複雑さに直面しているため、非常に困難である。 本稿では,任意の時間アルゴリズムとリアルタイム決定のための学習ベースのポリシーを組み合わせた新しい計算手法を提案する。
  論文  参考訳（メタデータ） (2022-04-25T23:17:34Z)
• An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services [5.649212162857776]
  動的車両ルーティング問題(DVRP)を解決するための完全オンライン手法を提案する。 時間的に疎いため、パラトランジットリクエストのバッチ化は困難である。 我々はモンテカルロ木探索を用いて任意の状態に対する行動を評価する。
  論文  参考訳（メタデータ） (2022-03-28T22:15:52Z)
• dFDA-VeD: A Dynamic Future Demand Aware Vehicle Dispatching System [21.17974307683502]
  本稿では,動的な将来需要対応型配車システムを提案する。 移動需要と交通条件の両方を考慮して、移転センターを探索することができる。 提案システムでは,サービス提供率を大幅に向上し,運用コストが極めて少ないことが実証された。
  論文  参考訳（メタデータ） (2021-06-10T13:40:17Z)
• Equilibrium Inverse Reinforcement Learning for Ride-hailing Vehicle Network [1.599072005190786]
  疎結合グラフにおける客車マッチングの問題を定式化する。 マルチエージェント環境における平衡ポリシを導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-13T03:18:44Z)
• Zone pAth Construction (ZAC) based Approaches for Effective Real-Time Ridesharing [30.964687022746226]
  リアルタイムのライドシェアリングシステムにおける重要な課題は、"右"の要求をグループ化して、"右"の利用可能な車両をリアルタイムで移動させることである。 我々は、ゾーンパスを利用するミオピック(現在の要求のみに焦点を当てたライドシェアリングの割り当て)と非ミオピック(将来の要求への影響を考慮したライドシェアリング)のアプローチにコントリビュートします。
  論文  参考訳（メタデータ） (2020-09-13T17:57:15Z)

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

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