PaperlayerView exact revision on arXiv

Source-linked AI summary

Empty-car routing in ridesharing systems

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

arXiv:1609.07219v4math.PR

TL;DR

The paper studies how to route empty cars in closed ridesharing networks to optimize utility. It develops a fluid-based optimization approach and shows that its policy is preferable to no empty-car routing and effective on real-world data.

  • Problem

    The paper asks how to choose empty-car routing for a given utility function in a ridesharing network.

    Source: §1 · p. 4

  • Method

    It models cars as jobs in a closed queueing network with single-server and infinite-server stations and develops a fluid-based optimization approach.

    Source: §1 · p. 2

  • Results

    The policy with Q21 = 1/3 is preferable to no empty-car routing, and real-world ridesharing data confirmed the solution’s effectiveness.

    Source: §1 · p. 4, §5 · p. 32

  • Takeaways & Limitations

    The centralized control mechanism provides a best-case performance benchmark for comparing empty-car routing policies.

    Source: §1 · p. 7

    The paper identifies rigorous analysis of varying parameters as an open question.

    Source: §5 · p. 32

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

This section models ridesharing as a closed queueing network and develops a fluid-based framework for empty-car routing and network utility optimization in large, potentially time-varying markets. It connects the fluid model to the underlying stochastic BCMP network, establishes convergence and asymptotic-optimality guarantees, and introduces the notation used throughout.

1. Introduction

  • The model represents cars as jobs in single-server waiting stations and infinite-server travel stations, with routing policy Q controlling whether empty cars stay or relocate.Passenger arrivals trigger rides when cars are available; after reaching destinations, cars become empty and follow Q, which may depend on the current car distribution.Source: §1 · p. 2
  • Empty-car routing addresses passenger imbalance: in the two-region example, region 1 availability is at most 50% without routing, losing at least half its passengers.Availability is the long-run fraction of time a region has an empty car and, by PASTA, equals the probability an arriving request is fulfilled.Source: §1 · p. 3
  • The example shows that routing matters: with 1200 cars, the policy Q21 = 1/3 is preferable to no empty-car routing, Q12 = Q21 = 0.The comparison concerns regional availabilities under several routing policies, as reported in Table 1.Source: §1 · p. 4, Table 1 · p. 4
  • Optimizing utility over routing policies is difficult because availability depends nonlinearly on Q, making even the two-region problem non-convex and unreliable for standard solvers.MATLAB’s built-in solver failed to converge, and NEOS solvers could not reliably solve the problem.Source: §1 · p. 5
  • As N and passenger arrival rates tend to infinity, the optimal solution converges to a fluid-based optimization problem solvable by linear programming, for a broad class of utility functions.This provides a theoretically grounded and efficient approach to the empty-car routing problem.Source: §1 · p. 5
  • The optimal static policy from the fluid problem upper-bounds performance under any state-dependent routing policy, and the bound is asymptotically tight.The bound is intended to guide policy development when the true optimal policy is unavailable for finite systems.Source: §1 · p. 5
  • The large market regime sends both the number of cars N and passenger arrival rates Nλ to infinity, allowing oversupply, undersupply, and critical supply-demand conditions.The authors argue this regime is more realistic because driver supply naturally increases with ride demand and does not restrict city-level supply-demand imbalance.Source: §1 · p. 6
  • A fluid-based optimization supports a time-dependent lookahead policy that anticipates parameter changes and yields significant performance benefits over interval-by-interval routing with constant parameters.The heuristic is intended to show that fluid optimization can guide high-performance policies when practical modeling assumptions may fail, not to provide the optimal algorithm for such settings.Source: §1 · p. 6
  • Centralized routing generates decisions through a routing matrix Q, providing a best-case benchmark for decentralized mechanisms and a way to quantify the “price of anarchy”.The centralized mechanism is also applicable to autonomous vehicles, while part of the gap from decentralized control could motivate driver compliance through incentives such as fuel subsidies.Source: §1 · pp. 6–7

1.1. Related Literature

  • Unlike earlier fluid models used only as heuristics, this paper proves that its fluid model is the limit of the BCMP network’s queue-length process and that its fluid optimization problems limit their stochastic counterparts.The related literature includes ridesharing repositioning, fleet-sizing, and pricing models, while the paper’s contribution is the rigorous stochastic-to-fluid connection.Source: §1.1 · pp. 7–8
  • Unlike prior empty-car routing studies that focus on individual optimization problems and often equalize regional availabilities, this approach handles a large class of optimization problems and remains relevant when demand is comparable to or exceeds supply.The prior equal-availability approach can hurt performance in the paper’s two-region example, where equalization requires Q12 = 0 and Q21 = 1/2.Source: §1.1 · pp. 7–8
  • The technical novelty is Theorem 4’s characterization of fluid-model limiting behavior, using L1 distance from equilibrium as a Lyapunov function rather than relative entropy [Anselmi et al. (2013)].Related work established process-level convergence for comparable closed networks, while Anselmi et al. (2013) studied networks without infinite-server stations.Source: §1.1 · p. 9

1.2. Contributions

  • For fixed static routing Q, the paper proves process-level and steady-state convergence to a fluid limit, characterizes its equilibrium set, and establishes convergence from every initial condition.The results also address the minimum cars needed for 100% availability everywhere asymptotically as N →∞.Source: §1.2 · p. 10
  • The fluid-based optimization accommodates utilities involving regional availabilities and empty or occupied road fractions, is efficiently reducible to linear constraints, and yields Q∗ asymptotically optimal among state-dependent policies.The asymptotic-optimality result is stated in Theorem 2 as the number of cars grows to infinity.Source: §1.2 · p. 10

1.3. Notation

  • The notation section defines derivatives, cadlag and continuous function spaces, max-norms and set cardinalities, and weak convergence notation.These definitions support the paper’s fluid-limit and convergence statements.Source: §1.3 · pp. 10–11

2. The Ridesharing Optimization Problem

This section formulates a fluid-based optimization for a closed ridesharing network with state-dependent empty-car routing, car flows, and availability variables. It relates the optimization to stationary system utility, establishes upper-bound and asymptotic-achievability guarantees, and develops a tractable linear-program-based procedure with extensions to broader utility functions.

2. The Ridesharing Optimization Problem

  • The model tracks empty cars waiting or traveling between regions and full cars carrying passengers in a continuous-time Markov chain with committed routing decisions.Cars remain committed to their chosen destination until a passenger arrives, and the process can be interpreted as a closed queueing network.Source: §2 · pp. 11–12

2.1. Main Results

  • The fluid-based optimization uses a static routing matrix and variables representing empty-car flow, full-car flow, and availability, with Little’s Law and flow-balance constraints.Its objective maximizes revenue generated by completed rides, while availability constraints capture when demand is unmet or all requests are served.Source: §2.1 · pp. 13–14
  • Theorem 1 connects feasible fluid-optimization solutions to the stationary fluid-scaled network, while Theorem 2 shows that the optimal static policy asymptotically outperforms all state-dependent policies.The comparison assumes the relevant Markov chain has a single recurrent class; the stated positivity assumptions are mainly used to facilitate the proof.Source: §2.1 · pp. 15–16
  • Theorem 1 also extends beyond exponential travel times to travel-time distributions with rational Laplace transforms through the BCMP-network structure.The stationary distribution depends on service rates rather than the entire service-time distribution in this broader class.Source: §2.1 · p. 16
  • The fluid-based optimum is a strict upper bound on expected utility under any state-dependent routing policy with a single recurrent CTMC class, and static routing asymptotically achieves it.This combines Theorem 2’s upper-bound and asymptotic-achievability results for the finite-car system.Source: §2.1 · p. 16

2.2. Efficient Solution of the Fluid-Based Optimization

  • Bilinear constraints in the fluid optimization are transformed into linear constraints, leaving only one bilinear constraint that can be safely ignored without changing the optimum.The transformation uses Lemma 1, while Lemma 2 modifies an optimal relaxed solution when necessary so it satisfies the omitted constraint with the same objective value.Source: §2.2 · pp. 16–18
  • The resulting solution procedure solves a linear program, optionally applies Lemma 2, and recovers the optimal routing policy using equation (11).The linear program has (4r^2 + 2r + 1) constraints and 2r^2 + r variables.Source: §2.2 · p. 18
  • The optimization and performance guarantees extend to utility functions nondecreasing in availability and flow, independent of self-loops, and concave in (¯e, ¯f).The extension uses conditions (a)–(e), with Jensen’s inequality supporting the fluid bound.Source: §2.2 · p. 18

3. A Numerical Study

Numerical studies on realistic 5-region and 9-region Didi networks evaluate fluid-based static and lookahead routing policies under time-varying demand. They examine comparative performance, pre-positioning, and robustness to moderate estimation error.

3. A Numerical Study

  • The study uses DRI (2016) data to construct a nine-region network with realistic parameters N, µ, λ, and P.Figure 2 examines fulfillment during the 5PM–6PM rush hour over 21 days.Source: §3 · pp. 18–19, Figure 2 · p. 19
  • Regions 13, 47, and 50 experienced significant supply shortages on most observed days, whereas most orders in the other six regions were fulfilled.The data could not determine the surplus of drivers in those six regions.Source: §3 · p. 19

3.1. Performance Comparison with Dynamic Routing Polices

  • Static routing under Q∗ outperforms SW and the JLCR-η family, while JLCR-0.5 maximizes availability among JLCR variants when N = 2,000.Q∗ requires λ, µ, and P, whereas JLCR-0.5 requires only λ, making robustness to parameter noise or change an important consideration.Source: §3.1 · pp. 21–22, Figure 3 · p. 22

3.2. Time-varying Parameters and the Lookahead Heuristic

  • Because parameters can vary faster than the system reaches equilibrium, the authors propose a T-lookahead policy that updates the fluid-based routing matrix over time.The method is intended to extend the stationary fluid-model framework to time-varying settings.Source: §3.2 · p. 23
  • The T-lookahead policy uses parameter averages over [t,t+T] to make time-varying routing decisions, with examples using 30- and 45-minute windows.Numerical decisions are discretized into one-minute intervals, and the lookahead policy is compared with standard fluid, JLCR, and SW routing.Source: §3.2 · p. 24

3.2.1. The 5-Region City

  • In the 5-region city, lookahead routing anticipates parameter changes by pre-positioning cars, whereas standard fluid performance degrades after the 7pm change.Standard fluid performs well during the initial 5–7pm slot but leaves the system far from the next fluid equilibrium; lookahead performance is consistent across initial configurations.Source: §3.2.1 · p. 25
  • 86% performance during 7–8pm versus 67% for standard fluid, after sacrificing 4% during 6–7pm with 45-minute lookahead.The 19% increase corresponds to 433 additional customers, while the earlier 4% drop corresponds to approximately 61 customers lost.Source: §3.2.1 · p. 25

3.2.2. The 9-Region Didi Network

  • In the 9-region Didi network, standard fluid performance again suffers after abrupt parameter changes, while lookahead corrects for them without a longer-window penalty in hour 2.With excess supply and nearly 100% availability during the first two hours, the 45-minute policy can pre-position cars for hour 3 without hurting hour-2 performance.Source: §3.2.2 · p. 26

3.3. Robustness

  • 5% and 10% estimation errors produce policies that are approximately 5% and 10% suboptimal, respectively.The study computes routing from noisy parameter estimates and evaluates it under the true parameters; sensitivity outside the tested examples depends on the parameter choice.Source: §3.3 · p. 27

4. The Fluid Model

The section formulates the ridesharing fluid model and establishes process-level convergence, then characterizes its equilibria and their connection to the fluid-based optimization problem. Under positivity assumptions, equilibria exist, may be nonunique in specific idle-car components, and motivate convergence to the equilibrium set.

4. The Fluid Model

  • The fluid model is defined by equations (19)–(22), and the scaled process converges to this dynamical system at the process level.The fluid trajectories are Lipschitz-continuous, supporting subsequent equilibrium analysis.Source: §4 · pp. 28–29

4.1. Equilibrium Points

  • At equilibrium, the fluid constraints coincide exactly with constraints (4b)–(4g) of the fluid-based optimization problem.The total amount of fluid remains one throughout the system’s evolution.Source: §4.1 · p. 30
  • Under Pij > 0 and Qii > 0 for all i,j, the equilibrium equations have at least one solution, although multiple solutions may exist.All solutions agree in a, off-diagonal f and e components, and diagonal e components with ai < 1; differences can remain in diagonal e components with ai = 1.Source: §4.1 · p. 31
  • The equilibrium set determines a unique utilization vector a and a unique quantity m, providing the final ingredient for proving Theorem 1.The section also notes that the positivity assumptions simplify the analysis and are expected to be replaceable by a single recurrent-class condition.Source: §4.1 · p. 31

5. Conclusions

The paper develops an asymptotic-fluid-based optimal empty-car routing policy and confirms its effectiveness numerically with real-world ridesharing data. The conclusions identify decentralized control, time-varying policies, and parameter-robust routing as future research directions.

Conclusions

  • The study analyzes empty-car routing as supply and demand grow without bound, designs an optimal policy through fluid analysis, and confirms its effectiveness using real-world ridesharing data.The authors characterize this work as a first step toward understanding ridesharing networks.Source: §5 · p. 32

Decentralized routing

  • The centralized routing policy assumes platform-wide control of empty cars, providing a best-case benchmark for designing decentralized incentive mechanisms.Its performance can quantify the efficiency of decentralized mechanisms.Source: §5 · p. 32

Time-varying parameters

  • The T-lookahead policy is a heuristic for time-varying parameters, motivating rigorous analysis of time-varying and transient control policies.Transient analysis is difficult because convergence can be slow and the fluid model is nonlinear.Source: §5 · p. 32

Robust routing policies

  • Certain state-dependent policies approach optimal static-policy performance without requiring explicit system parameters, motivating provably asymptotically optimal robust policies.The open problem is to minimize reliance on primitive system parameters while retaining asymptotic optimality.Source: §5 · p. 32

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

This appendix section develops process-level convergence for closed exponential-service networks containing single-server and infinite-server stations. Under increasing job counts and single-server service rates, the scaled queue-length process converges to a fluid limit, with the ridesharing model as a special case.

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

EC.1.1. The Fluid Model

This section formulates the fluid model by modifying the routing matrix at infinite-server stations and establishes convergence to a unique fluid solution under converging initial conditions.

EC.1.1. The Fluid Model

  • The modified matrix ˜R is obtained by setting all rows corresponding to infinite-server stations in R to zero, making ˜R^T sub-stochastic.This construction uses μ_i = 0 for i ∈ S and λ_i = 0 for i ∈ I.Source: EC.1.1. The Fluid Model · p. 36
  • The fluid model has a unique solution (q,v) with q(t) ∈ R_+^J and v(t) ∈ R^J.The stated existence and uniqueness result applies over the relevant time domain.Source: EC.1.1. The Fluid Model · p. 36
  • Theorem EC.1 establishes fluid-limit convergence when the scaled initial state converges to a vector a ∈ [0,1]^J.The theorem’s convergence conclusion is stated for every finite time horizon T > 0.Source: EC.1.1. The Fluid Model · pp. 36–37
  • Theorem EC.1 also implies that i(t) = 0 for i ∈ I and t ≥ 0, and Theorem 3 is a special case.The proof uses a functional strong law of large numbers argument.Source: EC.1.1. The Fluid Model · p. 37

EC.1.2. Proof of Lemma EC.1

The proof introduces the Skorohod problem and its Lipschitz properties, then establishes existence, uniqueness, and Lipschitz continuity for the auxiliary integral-equation solution, completing Lemma EC.1.

EC.1.2. Proof of Lemma EC.1

  • The Skorohod problem SP(x, ˜Q) is defined for the reflected pair (z,y), providing the framework for the lemma.Its solution and associated maps are shown to have Lipschitz properties on finite time intervals.Source: EC.1.2. Proof of Lemma EC.1 · p. 38
  • A successive-approximation sequence q_n is constructed for the integral equation, shown to be Cauchy, and proved to converge to a solution.The argument applies on every finite horizon T, yielding existence for the full domain.Source: EC.1.2. Proof of Lemma EC.1 · pp. 39–40
  • Uniqueness follows by applying the same recursive inequality to two candidate solutions and driving their finite-horizon difference to zero.This establishes a unique solution to the integral equations defining the auxiliary map.Source: EC.1.2. Proof of Lemma EC.1 · p. 40
  • The proof repeats the recursive comparison argument for two inputs to establish Lipschitz continuity of Υ, thereby proving (EC.13) and completing the lemma.The final step compares Υ(x) and Υ(˜x) and obtains a finite-horizon bound before taking the approximation index sufficiently large.Source: EC.1.2. Proof of Lemma EC.1 · p. 40

EC.2. Proof of Theorem 4

Theorem 4 is proved by constructing a Lyapunov function for the fluid model and applying LaSalle’s Invariance Principle to show that all positive limit points lie in E.

EC.2. Proof of Theorem 4

  • The proof defines V(e(t),f(t)) as a Lyapunov function and establishes its regular-point derivative properties under P_ij > 0 and Q_ii > 0.The relevant trajectories and auxiliary functions are Lipschitz-continuous, so almost every time is a regular point.Source: EC.2. Proof of Theorem 4 · p. 41
  • Using Lemmas EC.2 and EC.3 with LaSalle’s Invariance Principle, the proof shows that V is non-increasing and that its positive limit set is nonempty, compact, and positively invariant.The limit of V exists, and the positive limit set is then contained in E.Source: EC.2. Proof of Theorem 4 · p. 42
  • The resulting invariant-set argument proves Theorem 4 by establishing L+ ⊂ E for the fluid-model trajectory’s positive limit points.This conclusion follows by applying Lemma EC.2 to trajectories remaining in the positively invariant limit set.Source: EC.2. Proof of Theorem 4 · p. 42
  • The remainder of the section proves Lemma EC.2 by analyzing the Lyapunov derivative at regular points and introducing an illustrative example for intuition.The derivative calculation is developed from the fluid-model equations and regular-point identities.Source: EC.2. Proof of Theorem 4 · p. 43

EC.2.1. An Illustrative Example

Under a three-class parameter configuration with positive transition entries, the example examines selected configurations to build intuition for proving strict negativity of the Lyapunov derivative outside the equilibrium set.

EC.2.1. An Illustrative Example

EC.2.2. Proof of Lemma EC.2

The proof shows that the Lyapunov derivative is strictly negative at every regular point by exhausting equality conditions in two cases and deriving contradictions from region types and conserved fluid mass. It assumes P_ij > 0 and Q_ii > 0 to keep the argument tractable.

Proof assumptions

  • The proof assumes P_ij > 0 and Q_ii > 0 for all i,j, while noting the lemma is conjectured to hold without these conditions.These assumptions are imposed to prevent the subsequent contradiction arguments from becoming more involved.Source: EC.2.2. Proof of Lemma EC.2 · p. 47

First case

  • ˙V(e,f) < 0 at every regular point in the case {i : ¯a_i = 1} ≠ ∅ and the stated mass condition holds.The proof rules out types 4a and 4c, then types 1, 2a, and 2c, and finally shows that equality would imply total mass below one.Source: EC.2.2. Proof of Lemma EC.2 · pp. 47–48

Second case

  • In the second case, conditions 1, 2, and 4 remain unchanged, while condition 3 is replaced by 3′ because line 4 differs between (EC.35) and (EC.36).The proof then establishes that a region of type 2b, 2c, or 4b and a region of type 3′ must exist, ruling out types 1 and 2a.Source: EC.2.2. Proof of Lemma EC.2 · pp. 49–50
  • The existence of a type 3′ region with positive diagonal mass yields a contradiction, so the necessary conditions for ˙V(e,f) = 0 cannot hold and ˙V(e,f) < 0.Conservation supplies a negative flow or off-diagonal error component; the proof shows its derivative must be both zero and strictly negative.Source: EC.2.2. Proof of Lemma EC.2 · pp. 50–51

EC.2.3. Proof of Lemma EC.4

The proof of Lemma EC.4 derives the required Lyapunov-derivative identity by differentiating the defining equations, expanding terms, and combining the resulting relations. It then extends the argument to the complementary case by changing the summation range and concludes (EC.36).

Derivative identities

Algebraic expansion

  • The resulting expressions are expanded term by term in (EC.45)–(EC.50) and (EC.57)–(EC.59), then substituted back to recover the form required by (EC.35).The proof explicitly decomposes bulky terms, evaluates each component, and recombines the expansions before comparing the resulting 2 ˙V(e,f) with (EC.35).Source: EC.2.3. Proof of Lemma EC.4 · pp. 53–54

Complementary case

  • For the case {i : ¯a_i = 1} = ∅ or the stated alternative case, the same proof logic applies after extending the first summation over all i = 1,...,r.This altered summation range yields the analogue of (EC.38)–(EC.40) and replaces the restricted sums in (EC.51)–(EC.56).Source: EC.2.3. Proof of Lemma EC.4 · p. 56

Conclusion

  • Repeating the preceding argument with the modified summations verifies (EC.36) and completes the proof of Lemma EC.4.The conclusion follows after identifying the resulting expression for 2 ˙V(e,f) with the required equation.Source: EC.2.3. Proof of Lemma EC.4 · pp. 55–56

EC.2.4. Proof of Lemma EC.3

Lemma EC.3 is proved by adapting Khalil’s Lemma 4.1 argument, using existence, uniqueness, and continuity with respect to initial conditions where established.

Proof of Lemma EC.3

  • The proof of Lemma EC.3 follows Khalil (2002, Lemma 4.1) after identifying the three properties required for the argument.These properties are guaranteed existence, uniqueness, and continuity with respect to the initial condition.Source: EC.2.4. Proof of Lemma EC.3 · p. 56
  • Although global existence is not guaranteed, uniqueness follows from Lemma EC.1 and the needed continuity analogue follows from (EC.13), allowing the proof to carry through.Thus, the argument establishes Lemma EC.3 despite the difference from Khalil’s setting.Source: EC.2.4. Proof of Lemma EC.3 · p. 57

EC.3. Two Examples of Networks … EC.5.5. Proof of Lemma 3

This section develops numerical and stylized network examples alongside a fluid-based analysis of perfect availability. It characterizes feasibility through linear programming and proves supporting convergence, infeasibility, and uniqueness results.

EC.3. Two Examples of Networks

EC.3.1. 9-Region Didi Network

  • The analysis focuses on a nine-region network of “major” regions, restricts data to 5–6pm daily, and estimates P from ride counts between regions normalized by origin totals.Source: EC.3.1. 9-Region Didi Network · pp. 57–58

EC.3.2. 5-Region Network

  • The five-region city model comprises downtown, midtown, and three suburbs, with time-varying parameters representing evening flows from downtown to suburbs, then toward midtown and back to suburbs.The model specifies mean travel times in hours and passenger-arrival rates per hour per car.Source: EC.3.2. 5-Region Network · pp. 59–61

EC.4. Achieving 100% Availability Globally

  • The global-availability section asks how many cars are needed for 100% availability in every region when demand may exceed system capacity under any routing policy.It addresses this question using the fluid-based optimization problem.Source: EC.4. Achieving 100% Availability… · p. 61
  • Scaling the fleet by κ is equivalent to dividing per-car passenger arrival rates λ_i by κ, framing availability feasibility as a supply–demand balance.The associated fluid optimization replaces λ_i with λ_i/κ when the fleet contains κN cars.Source: EC.4. Achieving 100% Availability… · p. 62

Appendix EC.4.1.

  • Theorem EC.2 characterizes perfect availability using a linear program: κ>1 requires reducing λ to λ/κ, whereas κ≤1 permits perfect availability.κ is the minimal fluid mass needed for perfect availability and measures supply–demand imbalance.Source: Appendix EC.4.1 · pp. 62–63

EC.4.1. Proof of Theorem EC.2

  • Under the triangle-inequality assumption, an optimal routing solution can be chosen with strictly positive relevant flows, using small empty-car redirections without increasing the objective.The proof redirects empty cars between regions while preserving feasibility and objective optimality.Source: Appendix EC.4.1 · p. 63, EC.4.1. Proof of Theorem EC.2 · pp. 64–65

EC.5.1. Proof of Lemma 1

  • Lemma 1 shows that variables satisfying constraints (10a)–(10g) correspond to a routing matrix q satisfying the fluid constraints (4b)–(4g), and conversely.The converse construction defines q from the flow variables and uses nonnegativity and normalization conditions.Source: EC.5.1. Proof of Lemma 1 · pp. 65–66

EC.5.2. Proof of Lemma 2

  • Lemma 2 constructs a feasible solution satisfying (10a)–(10f) that is better than the purported optimizer, contradicting optimality when the stated positive self-flow condition holds.Source: EC.5.2. Proof of Lemma 2 · pp. 66–67

EC.5.3. Proof of Theorem 1

  • Stationary scaled states have subsequences converging weakly to probability measures supported entirely on the fluid equilibrium set E.The argument uses tightness on the compact set T, weak convergence to a fluid model, and convergence of that model to E.Source: EC.5.3. Proof of Theorem 1 · pp. 68–69

EC.5.4. Proof of Theorem 2

  • The optimization performance measures are feasible, but no finite-car CTMC routing policy can attain the optimum, making the inequality strict.Finite positive recurrence gives every state positive stationary mass, which prevents the performance measures from satisfying the optimal solution’s required conditions; part (b) follows from Theorem 1 with Q = q∗.Source: EC.5.4. Proof of Theorem 2 · pp. 69–70

EC.5.5. Proof of Lemma 3

  • When Pij > 0 and Qii > 0, B is column stochastic and irreducible, and (EC.74) has a unique solution up to a multiplicative constant, ca∗.B can be interpreted as a discrete-time Markov-chain transition matrix for car decisions as if travel times were zero.Source: EC.5.5. Proof of Lemma 3 · p. 72
Loading 1609.07219v4…