Empty-car routing in ridesharing systems

Anton Braverman, J. G. Dai, Xin Liu, Lei Ying

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1437-1452
Number of pages16
JournalOperations Research
Volume67
Issue number5
DOIs
StatePublished - 2019

Keywords

  • BCMP network
  • Car routing
  • Closed queueing network
  • Fluid limit
  • Ridesharing

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Empty-car routing in ridesharing systems'. Together they form a unique fingerprint.

Cite this