Matching Drivers to Riders: A Two-Stage Robust Approach

Smarter Matchmaking for Ride-Hailing Platforms Ride-hailing platforms such as Uber, Lyft, and DiDi must assign drivers to riders every minute without knowing who will request a ride next. Most systems optimize each batch myopically, and this can leave some future riders waiting much longer than necessary. In “Matching Drivers to Riders: A Two-Stage Robust Approach,” accepted for publication in Operations Research, the authors propose a two-stage robust matching model that incorporates uncertainty about future demand. The first stage matches current riders, reserving enough nearby drivers for plausible future scenarios; the second stage then tests these decisions against the most adverse demand patterns to guarantee good performance even in the worst case. The authors prove that finding the best such policy is computationally hard, but they develop constant factor approximation algorithms for several practically relevant cases and test them on large-scale taxi data from Shenzhen, China. Their methods substantially reduce maximum rider waiting times with little or no sacrifice in average travel distances.