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).
- 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
- Optimization Objectives: They formulate two primary goals:
- Driver Profit Maximization: Maximizing the 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).
- 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.
- Online Heuristics: Since real-world platforms don't know future requests, they propose two online versions:
- 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.
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.
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