An official website of the United States government
Two-Stage Matching and Pricing in Ride-Hailing Platforms Matching and pricing are two critical levers in two-sided marketplaces to connect demand and supply. The platform can produce more efficient matching and pricing decisions by batching the demand requests. We initiate the study of the two-stage stochastic matching problem with or without pricing to enable the platform to make improved decisions in a batch with an eye toward the imminent future demand requests. This problem is motivated in part by applications in online marketplaces, such as ride-hailing platforms. We design online competitive algorithms for vertex-weighted (or unweighted) two-stage stochastic matching for maximizing supply efficiency and two-stage joint matching and pricing for maximizing market efficiency. Using various techniques, such as introducing convex programming–based matching and graph decompositions, submodular maximization, and factor-revealing linear programs, we obtain either optimal competitive or improved approximation algorithms compared with naïve solutions. We enrich our theoretical study by data-driven numerical simulations using DiDi’s ride-sharing data sets.
more »
« less
Real-Time Pricing Optimization for Ride-Hailing Quality of Service
When demand increases beyond the system capacity, riders in ride-hailing/ride-sharing systems often experience long waiting time, resulting in poor customer satisfaction. This paper proposes a spatio-temporal pricing framework (AP-RTRS) to alleviate this challenge and shows how it naturally complements state-of-the-art dispatching and routing algorithms. Specifically, the pricing optimization model regulates demand to ensure that every rider opting to use the system is served within reason-able time: it does so either by reducing demand to meet the capacity constraints or by prompting potential riders to postpone service to a later time. The pricing model is a model-predictive control algorithm that works at a coarser temporal and spatial granularity compared to the real-time dispatching and routing, and naturally integrates vehicle relocations. Simulation experiments indicate that the pricing optimization model achieves short waiting times without sacrificing revenues and geographical fairness.
more »
« less
- Award ID(s):
- 1854684
- PAR ID:
- 10328527
- Date Published:
- Journal Name:
- 30th International Joint Conference on Artificial Intelligence (IJCAI-21
- Page Range / eLocation ID:
- 3742 to 3748
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Ride-hailing marketplaces like Uber and Lyft use dynamic pricing, often called surge, to balance the supply of available drivers with the demand for rides. We study driver-side payment mechanisms for such marketplaces, presenting the theoretical foundation that has informed the design of Uber’s new additive driver surge mechanism. We present a dynamic stochastic model to capture the impact of surge pricing on driver earnings and their strategies to maximize such earnings. In this setting, some time periods (surge) are more valuable than others (nonsurge), and therefore trips of different time lengths vary in the induced driver opportunity cost. First, we show that multiplicative surge, historically the standard on ride-hailing platforms, is not incentive compatible in a dynamic setting. We then propose a structured, incentive-compatible pricing mechanism. This closed-form mechanism has a simple form and is well approximated by Uber’s new additive surge mechanism. Finally, through both numerical analysis and real data from a ride-hailing marketplace, we show that additive surge is more incentive compatible in practice than is multiplicative surge. This paper was accepted by David Simchi-Levi, revenue management and market analytics.more » « less
-
Problem definition: Inspired by new developments in dynamic spectrum access, we study the dynamic pricing of wireless Internet access when demand and capacity (bandwidth) are stochastic. Academic/practical relevance: The demand for wireless Internet access has increased enormously. However, the spectrum available to wireless service providers is limited. The industry has, thus, altered conventional license-based spectrum access policies through unlicensed spectrum operations. The additional spectrum obtained through these operations has stochastic capacity. Thus, the pricing of this service by the service provider has novel challenges. The problem considered in this paper is, therefore, of high practical relevance and new to the academic literature. Methodology: We study this pricing problem using a Markov decision process model in which customers are posted dynamic prices based on their bandwidth requirement and the available capacity. Results: We characterize the structure of the optimal pricing policy as a function of the system state and of the input parameters. Because it is impossible to solve this problem for practically large state spaces, we propose a heuristic dynamic pricing policy that performs very well, particularly when the ratio of capacity to demand rate is low. Managerial implications: We demonstrate the value of using a dynamic heuristic pricing policy compared with the myopic and optimal static policies. The previous literature has studied similar systems with fixed capacity and has characterized conditions under which myopic policies perform well. In contrast, our setting has dynamic (stochastic) capacity, and we find that identifying good state-dependent heuristic pricing policies is of greater importance. Our heuristic policy is computationally more tractable and easier to implement than the optimal dynamic and static pricing policies. It also provides a significant performance improvement relative to the myopic and optimal static policies when capacity is scarce, a condition that holds for the practical setting that motivated this research.more » « less
-
The increasing rate of urbanization has added pressure on the already constrained transportation networks in our communities. Ride-sharing platforms such as Uber and Lyft are becoming a more commonplace, particularly in urban environments. While such services may be deemed more convenient than riding public transit due to their on-demand nature, reports show that they do not necessarily decrease the congestion in major cities. One of the key problems is that typically mobility decision support systems focus on individual utility and react only after congestion appears. In this paper, we propose socially considerate multi-modal routing algorithms that are proactive and consider, via predictions, the shared effect of riders on the overall efficacy of mobility services. We have adapted the MATSim simulator framework to incorporate the proposed algorithms present a simulation analysis of a case study in Nashville, Tennessee that assesses the effects of our routing models on the traffic congestion for different levels of penetration and adoption of socially considerate routes. Our results indicate that even at a low penetration (social ratio), we are able to achieve an improvement in system-level performance.more » « less
-
As Autonomous Vehicles (AVs) become possible for E-hailing services operate, especially when telecom companies start deploying next-generation wireless networks (known as 5G), many new technologies may be applied in these vehicles. Dynamic-route-switching is one of these technologies, which could help vehicles find the best possible route based on real-time traffic information. However, allowing all AVs to choose their own optimal routes is not the best solution for a complex city network, since each vehicle ignores its negative effect on the road system due to the additional congestion it creates. As a result, with this system, some of the links may become over-congested, causing the whole road network system performance to degrade. Meanwhile, the travel time reliability, especially during the peak hours, is an essential factor to improve the customers' ride experience. Unfortunately, these two issues have received relatively less attention. In this paper, we design a link-based dynamic pricing model to improve the road network system and travel time reliability at the same time. In this approach, we assume that all links are eligible with the dynamic pricing, and AVs will be perfect informed with update traffic condition and follow the dynamic road pricing. A heuristic approach is developed to address this computationally difficult problem. The output includes link-based surcharge, new travel demand and traffic condition which would improve the system performance close to the System Optimal (SO) solution and maintain the travel time reliability. Finally, we evaluate the effectiveness and efficiency of the proposed model to the well-known test Sioux Falls network.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.24963/ijcai.2021/515
