Dynamic Matching for Real-Time Ridesharing

In a ridesharing system such as Uber or Lyft, arriving customers must be matched with available drivers. These decisions affect the overall number of customers matched, because they impact whether or not future available drivers will be close to the locations of arriving customers. A common policy used in practice is the closest driver (CD) policy that offers an arriving customer the closest driver. This is an attractive policy because no parameter information is required. However, we expect that a parameter-based policy can achieve better performance.We propose to base the matching decisions on the solution to a linear program (LP) that accounts for (i) the differing arrival rates of drivers and customers in different areas of the city, (ii) how long customers are willing to wait for driver pick-up, and (iii) the time-varying nature of all the aforementioned parameters. Our main theorems establish the asymptotic optimality of an LP-based policy in a large market regime in which drivers are fully utilized. We show through extensive simulation experiments that an LP-based policy significantly outperforms the CD policy when there are large imbalances in customer and driver arrival rates across different areas in the city.