<="http://www.w3.org/1999/xhtml"> CMU Theory Lunch
Dynamic Matching for Real-Time Ridesharing
September 20, 2017

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 continuous linear program (CLP) that accounts for (i) the differing arrival rates of customers and drivers 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. We prove asymptotic optimality of a CLP-based policy in a large market regime. However, solving the CLP is difficult, thus we also propose matching policies based on a linear program (LP). We prove asymptotic optimality of an LP-based policy in a large market regime in which drivers are fully utilized. We conduct simulation experiments to test the performance of the CD, LP-based, and CLP-based policies.

*** This is joint work with Erhun Ozkan.

Short Bio:

Amy R. Ward is a Professor in the Data Sciences and Operations Department in the Marshall School of Business at the University of Southern California (USC). She received her Ph.D. from Stanford University in 2001. Her research focuses on the approximation and control of systems in which uncertainty and variability are present, and cannot be ignored. Service systems are her main application area. She has over 25 journal publications. She received the Marshall Deans Award for Research Excellence in 2015. She is the chair of the INFORMS Applied Probability Society (term 11/2016-11/2018) and the Service SIG Chair of the INFORMS MSOM Society (term 6/2017-6/2019). She serves as an Associate Editor for Operations Research, Stochastic Systems, and Operations Research Letters.