Empty-car routing in ridesharing systems

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

Source-linked AI summary

Empty-car routing in ridesharing systems

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

arXiv:1609.07219v4Sep 23, 2016math.PR

TL;DR

Ridesharing systems need effective empty-car routing, but optimizing routing-dependent availability is difficult. The paper models these systems as closed queueing networks, proves convergence to a fluid limit, and uses a fluid-based optimization. Its optimal policy provides an asymptotically tight upper bound and is supported by real-world ridesharing data, while robustness to changing parameters remains an open limitation.

Problem
The paper asks how to choose an empty-car routing policy to maximize a utility function when routing-dependent availability makes the optimization difficult.
Method
The paper models ridesharing as a closed queueing network, proves process-level and steady-state convergence to a fluid limit, and formulates a broadly applicable fluid-based optimization solvable through linear constraints.
Results
The fluid-based optimal static policy upper-bounds performance under state-dependent policies, achieves asymptotic tightness, and is effective on real-world ridesharing data.
Takeaways & Limitations
The resulting policy offers a theoretically grounded and efficient approach for designing empty-car routing policies in practical ridesharing systems.
Takeaways & Limitations
The paper does not provide a rigorous analysis of the lookahead policy for time-varying parameters.

Abstract

from arXiv · show

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, 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-world data released by Didi Chuxing demonstrate the benefit of using the fluid-based optimal routing policy compared to various other policies.

1. Introduction

The paper models ridesharing as a closed queueing network and studies empty-car routing to optimize system-wide utility, especially regional availability. It develops a fluid-based approach that is efficiently solvable and asymptotically optimal, with real-world motivation and numerical support.

System model: Cars are modeled as jobs in a closed queueing network, with single-server stations for passenger waiting and infinite-server stations for travel.The routing matrix Q controls whether empty cars stay in a region or relocate, and may depend on the current car distribution.
System model: Regional availability is the long-run fraction of time that at least one empty car is present, also giving the passenger fulfillment probability under Poisson arrivals.Empty cars can remain after completing a trip or relocate without a passenger to wait elsewhere.
Optimization challenge: Optimizing utility over routing policies is difficult because availability depends nonlinearly on Q, producing a non-convex problem that standard solvers could not reliably solve.The difficulty appears even in the two-region case.
Main results: As the number of cars and passenger arrival rates grow, the finite-system optimum converges to a fluid-based optimization whose solution can be obtained through a linear program.The framework accommodates a broad class of utilities involving regional availability and empty or occupied cars on roads.
Main results: The fluid-based optimal static policy upper-bounds performance under any state-dependent routing policy, and this bound is asymptotically tight.The queue-length process and steady-state distributions are proven to converge to the corresponding fluid descriptions.
Practical relevance: The proposed routing framework is intended to guide high-performance empty-car policies in practical ridesharing systems.The introduction motivates empty-car routing as a mechanism for improving system efficiency.

2. The Ridesharing Optimization Problem

The paper models ridesharing as a closed queueing network and formulates fluid-based optimization for static empty-car routing. The formulation captures car flows, ride availability, and utility while connecting static policies to state-dependent routing.

System model: The system contains N cars serving r regions, with empty and full cars represented by routing and queueing processes.Empty cars may wait in regions or travel between regions; full cars travel with passengers.
Fluid-based optimization: The fluid-based optimization uses routing q and steady-state variables for empty cars, full cars, and regional availability.The variables are q, ¯e, ¯f, and ¯a, with availability linked to ride initialization rates and rewards.
Fluid-based optimization: Its constraints encode full-car and empty-car Little’s Laws, regional flow balance, and the relationship between availability and idle cars.For example, λ_iP_ij¯a_i equals µ_ij¯f_ij for full-car flows, while availability shortages require zero idle-car mass.
Fluid-based optimization: The objective framework accommodates a broad class of utility functions, beyond the reward-based formulation shown in the optimization problem.The displayed formulation interprets c_ij as rewards for rides from region i to j.
Main results: The main results connect the fluid optimization to the scaled queueing process and compare its static policy with state-dependent policies.The analysis assumes P_ij > 0, q_ii > 0, and travel-time distributions with rational Laplace transforms for Theorem 1.
Efficient solution and main results: The fluid optimization can be transformed into a problem with only linear constraints, and its optimal value upper-bounds finite-system utility under state-dependent routing.The upper bound is asymptotically achievable under the corresponding static routing policy.

3. A Numerical Study

The numerical study evaluates fluid-based and dynamic empty-car routing policies on a nine-region network using Didi data, including time-varying demand and parameter-estimation noise. Fluid-based routing provides a benchmark, while lookahead policies prepare for parameter changes and can improve later-period performance.

Didi data yielded a nine-region network with realistic parameters for cars, travel, demand, and routing.
Three regions had significant supply shortages during most observed 5PM–6PM evening rush hours, while most orders in other regions were fulfilled.
Performance comparison: The fluid-based optimization gives an upper bound on finite-system utility for state-dependent routing policies.
Performance comparison: The fluid-based optimal static policy outperformed the tested SW and JLCR-η state-dependent policies, with JLCR-0.5 best within the JLCR family at N = 2,000.
Time-varying parameters: A standard fluid policy degraded after a 7pm parameter change, whereas lookahead policies anticipated changes by pre-positioning cars.
Time-varying parameters: A 45-minute lookahead sacrificed 4% during 6–7pm but raised 7–8pm performance to 86%, compared with 67% for the standard fluid policy.
Robustness: With parameter-estimation errors of 5% and 10%, the resulting policies were approximately 5% and 10% suboptimal, respectively.

4. The Fluid Model

The paper develops a fluid model for the ridesharing network and studies its equilibrium behavior under static empty-car routing. The model supports convergence analysis and a fluid-based optimization whose constraints characterize equilibrium states.

The analysis establishes process-level convergence of the scaled queueing-network processes to the fluid model.
The fluid model’s equilibrium behavior motivates the fluid-based optimization problem.
The fluid model describes static empty-car routing through equations (19)–(22), with total fluid in the system always equal to one.
Equilibrium behavior: Under Pij > 0 and Qii > 0, the equilibrium equations have at least one solution, although multiple solutions may differ in certain eii components.
Equilibrium behavior: The equilibrium set has a unique associated utilization vector and a unique quantity m̄.
Assumptions: The equilibrium results rely on positivity assumptions, though the authors expect analogous results when the CTMC has a single recurrent class.

5. Conclusions

The paper analyzes ridesharing networks in a large-market regime and develops an asymptotically optimal empty-car routing policy. It also identifies centralized control, time-varying parameters, and transient behavior as important boundaries for future work.

The analysis considers ridesharing networks as both car supply and passenger demand tend to infinity.
The paper proposes an optimal empty-car routing policy based on asymptotic fluid analysis.
Real-world ridesharing data confirmed the effectiveness of the proposed solution.
Decentralized routing: The centralized routing policy assumes that the platform has full control over empty cars and provides a best-case benchmark.
Decentralized routing: Designing decentralized incentive mechanisms to achieve the centralized solution's routing probabilities remains future work.
Time-varying parameters: The T-lookahead policy is a heuristic for time-varying parameters, while rigorous time-varying and transient control remain open problems.

EC.1. Process Level Convergence for Closed Networks of Single and Infinite Server Stations

This section establishes process-level fluid convergence for closed queueing networks containing single-server and infinite-server stations. The ridesharing model is a special case of the broader network results.

The networks studied contain both single-server and infinite-server stations, with stations indexed by J.
As the number of jobs and service rates increase, the appropriately scaled queue-length process converges to a fluid limit.
The ridesharing model is a special type of the considered queueing networks, making its convergence theorem a special case of the general result.
The process-level convergence result differs from prior work because the limiting process is not defined through a differential inclusion.

EC.1.1. The Fluid Model

The fluid-model section states conditions under which the scaled queueing-network process converges to a fluid trajectory. It establishes existence and uniqueness properties for the limiting representation.

The theorem applies to a network with both single-server and infinite-server stations through the scaled process formulation.
The fluid model has a unique solution under the stated network assumptions.
Theorem EC.1 assumes convergence of the initial scaled state and establishes a fluid-limit representation over every finite time horizon.
The proof uses a functional strong law of large numbers and the continuous mapping theorem.
The ridesharing convergence theorem follows immediately as a special case of Theorem EC.1.

EC.1.2. Proof of Lemma EC.1

The proof constructs the fluid solution through a Skorohod problem and an integral equation. Lipschitz bounds yield existence and uniqueness, completing the key continuity argument.

The proof introduces the Skorohod problem associated with the input path and routing matrix.
The resulting mapping is Lipschitz-continuous, establishing the required continuity relation and completing the lemma's proof.
The construction defines an integral operator and solves an associated integral equation for the fluid state.
The iterative sequence is shown to be Cauchy and therefore converges to a solution of the integral equation.
Uniqueness follows by applying the same recursive bounds to two potential solutions.

EC.2. Proof of Theorem 4

The proof establishes Theorem 4 by constructing a Lyapunov function for the fluid model and applying LaSalle’s Invariance Principle. Positive limit points are shown to lie in the equilibrium set.

Lyapunov argument: The proof defines V on the fluid-model state space and uses V(e(t),f(t)) as a Lyapunov function.The function is continuous, and its composition with the fluid trajectories is Lipschitz-continuous.
Regular points: Regular points are times at which the relevant diagonal and off-diagonal state functions are differentiable.The proof uses these differentiability conditions to establish the derivative relations needed for the Lyapunov analysis.
Lyapunov argument: Lemma EC.2 implies that V is non-increasing along fluid-model trajectories.Consequently, V has a finite limit as time tends to infinity.
Limit-set analysis: LaSalle’s Invariance Principle is applied to the nonempty, compact, positively invariant set of positive limit points.The proof uses continuity and positive invariance to keep the limiting trajectory within this set.
Conclusion: All positive limit points belong to the equilibrium set E, which proves Theorem 4.This conclusion follows after combining the limit-set argument with Lemma EC.2.

EC.2.1. An Illustrative Example

The illustrative example examines a three-region configuration to explain why apparent non-equilibrium behavior conflicts with the definition of a regular point. The contradiction supports the strict Lyapunov decrease argument.

Example setup: The example assumes r = 3, with ¯a1 < 1, ¯a2 = ¯a3 = 1, and ¯m > 0.It is used to develop intuition before the general algebraic expansion.
Contradiction: The apparent contradiction arises because the selected configuration would imply incompatible derivative conditions for the fluid variables.The argument combines the model equations with the assumed signs of the state deviations.
Contradiction: If the time were regular, equation (EC.28) would force ˙f2k = 0 for every k because ˆf2k = 0.The example then derives ˙f2k < 0, contradicting regularity.

EC.2.2. Proof of Lemma EC.2

Lemma EC.2 is proved by showing that the Lyapunov derivative is strictly negative at every regular point outside E. The proof rules out all configurations that could make the derivative zero.

Derivative conditions: The derivative expansion consists of non-positive terms, so equality requires a collection of sign and zero conditions across regions.The proof classifies regions according to the conditions required for ˙V(e,f) = 0.
Assumptions: The proof assumes Pij > 0 and Qii > 0 for all regions, while noting that the lemma may hold under weaker conditions.These assumptions are imposed to keep the case analysis manageable.
Ruling out cases: Several region types are impossible because their conditions contradict the fluid equations or conservation of total mass.The proof specifically rules out types 4a, 4c, and 2c, among others.
Ruling out cases: When some regions satisfy ¯ai = 1, the existence of type 3 or type 4b regions eliminates type 1 and type 2a configurations.Their required signs for ˆfij are incompatible.
Conclusion: Therefore, at every regular point outside E, ˙V(e,f) < 0.The argument uses conservation of fluid mass to exclude equality.
Remaining case: In the remaining case, the proof shows that a type 3′ region must exist and derives a contradiction from the required flow derivatives.This completes the exclusion of ˙V(e,f) = 0 outside E.

EC.2.3. Proof of Lemma EC.4

Lemma EC.4 supplies the algebraic expansion of the Lyapunov derivative used in Lemma EC.2. The proof expands each term and verifies that the resulting expression matches the required derivative formulas.

Case split: The proof handles separately the case where some regions satisfy ¯ai = 1 and the case where no such regions exist.The second case changes the summation range in one line of the derivative expression.
Algebraic expansion: Equations (EC.41)–(EC.43) are combined with the earlier derivative relations to expand the terms in (EC.45)–(EC.50).The proof manipulates one line at a time because the resulting expression is bulky.
Algebraic expansion: The expansions of (EC.57)–(EC.59) are obtained by differentiating the fluid equations and using equation (EC.34).These substitutions put the derivative terms into the form required for comparison.
Verification: The resulting expression for 1/2 ˙V(e,f) matches the target expression (EC.35).The proof verifies the identity after inserting all termwise expansions.
Verification: In the second case, the same calculations with summations over all regions verify equation (EC.36).This completes the proof of Lemma EC.4.

EC.2.4. Proof of Lemma EC.3

The proof develops conditions for applying a stability argument to the relevant differential equation, emphasizing existence, uniqueness, continuity, and a limitation on global existence.

The proof transfers the argument from Lemma EC.1 to Lemma EC.3.
The argument relies on solution existence, uniqueness, and continuous dependence on initial conditions.These are identified as the three properties needed for the cited lemma.
Global existence is not guaranteed for all t ≥ 0, although uniqueness and the analogous continuity property are established.

EC.3. Two Examples of Networks

The paper evaluates 9-region and 5-region ridesharing networks using synthetic scenarios and Didi Chuxing data, then uses a fluid-based optimization to study perfect availability and fleet sizing.

Network examples: The numerical study uses both 9-region and 5-region network examples.The 9-region network is constructed from major geographical regions in the Didi Chuxing data.
Data and calibration: Didi Chuxing orders provide origins, destinations, timestamps, fulfillment status, fulfilling-car identifiers, and trip prices.
Data and calibration: The empirical transition matrix P is estimated from origin-destination order counts during the 5-6pm window.For each origin i, orders from i to j are divided by total orders originating at i.
Data and calibration: Travel-time rates µ are calibrated from average trip costs because the dataset does not provide travel times.The time unit is a 10-minute interval; a 14.1 CNY average cost yields an assumed 14-minute travel time and µ47,50 = 1.41.
Data and calibration: The study chooses N = 2000 cars, and numerical results remain qualitatively consistent for nearby fleet sizes.
Perfect availability and fleet sizing: If κ > 1, perfect availability is infeasible at the current scale but becomes feasible when fleet size increases by factor κ.
Perfect availability and fleet sizing: If κ ≤ 1, perfect availability is feasible and remains feasible when λ is increased to the stated threshold.
Perfect availability and fleet sizing: The optimal fluid mass κ measures the minimum fluid capacity needed for perfect availability and indicates supply-demand imbalance.