Empty-Car Routing in Ridesharing Systems

• 成果类型: Article
• 署名作者: Braverman, Anton; Dai, J. G.; Liu, Xin; Ying, Lei
• 署名单位: Northwestern University; Cornell University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; The Chinese University of Hong Kong, Shenzhen; Arizona State University; Arizona State University-Tempe
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1822
• 发表日期: 2019
• 页码: 1437-1452
• 关键词: queuing-networks; demand; taxi

摘要

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.