Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources
Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1/2 - eps for any given eps greater than 0. We also show that no non-adaptive algorithm can achieve a ratio of 1/2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ride-sharing systems. We also present heuristics that perform well in practice.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Spatio-Temporal Hierarchical Adaptive Dispatching for Ridesharing Systems
Nowadays, ridesharing has become one of the most popular services offered by online ride-hailing platforms (e.g., Uber and Didi Chuxing). Existing ridesharing platforms adopt the strategy that dispatches orders over the …
A Unified Model for the Two-stage Offline-then-Online Resource Allocation
With the popularity of the Internet, traditional offline resource allocation has evolved into a new form, called online resource allocation. It features the online arrivals of agents in the system and the real-time decis…
Decision MakingCompetitive Ratios for Online Multi-capacity Ridesharing
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…
On the Real-time Vehicle Placement Problem
Motivated by ride-sharing platforms' efforts to reduce their riders' wait times for a vehicle, this paper introduces a novel problem of placing vehicles to fulfill real-time pickup requests in a spatially and temporally …
SchedulingAn Online Ride-Sharing Path Planning Strategy for Public Vehicle Systems
As efficient traffic-management platforms, public vehicle (PV) systems are envisioned to be a promising approach to solving traffic congestions and pollutions for future smart cities. PV systems provide online/dynamic pe…
ManagementScheduling