論文の概要: Competitive Ratios for Online Multi-capacity Ridesharing
- arxiv url: http://arxiv.org/abs/2009.07925v1
- Date: Wed, 16 Sep 2020 20:29:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-18 00:40:41.602123
- Title: Competitive Ratios for Online Multi-capacity Ridesharing
- Title（参考訳）: オンラインマルチキャパシティライドシェアリングにおける競合率
- Authors: Meghna Lowalekar, Pradeep Varakantham, Patrick Jaillet
- Abstract要約: マルチキャパシティのライドシェアリングでは、複数のリクエスト(例えば、顧客、食品、パーセル)が、異なる起源と宛先ペアが1つのリソースを旅する。
オンラインのマルチキャパシティーライドシェアリングは、基礎となるマッチンググラフが二部作にならないため、非常に難しい。
本稿では,オンラインマルチキャパシティ・ライドシェアリングの競争率に制約を課した最初のアプローチを提案する。
- 参考スコア（独自算出の注目度）: 30.964687022746226
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In multi-capacity ridesharing, multiple requests (e.g., customers, food
items, parcels) with different origin and destination pairs travel in one
resource. In recent years, online multi-capacity ridesharing services (i.e.,
where assignments are made online) like Uber-pool, foodpanda, and on-demand
shuttles have become hugely popular in transportation, food delivery, logistics
and other domains. This is because multi-capacity ridesharing services benefit
all parties involved { the customers (due to lower costs), the drivers (due to
higher revenues) and the matching platforms (due to higher revenues per
vehicle/resource). Most importantly these services can also help reduce carbon
emissions (due to fewer vehicles on roads).
Online multi-capacity ridesharing is extremely challenging as the underlying
matching graph is no longer bipartite (as in the unit-capacity case) but a
tripartite graph with resources (e.g., taxis, cars), requests and request
groups (combinations of requests that can travel together). The desired
matching between resources and request groups is constrained by the edges
between requests and request groups in this tripartite graph (i.e., a request
can be part of at most one request group in the final assignment). While there
have been myopic heuristic approaches employed for solving the online
multi-capacity ridesharing problem, they do not provide any guarantees on the
solution quality. To that end, this paper presents the first approach with
bounds on the competitive ratio for online multi-capacity ridesharing (when
resources rejoin the system at their initial location/depot after serving a
group of requests).
- Abstract（参考訳）: マルチキャパシティのライドシェアリングでは、複数のリクエスト(例えば、顧客、食品、パーセル)が、異なる起源と宛先ペアが1つのリソースを旅する。
近年、Uberプール、フードパンダ、オンデマンドシャトルなどのオンライン多人数配車サービス(オンライン配車サービス)は、輸送、フードデリバリー、物流、その他の領域で大きな人気を集めている。
これは、マルチキャパシティのライドシェアリングサービスが、顧客(低コスト)、ドライバー(より高い収入)、マッチングプラットフォーム(車両/リソース当たりの収入)を含むすべての当事者に利益をもたらすためである。
もっとも重要なのは、これらのサービスが二酸化炭素排出量の削減にも役立つことだ(道路を走る車両が少ないため)。
オンラインのマルチキャパシティライドシェアリングは、マッチンググラフが(ユニットキャパシティの場合のように)もはや二分ではなく、リソース(タクシー、車)、リクエスト、リクエストグループ(一緒に旅行できるリクエストの組み合わせ)を備えた三分グラフであるため、非常に難しい。
リソースとリクエストグループ間の望ましいマッチングは、この三部グラフ内のリクエストグループとリクエストグループの間のエッジによって制約される(すなわち、リクエストは最終割り当てで少なくとも1つのリクエストグループの一部になる)。
オンラインのマルチキャパシティ・ライドシェアリング問題を解決するために、妙にヒューリスティックなアプローチが採用されているが、ソリューションの品質に関する保証は提供していない。
そこで本稿では,オンライン・マルチキャパシティ・ライドシェアリングにおける競争比率(リソースが要求群にサービスを提供して最初のロケーション/デポットに再加入する場合)に関する最初のアプローチを提案する。
関連論文リスト
- Mutual Information as Intrinsic Reward of Reinforcement Learning Agents
for On-demand Ride Pooling [19.247162142334076]
オンデマンドの車両プールサービスにより、各車両は一度に複数の乗客にサービスを提供することができる。
既存のアルゴリズムでは、収益のみを考慮する場合が多いため、異常な配信要求を抱える場合、乗車が困難になる。
本稿では,都市を個別の配車に分割した配車作業のための配車フレームワークを提案し,これらの地域での配車に強化学習(RL)アルゴリズムを用いる。
論文 参考訳（メタデータ） (2023-12-23T08:34:52Z) - Fair collaborative vehicle routing: A deep multi-agent reinforcement
learning approach [49.00137468773683]
協力的な車両ルーティングは、キャリアがそれぞれの輸送要求を共有し、互いに代表して輸送要求を実行することで協力するときに発生する。
従来のゲーム理論解の概念は、特性関数がエージェントの数とともに指数関数的にスケールするので、計算に費用がかかる。
我々は,この問題を,深層マルチエージェント強化学習を用いて解決した連立交渉ゲームとしてモデル化することを提案する。
論文 参考訳（メタデータ） (2023-10-26T15:42:29Z) - Coalitional Bargaining via Reinforcement Learning: An Application to
Collaborative Vehicle Routing [49.00137468773683]
コラボレーティブ・ビークル・ルーティング(Collaborative Vehicle Routing)とは、デリバリ情報を共有し、互いに代理してデリバリ要求を実行することで、デリバリ企業が協力する場所である。
これによりスケールの経済が達成され、コスト、温室効果ガスの排出、道路渋滞が減少する。
しかし、どの会社が誰とパートナーし、それぞれの会社がどれだけの報酬を支払うべきか?
シャプリー値(英語版)やヌクレオルス(英語版)のような伝統的なゲーム理論解の概念は、協調車両ルーティング(英語版)の現実問題に対して計算することが困難である。
論文 参考訳（メタデータ） (2023-10-26T15:04:23Z) - Modeling routing problems in QUBO with application to ride-hailing [0.0]
このようなルーティング問題のひとつ,RPP(Ride Pooling Problem)に注力しています。
このタスクは、小規模な柔軟なバスルートに似た、限られた車両セットを使用して顧客の要求を最適にプールすることである。
論文 参考訳（メタデータ） (2022-12-09T14:55:34Z) - Efficiency, Fairness, and Stability in Non-Commercial Peer-to-Peer
Ridesharing [84.47891614815325]
本稿は、P2Pライドシェアリングにおける中核的な問題である、ライダーとドライバーのマッチングに焦点を当てる。
P2Pライドシェアリングにおける公平性と安定性の新たな概念を紹介する。
結果は、妥当な計算時間で、公平で安定した解が得られることを示唆している。
論文 参考訳（メタデータ） (2021-10-04T02:14:49Z) - Dynamic Bicycle Dispatching of Dockless Public Bicycle-sharing Systems
using Multi-objective Reinforcement Learning [79.61517670541863]
ドッキングレスPBS(DL-PBS)に欠かせない動的自転車レンタル需要に基づく効率的な自転車配車ソリューションを実現するためのAIの活用
DL-PBSに最適な自転車ディスパッチソリューションを提供するために、マルチオブジェクト強化学習(MORL-BD)に基づく動的自転車ディスパッチアルゴリズムを提案します。
論文 参考訳（メタデータ） (2021-01-19T03:09:51Z) - Joint predictions of multi-modal ride-hailing demands: a deep multi-task
multigraph learning-based approach [64.18639899347822]
本稿では、複数のマルチグラフ畳み込み(MGC)ネットワークを組み合わせて、異なるサービスモードの要求を予測する深層マルチタスクマルチグラフ学習手法を提案する。
提案手法は,様々な配車モードの予測精度において,ベンチマークアルゴリズムよりも優れていることを示す。
論文 参考訳（メタデータ） (2020-11-11T07:10:50Z) - Zone pAth Construction (ZAC) based Approaches for Effective Real-Time
Ridesharing [30.964687022746226]
リアルタイムのライドシェアリングシステムにおける重要な課題は、"右"の要求をグループ化して、"右"の利用可能な車両をリアルタイムで移動させることである。
我々は、ゾーンパスを利用するミオピック(現在の要求のみに焦点を当てたライドシェアリングの割り当て)と非ミオピック(将来の要求への影響を考慮したライドシェアリング)のアプローチにコントリビュートします。
論文 参考訳（メタデータ） (2020-09-13T17:57:15Z) - Balancing Taxi Distribution in A City-Scale Dynamic Ridesharing Service:
A Hybrid Solution Based on Demand Learning [0.0]
本研究では,動的なライドシェアリングサービスにおいて,都市間のタクシー配電のバランスをとる上での課題について検討する。
本稿では,Correlated Pooling が関連ライダーの要求を収集し,Adjacency Ride-Matching が要求学習に基づくタクシーをライダーに割り当て,Greedy Idle Movement が現在利用者が必要な地域への配車なしでタクシーを誘導することを目的としたハイブリッドソリューションを提案する。
論文 参考訳（メタデータ） (2020-07-27T07:08:02Z) - Modeling and solving the multimodal car- and ride-sharing problem [0.0]
マルチモーダルカー・ライドシェアリング問題(MMCRP)を紹介する。
車両のプールは一連の乗車要求をカバーするために使用され、発見されていない要求は他の交通手段に割り当てられる。
カラム生成に基づく2層分解アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-15T09:43:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。