論文の概要: Offline Vehicle Routing Problem with Online Bookings: A Novel Problem
Formulation with Applications to Paratransit
- arxiv url: http://arxiv.org/abs/2204.11992v1
- Date: Mon, 25 Apr 2022 23:17:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-27 12:38:08.972096
- Title: Offline Vehicle Routing Problem with Online Bookings: A Novel Problem
Formulation with Applications to Paratransit
- Title（参考訳）: オンライン予約によるオフライン車両ルーティング問題:パラトランジットによる新しい問題定式化
- Authors: Amutheezan Sivagnanam, Salah Uddin Kadir, Ayan Mukhopadhyay, Philip
Pugliese, Abhishek Dubey, Samitha Samaranayake, Aron Laszka
- Abstract要約: オンライン予約によるオフライン車両ルーティング問題の新しい定式化について紹介する。
この問題は、大量の要求を考えるという複雑さに直面しているため、非常に困難である。
本稿では,任意の時間アルゴリズムとリアルタイム決定のための学習ベースのポリシーを組み合わせた新しい計算手法を提案する。
- 参考スコア（独自算出の注目度）: 5.8521525578624916
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Vehicle routing problems (VRPs) can be divided into two major categories:
offline VRPs, which consider a given set of trip requests to be served, and
online VRPs, which consider requests as they arrive in real-time. Based on
discussions with public transit agencies, we identify a real-world problem that
is not addressed by existing formulations: booking trips with flexible pickup
windows (e.g., 3 hours) in advance (e.g., the day before) and confirming tight
pickup windows (e.g., 30 minutes) at the time of booking. Such a service model
is often required in paratransit service settings, where passengers typically
book trips for the next day over the phone. To address this gap between offline
and online problems, we introduce a novel formulation, the offline vehicle
routing problem with online bookings. This problem is very challenging
computationally since it faces the complexity of considering large sets of
requests -- similar to offline VRPs -- but must abide by strict constraints on
running time -- similar to online VRPs. To solve this problem, we propose a
novel computational approach, which combines an anytime algorithm with a
learning-based policy for real-time decisions. Based on a paratransit dataset
obtained from our partner transit agency, we demonstrate that our novel
formulation and computational approach lead to significantly better outcomes in
this service setting than existing algorithms.
- Abstract（参考訳）: 車両ルーティング問題(vrps)は、所定のトリップリクエストのセットを提供するオフラインvrpと、リアルタイムにリクエストが到着することを考慮したオンラインvrpの2つのカテゴリに分けられる。
公共交通機関との議論に基づき、既存の定式化では解決されていない現実の問題として、事前(例えば、前日)に柔軟なピックアップウィンドウ(例えば、3時間)を予約し、予約時に厳密なピックアップウィンドウ(例えば、30分)を確認する。
このようなサービスモデルは、通常、乗客が電話で翌日の旅行を予約するパラトランジットサービス設定で必要とされることが多い。
オフラインとオンラインのこのギャップに対処するために,オンライン予約を伴うオフライン車両ルーティング問題として,新たな定式化を提案する。
この問題は、オフラインのvrpと同様に、大規模なリクエストセットを考える複雑さに直面しているが、オンラインのvrpと同様に、実行時間に関する厳格な制約に従わなければならないため、計算上非常に困難である。
この問題を解決するために,任意の時間アルゴリズムとリアルタイム決定のための学習ベースのポリシーを組み合わせた新しい計算手法を提案する。
パートナー輸送機関から得られたパラトランジットデータセットに基づいて、我々の新しい定式化と計算アプローチが、既存のアルゴリズムよりも、このサービス設定においてはるかに優れた結果をもたらすことを実証する。
関連論文リスト
- Solving the Team Orienteering Problem with Transformers [46.93254771681026]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
本稿では,チームオリエンテーリング問題を高速かつ高精度に解決できる多エージェント経路計画システムを提案する。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - Fair collaborative vehicle routing: A deep multi-agent reinforcement
learning approach [49.00137468773683]
協力的な車両ルーティングは、キャリアがそれぞれの輸送要求を共有し、互いに代表して輸送要求を実行することで協力するときに発生する。
従来のゲーム理論解の概念は、特性関数がエージェントの数とともに指数関数的にスケールするので、計算に費用がかかる。
我々は,この問題を,深層マルチエージェント強化学習を用いて解決した連立交渉ゲームとしてモデル化することを提案する。
論文 参考訳（メタデータ） (2023-10-26T15:42:29Z) - Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows [0.0]
我々は,VRPTWの解法であるHybrid Genetic Search (HGS) アルゴリズムを動的変種に適用する。
弊社のアプローチでは、これらのコンポーネントをDVRPTWに修正し、ソリューションの品質と今後の顧客の到着に対する制約のバランスを取ろうとしている。
論文 参考訳（メタデータ） (2023-07-21T11:16:49Z) - 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 deep learning Attention model to solve the Vehicle Routing Problem and
the Pick-up and Delivery Problem with Time Windows [0.0]
フランスの公共列車会社SNCFは、車両のルーティング問題に対処して、新しいタイプの交通サービスを開発する実験を行っている。
我々は,CPDPTWの実現可能性チェックのために,アテンション・デコーダ構造を用いて新しい挿入を設計する。
我々のモデルは、CVRPTWでよく知られた学習ソリューションよりも優れた結果をもたらす。
論文 参考訳（メタデータ） (2022-12-20T16:25:55Z) - 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) - A Case Study of Vehicle Route Optimization [2.2101681534594237]
本研究では,主に関連する実世界の制約と要件を取り入れる。
時間ウィンドウと停止時間のための2段階戦略とタイムラインアルゴリズムを提案する。
4つの最先端アルゴリズムに対する8つの異なる問題インスタンスの評価は、我々のアプローチが与えられた制約を妥当な時間で処理することを示している。
論文 参考訳（メタデータ） (2021-11-17T13:10:55Z) - Offline-to-Online Reinforcement Learning via Balanced Replay and
Pessimistic Q-Ensemble [135.6115462399788]
深いオフライン強化学習により、オフラインデータセットから強力なロボットエージェントをトレーニングすることが可能になった。
状態-作用分布シフトは、微調整中に厳しいブートストラップエラーを引き起こす可能性がある。
本稿では,オンライン上で遭遇したサンプルを優先しながら,ほぼ政治的なサンプルの使用を奨励するバランスの取れたリプレイ方式を提案する。
論文 参考訳（メタデータ） (2021-07-01T16:26:54Z) - Flatland Competition 2020: MAPF and MARL for Efficient Train
Coordination on a Grid World [49.80905654161763]
車両再スケジュール問題(vrsp)の解法開発を目的としたフラットランドコンペティション
VRSPは、交通ネットワークにおける旅行のスケジュールと、故障が発生した場合の車両の再スケジュールに関するものである。
現代の鉄道網の複雑化は、交通の動的リアルタイムスケジューリングを事実上不可能にします。
論文 参考訳（メタデータ） (2021-03-30T17:13:29Z) - Computation Offloading in Heterogeneous Vehicular Edge Networks: On-line
and Off-policy Bandit Solutions [30.606518785629046]
高速変動車体環境では、ネットワークの混雑によりオフロードの遅延が発生する。
本稿では,バンディット理論に基づくオンラインアルゴリズムと非政治学習アルゴリズムを提案する。
提案手法は,最も混雑の少ないネットワークを選択することで,ネットワークのトラフィック変化に適応することを示す。
論文 参考訳（メタデータ） (2020-08-14T11:48:13Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。