Dispatching Through Pricing: Modeling Ride-Sharing and Designing Dynamic Prices

Mengjing Chen, Weiran Shen, Pingzhong Tang, Song ZuoIJCAI 2019 · OpenReview

Abstract

Over the past few years, ride-sharing has emerged as an effective way to relieve traffic congestion. A key problem for the ride-sharing platforms is to come up with a revenue-optimal (or GMV-optimal) pricing scheme and a vehicle dispatching policy that incorporate geographic and temporal information. In this paper, we aim to tackle this problem via an economic approach. Modeled naively, the underlying optimization problem may be non-convex and thus hard to solve. To this end, we use a so-called "ironing" technique to convert the problem into an equivalent convex optimization one via a clean Markov decision process (MDP) formulation, where the states are the driver distributions and the decision variables are the prices for each pair of locations. Our main finding is an efficient algorithm that computes the exact revenue-optimal (or GMV-optimal) randomized pricing scheme, which naturally induces the accompany vehicle dispatching policy. We also conduct empirical evaluations of our solution through real data of a major ride-sharing platform and show its advantages over fixed pricing schemes as well as several prevalent surge-based pricing schemes.

Introduction: The Balancing Act of Ride-Sharing

Ride-sharing platforms face a constant challenge in balancing supply and demand. Ideally, drivers should be positioned exactly where passengers need them. However, in practice, geographic and temporal imbalances often lead to the "wild goose chase" phenomenon, where drivers must travel long distances for pickups, reducing overall efficiency and platform revenue.

While "surge pricing" is the industry standard for managing these imbalances, it does not inherently guarantee efficient vehicle dispatching. Conversely, traditional dispatching algorithms often overlook the economic impact of pricing on passenger and driver behavior. This paper introduces a unified pricing and dispatching scheme designed for complex, time-varying urban environments.

Methodology: A Unified Framework

The proposed model represents a city as a directed graph, where nodes signify regions and edges represent potential trips. To optimize this system, the authors utilize several key mathematical strategies:

  1. MDP Formulation: The system is modeled as a Markov Decision Process (MDP) where the state is the driver distribution and actions are the prices set for each route.
  2. Temporal Normalization: To handle varying trip durations, "virtual nodes" are added to the graph, segmenting long trips into discrete one-timestep intervals. This ensures all drivers are available for new decisions at every timestep.
  3. The "Ironing" Technique: Revenue functions in ride-sharing models are typically non-convex, making them difficult to optimize. The authors apply an economic "ironing" technique to transform the non-convex objective into a concave one. This allows for the use of randomized pricing to achieve optimal driver flow, converting a complex optimization problem into a solvable convex program.
The ironing technique transforms a non-convex objective function into a concave one, enabling efficient optimization.

Experimental Setup: Real-World Data from Didi Chuxing

The model was evaluated using a large-scale dataset from Didi Chuxing, covering three weeks of activity in a major Chinese city (January 1st – 21st, 2016). The dataset includes over 8.5 million individual orders, providing detailed records of origin/destination pairs, timestamps, and estimated prices. Demand curves were fitted to lognormal distributions, and travel times were inferred using linear regression.

Key Insights: Pricing as a Dispatching Mechanism

A central finding of this research is that pricing and dispatching are not separate problems. Setting appropriate prices for specific routes naturally "pulls" drivers toward high-demand areas. Furthermore, the "ironing" technique suggests that randomized pricing—offering different prices for the same route—can be an effective tool for maintaining optimal driver flow. Unlike traditional surge pricing, which focuses on local imbalances, this model considers the global state of the city to ensure long-term system stability.

Performance Evaluation

The proposed policy, DYNAM, was compared against two benchmarks: FIXED (constant per-minute pricing) and SURGE (demand-based multipliers).

  • Revenue Gains: In static environments, DYNAM outperformed FIXED by 24% and SURGE by 17%. During peak demand periods (e.g., 8:00 AM), DYNAM generated approximately 33% more revenue than SURGE and 60% more than FIXED.
  • Supply-Demand Stability: DYNAM maintained a supply ratio (available drivers to demand) near 1.0 across all regions. In contrast, FIXED and SURGE policies often resulted in significant over-supply or severe shortages, leading to a "death spiral" of declining revenue as the system became more unbalanced.
Comparison of revenue per minute for DYNAM, FIXED, and SURGE policies in both static and dynamic environments.

Discussion and Future Directions

While the model provides a robust framework for dynamic pricing, it assumes drivers are "non-strategic" and will accept any platform assignment. In reality, independent contractors may reject low-value trips. Additionally, the model's performance relies on accurate demand estimation. Future research could explore models that account for strategic driver behavior and incorporate broader welfare metrics alongside platform revenue.

Summary updated

Abstract

Over the past few years, ride-sharing has emerged as an effective way to relieve traffic congestion. A key problem for the ride-sharing platforms is to come up with a revenue-optimal (or GMV-optimal) pricing scheme and a vehicle dispatching policy that incorporate geographic and temporal information. In this paper, we aim to tackle this problem via an economic approach. Modeled naively, the underlying optimization problem may be non-convex and thus hard to solve. To this end, we use a so-called ``ironing'' technique to convert the problem into an equivalent convex optimization one via a clean Markov decision process (MDP) formulation, where the states are the driver distributions and the decision variables are the prices for each pair of locations. Our main finding is an efficient algorithm that computes the exact revenue-optimal (or GMV-optimal) randomized pricing scheme, which naturally induces the accompany vehicle dispatching policy. We also conduct empirical evaluations of our solution through real data of a major ride-sharing platform and show its advantages over fixed pricing schemes as well as several prevalent surge-based pricing schemes.
BibTeX
@inproceedings{chen2019dispatching,
  author = {Mengjing Chen and Weiran Shen and Pingzhong Tang and Song Zuo},
  title = {{Dispatching Through Pricing: Modeling Ride-Sharing and Designing Dynamic Prices}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=KzuSsioz592},
}
Figure