An Optimization Framework For Online Ride-sharing Markets

Yongzheng Jia, Wei Xu, Xue Liu

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.

Introduction

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—such as 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.

Methodology

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, a "task map" is constructed where nodes represent potential ride requests and edges represent feasible transitions. A transition is feasible if the driver can finish Task A and reach the start of Task B within the required time window.

An example of a driver's task map showing feasible sequences of rides

2. Optimization Objectives

The framework formulates two primary goals:

  • Driver Profit Maximization: Maximizing total revenue minus the "excess cost" (extra mileage driven to reach passengers).
  • Social Welfare Maximization: Maximizing the sum of driver profits and "consumer surplus" (the value riders get above what they paid).

3. Algorithms

  • Greedy Algorithm (GA): An offline approach that iteratively selects the highest-profit path for any driver and removes those tasks from the pool. The authors prove this has an approximation ratio of $1/(D+1)$, where $D$ is the maximum number of tasks a single driver can perform.
  • Online Heuristics: Since real-world platforms lack knowledge of future requests, two online versions are proposed:
  • Nearest Driver: Assigns a task to the driver who can reach the source fastest.
  • Maximum Marginal Value (maxMargin): Assigns a task to the driver who gains the most additional profit from taking it.

Experimental Setup

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

Key Insights

  • The "Hitchhiking" Advantage: The paper compares a "home-work-home" model (full-time driving) with a "hitchhiking" model (part-time, where drivers are already commuting). The hitchhiking model is more economically efficient because it matches riders with drivers already headed in the same direction, reducing "deadhead" miles.
  • 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 (4-10 trips per shift), making 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. Effective market design must balance these factors to maintain satisfaction on both sides.

Key Results

The offline Greedy Algorithm consistently provided the best results in simulations. For online scenarios, the maxMargin heuristic outperformed the Nearest Driver approach, suggesting that profit margin is a superior dispatch metric compared to simple proximity.

The authors also demonstrated that their $1/(D+1)$ bound is "tight." They constructed a worst-case scenario where the algorithm performs exactly at this bound, confirming the theoretical limits of the greedy approach.

A theoretical graph used to prove the tight approximation bound of the greedy algorithm

Conclusion and Future Work

While the offline algorithm has a theoretical bound, the online algorithms remain heuristic. Developing non-heuristic online algorithms with provable performance ratios is a critical next step. Additionally, while this study uses a simplified surge pricing model, future work could integrate complex, real-time game-theoretic pricing strategies. The authors aim to extend this framework to other "gig economy" markets beyond ride-sharing and 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},
}
Figure