Matching Drivers to Riders: A Two-Stage Robust Approach

Matching demand (riders) to supply (drivers) efficiently is a fundamental problem for ride-sharing platforms that need to match the riders (almost) as soon as the request arrives with only partial knowledge about future ride requests. A myopic approach that computes an optimal matching for current requests ignoring future uncertainty can be highly suboptimal. In this paper, we consider a two-stage robust optimization framework for this matching problem in which future demand uncertainty is modeled using a set of demand scenarios (specified explicitly or implicitly). The goal is to match the current request to drivers (in the first stage) so that the cost of first stage matching and the worst case cost over all scenarios for the second stage matching is minimized. We show that the two-stage robust matching is NP-hard under various cost functions and present constant approximation algorithms for different settings of our two-stage problem. Furthermore, we test our algorithms on real-life taxi data from the city of Shenzhen and show that they substantially improve upon myopic solutions and reduce the maximum wait time of the second stage riders.

Funding: This work was supported by the National Science Foundation [Grant CMMI 1636046] (for V. Goyal).

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2021.0668.