Empty-Car Routing in Ridesharing Systems
| Autor: | J. G. Dai, Anton Braverman, Lei Ying, Xin Liu |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Fluid limit
Queueing theory Mathematical optimization 050208 finance 021103 operations research Optimization problem Computer science 05 social sciences 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research BCMP network Upper and lower bounds Computer Science Applications Network utility 0502 economics and business Convergence (routing) Routing (electronic design automation) |
| Zdroj: | Operations Research. 67:1437-1452 |
| ISSN: | 1526-5463 0030-364X |
| DOI: | 10.1287/opre.2018.1822 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|