Abstract
This paper introduces a novel real-time assignment model for ridesourcing that bridges the gap between immediate matching and batch processing. By accounting for rider impatience through a continuous "quitting function," the proposed MULTI-REQ algorithm strategically decides whether to match a rider immediately or wait for a potentially closer driver to arrive. Evaluations on both synthetic and real-world NYC taxi datasets demonstrate that MULTI-REQ improves overall system efficiency by 10-20% over existing baselines while maintaining a balance between wait times and matching costs.
Introduction
Ridesourcing platforms like Uber and Lyft face a fundamental trade-off between two matching strategies. Batch Matching waits for a fixed window (e.g., 1 minute) to find a global optimum, which is efficient for the system but increases initial rider wait times. Conversely, Immediate Matching pairs riders the moment they request a ride, minimizing initial wait but often resulting in inefficient assignments—such as a driver being dispatched from five minutes away when a closer one might have appeared seconds later.
The authors identify a critical missing "middle ground": real riders are impatient and may cancel their requests at any time if the wait feels excessive. The challenge lies in designing an algorithm that calculates the optimal duration to wait for a "better" driver before the risk of the rider quitting becomes too high.
Methodology
The authors approach the problem through a two-step optimization process:
1. The Single-Request Case
They first solve the problem for a single rider and multiple driver types arriving via a Poisson process. This results in an optimal threshold strategy ($T^*$): for every available driver type, there is a specific time threshold. If the current best available driver is of a certain type, the algorithm waits until time $T^*$ in hopes of a closer driver appearing. If no superior match arrives by that time, the match is executed.
2. The Multi-Request Algorithm (MULTI-REQ)
Scaling this to hundreds of simultaneous requests involves a "Continuous Markov Decision Process," which is typically computationally prohibitive. To address this, the authors employ a decomposition approach:
- Virtual Matching: Each active request is "virtually" paired with the best currently available driver.
- Rate Sharing: The total arrival rate of future drivers is decomposed among all active requests. Each request is treated as a subproblem that "owns" a fraction of the probability that a new driver will appear nearby.
- Two-Stage Optimization: Linear approximations are used to solve the matching and rate allocation efficiently, ensuring the algorithm maintains an $O(n^2)$ update time per event, suitable for real-time operations.
Experimental Evaluation
The researchers evaluated MULTI-REQ using two primary data sources:
- Synthetic Datasets: Used to stress-test the algorithm under varying levels of rider impatience and matching importance.
- NYC Taxi Dataset: 100,000 real-world trip records from New York City (2010-2013), providing a realistic distribution of spatial and temporal demand.
Key Results and Insights
MULTI-REQ consistently outperformed standard baselines, including Greedy and Batch matching, by 10% to 20% in terms of the Empirical Competitive Ratio (ECR). Unlike models that assume riders stay indefinitely or leave at a hard deadline, this model's continuous quitting probability function more accurately reflects human behavior.
Strategic Waiting
The algorithm demonstrates that "Greedy" matching is rarely optimal. By waiting just a few extra seconds, the system can significantly reduce "deadhead" miles—the distance drivers travel without a passenger. In real-world simulations, MULTI-REQ achieved a superior balance: while Greedy matching resulted in 455 "No Wait" assignments but high matching costs, MULTI-REQ strategically chose 346 "No Wait" and 131 "Wait & Match" outcomes, leading to a lower total system cost.
Conclusion and Future Work
While MULTI-REQ provides a robust framework for real-time assignment, several avenues for future research remain. The current model assumes drivers stay in the system until matched, whereas in reality, drivers may also log off if they wait too long. Additionally, the model focuses on one-to-one matching and does not yet account for carpooling or ride-sharing scenarios. Finally, future iterations could explore how the algorithm handles potential errors in historical arrival rate ($\lambda$) estimates.
Summary updated