Fluid-Model-Based Car Routing for Modern Ridesharing Systems
| Autor: | Jim Dai, Xin Liu, Anton Braverman, Lei Ying |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
050210 logistics & transportation
Static routing Mathematical optimization Fluid limit Queueing theory Computer science Computer Networks and Communications 05 social sciences 010501 environmental sciences BCMP network 01 natural sciences Network utility Hardware and Architecture 0502 economics and business Convergence (routing) Layered queueing network Routing (electronic design automation) Simulation Software 0105 earth and related environmental sciences |
| Zdroj: | SIGMETRICS (Abstracts) |
| ISSN: | 0163-5999 |
| DOI: | 10.1145/3143314.3078595 |
| Popis: | We consider 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, e.g. 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-word data released by Didi Chuxing demonstrate that the utility under the fluid-based optimal routing policy converges to the upper bound with a rate of 1/√N, where N is the number of cars in the network. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|