Empty-Car Routing in Ridesharing Systems

Anton Braverman (), J. G. Dai (), Xin Liu () and Lei Ying ()
Additional contact information
Anton Braverman: Kellogg School of Management, Kellogg Global Hub, 2211 Campus Drive, Evanston, Illinois 60208
J. G. Dai: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853; Institute for Data and Decision Analytics (iDDA) and Shenzhen Research Institute of Big Data, The Chinese University of Hong Kong, Shenzhen, 518172 China
Xin Liu: School of Electrical, Computer, and Energy Engineering, Arizona State University, Tempe, Arizona 85281
Lei Ying: School of Electrical, Computer, and Energy Engineering, Arizona State University, Tempe, Arizona 85281

Operations Research, 2019, vol. 67, issue 5, 1437-1452

Abstract: This paper considers a closed queueing network model of ridesharing systems, such as Didi Chuxing, Lyft, and Uber. We focus on empty-car routing, a mechanism by which we control car flow in the network to optimize system-wide utility functions, for example, the availability of empty cars when a passenger arrives. We establish both process-level and steady-state convergence of the queueing network to a fluid limit in a large market regime where demand for rides and supply of cars tend to infinity and use this limit to study a fluid-based optimization problem. We prove that the optimal network utility obtained from the fluid-based optimization is an upper bound on the utility in the finite car system for any routing policy, both static and dynamic, under which the closed queueing network has a stationary distribution. This upper bound is achieved asymptotically under the fluid-based optimal routing policy. Simulation results with real-world data released by Didi Chuxing demonstrate the benefit of using the fluid-based optimal routing policy compared with various other policies.

Keywords: ridesharing; fluid limit; closed queueing network; BCMP network; car routing (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
https://doi.org/opre.2018.1822 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:5:p:1437-1452

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().