An Optimization Framework for Online Ride-Sharing Markets

Yongzheng Jia, Wei Xu, Xue Liu

TL;DR

This paper introduces a generalized optimization framework for two-sided ride-sharing markets (like Uber or Waze Rider) that balances the needs of both drivers and passengers. The authors develop a greedy offline algorithm with a provably tight approximation bound and propose two practical online heuristics that significantly improve market efficiency using real-world taxi trajectory data.

What Problem Does This Paper Address?

Efficiently matching supply (drivers) and demand (riders) in a city is a massive computational challenge. While traditional "Vehicle Routing Problems" (VRP) often focus on one-sided optimization (e.g., a delivery company optimizing its own fleet), modern ride-sharing platforms operate in two-sided markets. In these markets, both groups are independent actors with their own constraints: drivers have specific working hours and locations, while riders have specific pickup/drop-off windows and a "willingness to pay."

The core challenge is scaling: in cities like New York or Beijing, platforms must manage millions of requests and tens of thousands of drivers simultaneously. Existing models are often too detailed to scale or too simplified to capture the dynamic nature of surge pricing and driver availability.

Methods

The authors model the ride-sharing market as a Multiple Disjoint Paths (MDP) problem on a Directed Acyclic Graph (DAG).

  1. Task Map Construction: For every driver, they build a "task map" where nodes represent potential ride requests and edges represent feasible transitions (i.e., can the driver finish Task A and reach the start of Task B in time?). An example of a driver's task map showing feasible sequences of rides
  2. Optimization Objectives: They formulate two primary goals:
  3. Driver Profit Maximization: Maximizing the total revenue minus the "excess cost" (extra mileage driven to reach passengers).
  4. Social Welfare Maximization: Maximizing the sum of driver profits and "consumer surplus" (the value riders get above what they paid).
  5. Algorithms:
    • Greedy Algorithm (GA): An offline approach that iteratively picks the highest-profit path for any driver and removes those tasks from the pool. They prove this has an approximation ratio of $1/(D+1)$, where $D$ is the maximum number of tasks a single driver can perform.
  6. Online Heuristics: Since real-world platforms don't know future requests, they propose two online versions:
  7. Nearest Driver: Assigns a task to the driver who can reach the source fastest.
  8. Maximum Marginal Value (maxMargin): Assigns a task to the driver who gains the most additional profit from taking it.
An example of a driver's task map showing feasible sequences of rides

Datasets

The researchers evaluated their framework using a massive real-world dataset from ECML/PKDD 15, which contains a full year of trajectories for 442 taxis in Porto, Portugal. This includes over one million trip records with precise timestamps and GPS polylines. They used Monte Carlo methods to simulate driver home/work locations based on this historical data.

Key Insights and Ideas

  • The "Hitchhiking" Advantage: The paper compares a "home-work-home" model (full-time Uber-style driving) with a "hitchhiking" model (part-time Waze Rider-style, where drivers are already going somewhere). They found that the hitchhiking model is actually more economically efficient because it's easier to match riders with drivers who are already headed in the same direction.
  • The Power of $D$: The performance of the greedy algorithm is directly tied to $D$ (the diameter of the task graph). In ride-sharing, $D$ is usually small (a driver might only do 4-10 trips in a shift), which makes the greedy approach surprisingly effective compared to more complex theoretical bounds.
  • Market Density vs. Congestion: As more drivers enter the market, the "service rate" (percentage of orders fulfilled) increases, but the average payoff per driver decreases due to competition. An effective market designer must balance these to keep both sides of the market satisfied.

Key Results

  • Algorithm Performance: In simulations with 1,000 records, the offline Greedy Algorithm consistently provided the best results. For online scenarios, the maxMargin heuristic outperformed the Nearest driver approach, suggesting that looking at profit margins is a better dispatch strategy than simply looking at proximity.
  • Tight Bounds: The authors demonstrated that their $1/(D+1)$ bound is "tight," meaning they constructed a worst-case scenario where the algorithm performs exactly that well and no better. A theoretical graph used to prove the tight approximation bound of the greedy algorithm
  • Scalability: By partitioning the problem by city and using the DAG structure, the framework handles the high-dimensional data of modern urban transport efficiently.
A theoretical graph used to prove the tight approximation bound of the greedy algorithm

Limitations and Future Work

  • Heuristic Reliance: While the offline algorithm has a theoretical bound, the online algorithms are purely heuristic. The authors suggest that developing non-heuristic online algorithms with provable performance ratios is a key next step.
  • Simplified Pricing: The study uses a simplified surge pricing model. Future work could integrate more complex, real-time game-theoretic pricing strategies.
  • Broader Markets: The authors hope to apply this framework to other two-sided "gig economy" markets beyond just ride-sharing and product delivery.

Summary updated

Abstract

Taxi services and product delivery services are instrumental for our modern society. Thanks to the emergence of sharing economy, ride-sharing services such as Uber, Didi, Lyft and Google's Waze Rider are becoming more ubiquitous and grow into an integral part of our everyday lives. However, the efficiency of these services are severely limited by the sub-optimal and imbalanced matching between the supply and demand. We need a generalized framework and corresponding efficient algorithms to address the efficient matching, and hence optimize the performance of these markets. Existing studies for taxi and delivery services are only applicable in scenarios of the one-sided market. In contrast, this work investigates a highly generalized model for the taxi and delivery services in the market economy (abbreviated as"taxi and delivery market") that can be widely used in two-sided markets. Further, we present efficient online and offline algorithms for different applications. We verify our algorithm with theoretical analysis and trace-driven simulations under realistic settings.
BibTeX
@inproceedings{jia2017optimization,
  author = {Yongzheng Jia and Wei Xu and Xue Liu},
  title = {{An Optimization Framework for Online Ride-Sharing Markets}},
  booktitle = {ICDCS},
  year = {2017},
  url = {https://openreview.net/forum?id=Wg8Q_Yr9Pwk},
}

Loading related content...

Figure