Journal Article

Empty-Car Routing in Ridesharing Systems

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

2019

Overview

Understanding the Fundamentals of Empty-Car Routing in Ridesharing Systems How to efficiently route empty-cars in ridesharing systems? In this paper “Empty-car Routing in Ridesharing Systems,” A. Braverman, J.G. Dai, X. Liu, and L. Ying introduce a novel model based on closed queueing networks and propose an optimization framework to optimize empty-car routing for maximizing system-wide utility functions. We propose a fluid-based optimal routing policy by solving the optimization problem in a large market regime. We establish both process-level and steady-state convergence of the closed queueing network to the fluid-limit and prove 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 under which the closed queueing network has a stationary distribution. This upper bound is achieved asymptotically under the fluid-based optimal routing policy. 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.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: Automobiles / BCMP network / Car pools / car routing / closed queueing network / Computer simulation / fluid limit / Job shops / Methods / Network management software / Operations research / Optimization / Queues / Research funding / Ride sharing services / ridesharing / Routing / Simulation / Upper bounds