# Large-scale analysis of load-balancing policies for free-floating car-sharing models

Christine Fricker, Hanene Mohamed, Alessia Rigonat

► To cite this version:

Christine Fricker, Hanene Mohamed, Alessia Rigonat. Large-scale analysis of load-balancing policies for free-floating car-sharing models. IFIP WG 7.3 Performance 2025 conference: 43rd International Symposium on Computer Performance, Modeling, Measurements and Evaluation, Rob van der Mei and Sandjai Bhulai, Nov 2025, Amsterdam, Netherlands. hal-05533784

HAL Id: hal-05533784

https://hal.science/hal-05533784v1

Submitted on 2 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Large-scale analysis of load-balancing policies for free-floating car-sharing models

Christine Fricker

INRIA Paris, DI-ENS

christine.fricker@inria.fr

Hanene Mohamed

MODAL'X, Université Paris

Nanterre

hmohamed@parisnanterre.fr

Alessia Rigonat

INRIA Paris, DI-ENS

alessia.rigonat@inria.fr

## ABSTRACT

In *free-floating* (FF) car-sharing systems, FF cars share parking spaces in public space with much more numerous private cars. The system is modelled as a closed queuing network with two classes of customers, FF and private cars, with different orders of magnitude. They move between *N* nodes, each with a large capacity *CN*, *C* > 0.

Mean-field techniques are adapted to the presence of private cars, which act as a fast-varying random environment. This allows us to study the impact of load-balancing policies on the distribution of the number of FF cars per zone when the system gets large. For two load-balancing policies, respectively modifying the routing probabilities and the pick-up rates, we obtain an explicit distribution, a binomial negative distribution driven by a fixed point equation. The influence of parameters on performance is derived.

## 1. INTRODUCTION

*Context.* Free-floating (FF) car-sharing systems are becoming increasingly popular as an alternative means of transport that is both environmentally friendly and cost-effective. These car-sharing systems do not require physical stations. FF cars share public space with the more numerous private cars. Few studies take into account this sharing of capacity between private and FF cars. Indeed, by dividing the service area into small zones, from 0.25 km² to 1 km², acting as stations [5], transport research often assimilates FF car sharing to a classical model based on stations with arbitrarily fixed capacities.

*Model.* The stochastic model presented here is specific to FF. It involves a closed system of $M_N$ FF cars and $L_N$ private cars moving according to two different Markov dynamics between *N* zones. Each zone has a large capacity *CN*, *C* > 0. Private cars are assumed to be more numerous than FF cars, so that $M_N$ is of the order of *N* while $L_N$ is of the order of $N^2$. For further discussion on the orders of magnitude, see Appendix A. Travel times for both types of cars follow exponential distributions, while routing is different: uniform for private cars and weighted for FF cars. This modeling is flexible enough to take into account balancing policies based on the number of FF cars available in each zone.

*Aim of the paper.* This paper studies the impact of load-balancing policies on the distribution of the number of FF cars per zone when the system is large. For the application, the objective is to have one FF car per zone. In particular, two incentive policies are considered, aimed at better distributing FF cars and improving their availability. The first policy has repulsive routing (RR) rates, which discourage users from parking their cars in zones close to saturation. The second presents adaptive pick-up (AP), which adapts the pick-up rates to the number of FF cars parked locally.

*Results.* The large-scale analysis of our model with load-balancing policies gives that the lack of parking spaces is independent of the presence of free-floating cars. The limiting invariant distribution of the number of FF cars per zone is derived in Theorem 3.1. The analysis uses mean-field techniques, adapted to the presence of private cars which act as a random environment for FF cars. For the RR and AP policies, this limiting distribution is explicit. It is a negative binomial distribution with a parameter driven by a fixed point equation. This is a generalization of the geometric distribution of the zero-incentive case.

The impact of each of the two policies on system performance is studied. We prove that the performance is a decreasing function of the fleet size parameter. This allows us to quantify the minimum fleet size required to attain a given performance threshold, in terms of the strength of the load-balancing policies. Qualitatively, when the strength of repulsion in the RR policy or that of adaptivity in the AP policy increases, the fleet size that guarantees a certain performance becomes smaller. Moreover, both policies exhibit a significant performance improvement when transitioning from zero-incentives to low-incentives dynamics, after which the gains become progressively smaller.

*Related work.* From a queuing point of view, the model proposed here is a network with two classes of customers with two different orders of magnitude. This model is suited to FF and close to the one introduced in [3] and analyzed in [2] where FF car routing is uniform among the *N* zones and private cars arrive and leave every zone independently, without moving between zones. Thus, the asymptotic behavior of the system is that of $N M/M/CN/CN$ queues of class-2 customers (private cars), disrupted by the presence of a small number of class-1 customers (FF cars) moving between *N* nodes (zones) as a closed system. From the point of view of FF cars, competition with private cars to share the capacity of each zone creates a random environment that varies rapidly due to the numerical imbalance between FF and private cars. In [2], it is shown that the operator has
no control over the lack of parking spaces, but only over the availability of FF cars. Dynamic pricing can be used to better distribute FF cars in the service area. In [7], it is shown that even small differences in pricing by a simple adaptive algorithm can affect demand or routing. Dynamic pricing therefore seems a promising way for the operator for rebalancing based on incentive policies.

Beyond shared mobility, load-balancing is a main topic in stochastic networks with a huge literature. However, most papers concern parallel queues rather than closed systems. It consists in schemes like d-choice from [9], Power-of-2 from [6], Join-the-shortest-queue (JSQ), Join-the-idle-queue (JIQ), etc. Our load-balancing policies are closer to the dynamics introduced by Spitzer in [8], in the context of interacting particle systems, where the jump rates depend only on the state of the departure site (zero range).

## 2. MODEL DESCRIPTION

The model considered in this paper is a system with two classes of customers that move between $N$ nodes, each with capacity $CN$, for $C \in \mathbb{N}^*$. The total numbers of class-1 customers (FF cars) and class-2 customers (private cars) are, respectively, $M_N$ and $L_N$. We assume

$$ \lim_{N \to \infty} \frac{M_N}{N} = s > 0 \quad \text{and} \quad \lim_{N \to \infty} \frac{L_N}{N^2} = w > 0, $$

where the parameter $s$ is called the fleet size parameter. In the following $w_N \stackrel{def}{=} L_N/N^2$. Therefore, the two classes of customers have different orders of magnitude with respect to the scaling parameter $N$. This reflects the fact that in the real world, private cars outnumber FF cars.

The dynamics of the model are described as follows.

* There is a single server in each node for class-1 customers. Service times at node $i$ have exponential distribution with parameter $\lambda(v_i)$, where $\lambda: \mathbb{N} \to \mathbb{R}^+$ is a bounded increasing function, and $v_i$ is the number of class-1 customers at node $i$. At service completion, the class-1 customer leaves the node and starts a switch-over time. Service times represent user inter-arrival times in the zone.

* The switch-over time has exponential distribution with parameter $\mu$. At the end of the switch-over, the customer of class-1 chooses the next node, say node $j$, according to probability $P_j(v) = p(v_j)/\sum_{l=1}^N p(v_l)$, where $p: \mathbb{N} \to \mathbb{R}^+$ is a decreasing function and

$$ \exists C > 0, \quad 1/C \le \frac{\min_{k \ge 0} p(k)}{\max_{k \ge 0} p(k)} \le C. \quad (1) $$

If the customer does not find an available slot at node $j$, they start a new switch-over time with exponential distribution with the same parameter $\mu$. Then they choose a node according to probability $P(v)$, and repeat the process until they find an available slot.

* Once they join a node, class-2 customers are immediately served. The service times have an exponential distribution with parameter $\beta$.

* The switch-over time of class-2 customers has exponential distribution with parameter $\alpha$. At the end of the switch-over, the customer of class 2 chooses the next node to visit with uniform probability $1/N$. For

<figure><img src="image_2.png" /><figcaption>Figure 1: The system with $N$ nodes of capacity $CN$ connected to the $(N+1)$-th central node. Two classes of customers: FF cars $V$ and private cars $X$.</figcaption></figure>

class-2 customers, saturation is managed in the same way as for class-1 customers.

* All inter-arrival times, service times and switch-over times are independent.

The system can be seen as a generalization of a closed Jackson network with $N+1$ nodes and two classes of customers. The $(N+1)$-th node has infinite capacity, it represents the route containing all cars in circulation (see Figure 1).

## 3. MARKOV PROCESS

For $i = 1, ..., N$, let us denote by $m_i^N(t)$ the number of available slots, $V_i^N(t)$ the number of class-1 customers and $X_i^N(t)$ the number of class-2 customers, at node $i$, at time $t$. Note that, for $i = 1...N$ and $t \ge 0$, the relation

$$ m_i^N(t) + V_i^N(t) + X_i^N(t) = CN $$

holds. Thus $X^N(t)$ can be omitted and the state of the system is described by the process

$$ (m^N(t), V^N(t)) = ((m_i^N(t), V_i^N(t)))_{1 \le i \le N}, $$

which is a Markov process on the state space $S^N$ defined as the set of $(m, v) \in \mathbb{N}^{2N}$ with the following constraints

$$ m_i + v_i \le CN, \sum_{k=1}^{N} v_k \le M_N, \sum_{k=1}^{N} (CN - m_k - v_k) \le L_N. $$

The transitions of this Markov process modify only the state of one node at a time. The transition rates for node $i$ are, from state $(m, v) = (m_i, v_i)_{1 \le i \le N}$ to

$$ (m, v) + \begin{cases} -e_i + f_i & \mathbb{1}_{\{m_i > 0\}} \mu(M_N - \sum_{l=1}^N v_l)P_i(v) \\ +e_i - f_i & \lambda(v_i) \mathbb{1}_{\{v_i > 0\}} \\ +e_i & \beta(CN - m_i - v_i) \\ -e_i & \mathbb{1}_{\{m_i > 0\}} \alpha \left(L_N - \sum_{k=1}^N (CN - m_k - v_k)\right)/N, \end{cases} $$

where $(e_i, f_i)_{1 \le i \le N}$ is the canonical basis of $\mathbb{R}^{2N}$.

### 3.1 Preliminary results

The following lemma gives a coupling between the process of available slots and a birth-and-death process, which will be useful to prove convergence results. For this, we assume that $\lambda$ is a bounded function on $\mathbb{N}$.
**LEMMA 3.1 (COUPLING).** Assume $w > C$. For any $\beta_0 > \beta$, any $w_0$ such that $C < w_0 < w$ and $N$ large enough, for $i = 1, \dots, N$, there exists a coupling between process $(m_i^N(t))$ and $(L_m^i(Nt))$, where $(L_m^i(t))$ is the number of customers in a $M/M/1$ queue with arrival rate $\beta_0 C$ and service rate $\alpha(w_0 - C)$, such that

$$L_m^i(0) = m_i^N(0), \quad m_i^N(t) \le L_m^i(Nt), \quad t \ge 0. \quad (2)$$

See Appendix for the proof. The following proposition gives that, under some condition on the parameters, $(m_i^N(t))$ at scale $Nt$ is negligible compared to $N$ for every starting state of the system. Its limit will be specified by Theorem 3.1.

**PROPOSITION 3.1 (MAGNITUDE OF AVAILABLE SLOTS).** Assume $\beta C < \alpha(w - C)$ and let $1 \le i \le N$ be fixed. The process $(m_i^N(Nt)/N)$ converges in distribution to (0).

**PROOF.** It is sufficient to construct the previous coupling of Lemma 3.1 and to apply Lemma A.1. $\square$

## 3.2 Mean-field analysis

Let us denote by $(\Lambda^N(t))$ the empirical measure process of the state process $(m^N(t), V^N(t))$, i.e.

$$\Lambda^N(t) = \frac{1}{N} \sum_{i=1}^{N} \delta_{(m_i^N(t), V_i^N(t))}. \quad (3)$$

The objective is to analyse the behavior of the state process through the evolution equation (21) of the empirical measure process, written in the Appendix. From the transition rates, using assumption (1), which implies easily that $P_i(v)$ is of order $1/N$, it holds that, for any $i$, process $(m_i^N(t))$ is fast with respect to the scaling parameter $N$ compared to the process $(V_i^N(t))$. Therefore, intuitively, for large values of $N$, the indicator function $\mathbb{1}_{\{m_i^N(t)>0\}}$ behaves like the stationary probability that the number of available slots is non-zero. This reflects the stochastic averaging principle. Based on this limiting probability, independent of $i$ by homogeneity, two regimes can be identified:

* If this limiting probability is equal to one, the system is said to be in the underloaded regime, and there is no saturation in the nodes.

* Otherwise, it is in the overloaded regime.

In the following, we study the overloaded regime, more interesting from a theoretical and a practical point of view.

**DEFINITION 3.1 (OCCUPATION MEASURE).** For a non-negative Borelian function $g$ with compact support on $\mathbb{R}_+ \times \mathbb{N}^2$, the occupation measure $\mu_N$ is defined by

$$\langle \mu_N, g \rangle = \frac{1}{N} \sum_{i=1}^{N} \int_{\mathbb{R}_+} g(u, m_i^N(Nu), V_i^N(Nu)) du. \quad (4)$$

The next theorem is the main result of the paper. It describes the long-time behavior of a large system in the overloaded regime.

**THEOREM 3.1.** Assume $\beta C < \alpha(w - C)$. The sequence of occupation measures $(\mu_N)$ on state space $\mathbb{R}_+ \times \mathbb{N}^2$ defined by equation (4) is tight. Moreover, for the weak convergence, any limiting point $\mu_\infty$ satisfies

$$\langle \mu_\infty, g \rangle = \int_{\mathbb{R}_+} \mathbb{E}[g(u, X_1, X_2)] du \quad (5)$$

for any function $g$ with finite support on $\mathbb{R}^+ \times \mathbb{N}^2$, where $X_1$ and $X_2$ are independent random variables such that

* $X_1$ has a geometric distribution on $\mathbb{N}$, with parameter $\beta C/\alpha(w - C)$,

* the distribution $\pi_2$ of $X_2$ is related to the choice of the load-balancing policy and is solution to the fixed point equation,

$$\pi_2(k) = \pi_2(0) \left( \frac{\mu\beta C}{\alpha(w-C)} \frac{s - \int_{\mathbb{N}} v \pi_2(dv)}{\int_{\mathbb{N}} p(v) \pi_2(dv)} \prod_{i=1}^{k} \frac{p(i-1)}{\lambda(i)} \right), \quad (6)$$
$$\text{for } k \in \mathbb{N}_+.$$

To prove Theorem 3.1 we adapt the proof of [2, Theorem 2] to our framework. See Appendix for the key arguments.

**REMARK 1.** The limiting number of available slots per zone $X_1$ does not depend on the FF cars parameters. As in [2] without incentives, this is due to the negligible order of magnitude of FF cars compared to private cars.

## 4. LOAD-BALANCING POLICIES

In this section, we focus on two examples of policies where the limiting distribution $\pi_2$ (see Theorem 3.1) of the number of FF cars per zone can be computed explicitly. The two policies act at two times: at car drop-off and at car pick-up.

* **Repulsive routing (RR) policy:** it discourages users to park their FF car in zones with many FF cars;

* **Adaptive pick-up (AP) policy:** it adapts the pick-up rate in a zone to the number of FF cars parked there.

For $r \in \mathbb{N}^+$ and $\rho \in (0, 1)$, let us denote by $\pi_{r,\rho}$ the Negative Binomial distribution with parameters $r$ and $\rho$, given, for $k \in \mathbb{N}$, by

$$\pi_{r,\rho}(k) = (1-\rho)^r \rho^k \binom{k+r-1}{k},$$

and let us introduce the following notation

$$A = \frac{\mu\beta C}{\lambda\alpha(w-C)}. \quad (7)$$

### 4.1 Repulsive routing (RR) policy

The following proposition gives the limiting distribution $\pi_2$ for a particular choice of routing function $p: \mathbb{N} \mapsto \mathbb{R}_+$, while the departure rate $\lambda(k) = \lambda > 0$ is fixed.

**PROPOSITION 4.1.** Let us assume $\beta C < \alpha(w - C)$ and $\lambda(k) = \lambda > 0$ for all $k \in \mathbb{N}$. For some parameter $r \in \mathbb{N}^+$, consider a routing mechanism with

$$p_r(k) = 1 + \frac{r-1}{k+1}, \quad k \in \mathbb{N}. \quad (8)$$

Then the distribution $\pi_2$ of the random variable $X_2$ in (5) is the negative binomial distribution with parameters $r$ and $\rho(r)$, unique solution of equation with

$$(1 - \rho)^{r+1} + \rho(1 - As - Ar) = 1 - As. \quad (9)$$
PROOF. Replacing $p(k) = p_r(k)$ and $\lambda(k) = \lambda$ in (6), the equilibrium distribution $\pi_2$ of the number of FF cars is such that, for $k \in \mathbb{N}$,

$$ \pi_2(k) \propto \rho^k \frac{(k+r-1)!}{k!} $$

with

$$ \rho \stackrel{\text{def}}{=} A \frac{s - \int_{\mathbb{N}} v \pi_2(dv)}{\int_{\mathbb{N}} (1 + \frac{r-1}{v+1}) \pi_2(dv)}, \quad (10) $$

thus $\pi_2$ is a negative binomial distribution with parameters $r$ and $\rho$. With straightforward computations of its right-hand side as a function of $\rho$, equation (10) can be rewritten

$$ 1 = A \frac{s - r \frac{\rho}{1-\rho}}{1 - (1-\rho)^r}, \quad (11) $$

if $\rho \in (0, 1]$, which gives (9).

Let us denote by $f$, the function defined for every $\rho \in (0, 1]$, by

$$ f(\rho) = (1 - \rho)^{r+1} + \rho(1 - As - Ar) + As - 1. $$

Since $f$ is continuous in $[0, 1]$, $f(0) = As > 0$ and $f(1) = -Ar < 0$, there exists at least one solution of the fixed-point equation (9). For $\rho \in (0, 1]$,

$$ f''(\rho) = r(r+1)(1-\rho)^{r-1} > 0, $$

thus the solution of (9) is unique. $\square$

**Impact of parameter $r$.** In the routing probability (8), the term $(r-1)/(k+1)$ reflects some discouragement for users to join a zone, inversely proportional to the occupation of this zone by FF cars. The parameter $r$ expresses the level of discouragement that the operator applies to users. When $r=1$ there is no discouragement, the choice is uniform among the nodes. The level of discouragement increases with $r$. More precisely, when $r$ increases, the distribution obtained by renormalizing $p_r(k)$ at all stations becomes more and more concentrated in zones with few or no FF cars. The following proposition states that, when $r$ becomes large, the limiting distribution $\pi_{r,\rho(r)}$ converges to a Poisson distribution. This shows that the mass of the limiting invariant distribution $\pi_{r,\rho(r)}$ becomes increasingly concentrated around the mean (see Figure 2). Recall that the Negative Binomial distribution with parameters $r$ and $\rho$ is denoted by $\pi_{r,\rho}$.

**PROPOSITION 4.2.** For $r=1$, the routing is uniform and $\pi_{1,\rho(1)}$ is a geometric distribution with parameter

$$ \rho(1) = \frac{1}{2} \left( 1 + As + A - \sqrt{(1 + As + A)^2 - 4As} \right). \quad (12) $$

For $r \to \infty$, $\pi_{r,\rho(r)} \xrightarrow{d} \text{Poisson}(\gamma)$, where $\gamma > 0$ is the unique solution to the fixed-point equation

$$ \gamma = s - \frac{1 - e^{-\gamma}}{A}. \quad (13) $$

PROOF. For $r=1$, the system is a Jackson network with $N+1$ nodes. In this case, one gets a geometric distribution $\pi_{1,\rho(1)} = (1-\rho(1))\rho(1)^k$ with explicit parameter $\rho(1)$ given by (12). In order to study the convergence of the limiting distribution $\pi_{r,\rho(r)}$ when $r$ becomes large, let us consider the generating function of a random variable $X_{r,\rho(r)}$ with a

negative binomial distribution $\pi_{r,\rho(r)}$. It is given by

$$ G_{X_{r,\rho(r)}}(u) = \left( \frac{1-\rho(r)}{1-u\rho(r)} \right)^r, \quad |u| < 1. $$

Note that $\lim_{r \to \infty} \rho(r) = 0$. Moreover and that $\lim_{r \to \infty} r\rho(r) = \gamma$ where $\gamma$ is the unique solution to the fixed point equation (13), see Appendix for details. Then

$$ \lim_{r \to \infty} G_{X_{r,\rho(r)}}(u) = e^{\gamma(u-1)}, \quad |u| < 1, $$

which is the generating function of a random variable with a Poisson distribution with parameter $\gamma$. It follows that $X_{r,\rho(r)}$ converges in distribution, when $r$ becomes large, to a random variable $X$ with a Poisson distribution with parameter $\gamma$ (see Figure 2). $\square$

<figure><img src="image_3.png" /><figcaption>Figure 2: Plot, for the RR policy, of the Negative Binomial distribution with parameters $r$ and $\rho(r)$. For large values of $r$, approximation by a Poisson($r\rho(r)$) distribution. $A=2$ and $s=10$.</figcaption></figure>

## 4.2 Adaptive pick-up (AP) policy

In this section, we study the limiting distribution $\pi_2$ for a particular choice of the pick-up rate function $\lambda$, while the routing function is $p(k) = 1$ for all $k \in \mathbb{N}$. The parameter $\rho$ is again derived from a fixed point equation and has an explicit expression.

**PROPOSITION 4.3.** Let us assume $\beta C < \alpha(w-C)$, $p(k) = 1$ for all $k \in \mathbb{N}$, and consider the following pick-up rates for class-1 customers. For $k \in \mathbb{N}$,

$$ \lambda_r(k) = \lambda \left( 1 - \frac{r-1}{k+r-1} \right), $$

for some parameter $r \in \mathbb{N}^+$. Then the distribution $\pi_2$ of the random variable $X_2$ in (5) is a negative binomial distribution with parameters $r$ and $\rho$ where $\rho$ is given by

$$ \rho = \frac{1}{2} \left( As + Ar + 1 - \sqrt{(As + Ar + 1)^2 - 4As} \right). \quad (14) $$

PROOF. Replacing $p(k) = 1$ and $\lambda(k) = \lambda_r(k)$ in (6), the limiting distribution $\pi_2$ is given by

$$ \pi_2(k) = \pi_2(0) A^k \left( s - \int_{\mathbb{N}} v \pi_2(dv) \right)^k \frac{(k+r-1)!}{k!(r-1)!}. $$

This is a negative binomial distribution with parameters $r$
and $\rho$ with

$$ \rho \stackrel{\text{def}}{=} A \left( s - \int_{\mathbb{N}} v \pi_2(dv) \right). \qquad (15) $$

Writing the right-hand side of (15) in terms of $\rho$, the following fixed point equation is derived for $\rho \in (0, 1]$

$$ \rho = A \left( s - r \frac{\rho}{1 - \rho} \right), \qquad (16) $$

rewritten as a second-degree polynomial equation

$$ \rho^2 - \rho(As + Ar + 1) + As = 0, $$

which has two distinct solutions $0 < \rho_- < 1 < \rho_+$. Therefore, there exists a unique value of $\rho \in (0, 1]$, with explicit expression (14), suitable to be the parameter of the negative binomial distribution $\pi_2$. $\square$

REMARK 2. For $r = 1$, the transition rates are the same for both policies. Thus the limiting distribution $\pi_{1,\rho}$ is again a geometric distribution with explicit parameter $\rho = (1 + As + A - \sqrt{(1 + As + A)^2 - 4As})/2$. For the AP policy, studying the convergence of the distribution $\pi_{r,\rho(r)}$ when $r$ becomes large makes no sense. In fact $\lim_{r \to \infty} \lambda_r(k) = 0$ for every $k \in \mathbb{N}$, thus the limiting pick-up rate of cars is 0.

# 5. PERFORMANCE EVALUATION

Users of FF car-sharing systems face the problem of finding available cars and parking spaces throughout the service area. While in the underloaded regime, the limiting proportion of zones without parking spaces is 0, in the overloaded regime the limiting proportion of zones without available parking spaces is $\beta C/\alpha(w - C)$ by Theorem 3.1, and depends only on the parameters of the environment (private cars and characteristics of the zone). Therefore, the car-sharing operator can only act on the limiting probability of finding available FF cars. The following corollary gives straightforwardly an explicit expression for this probability under the RR and the AP policies.

COROLLARY 5.1 (PERFORMANCE). The limiting probability of failure, defined as the stationary probability of absence of FF cars at any zone, is given, for fixed $r$, by

$$ \pi_{r,\rho(r)}(0) = (1 - \rho(r))^r, $$

where $\rho(r) \in (0, 1]$ is the solution to the fixed point equation (9) for the RR policy, and (16) for the AP policy.

As a by-product, the following proposition states that the limiting probability of failure decreases with the fleet size.

PROPOSITION 5.1 (INFLUENCE OF FLEET SIZE). The limiting probability of failure is a decreasing function of $s$.

See Appendix for the proof. As a consequence, given a threshold, say $\varepsilon$, for the limiting probability of failure, one can compute the minimum fleet size $s_\varepsilon$ that assures

$$ \pi_{r,\rho}(0) \le \varepsilon. $$

By simple calculations, the minimum fleet size $s_\varepsilon$ is explicitly given by

$$ s_{\varepsilon}(r) = \begin{cases} \frac{1-\varepsilon}{A} + r \frac{1-\varepsilon^{1/r}}{\varepsilon^{1/r}} & \text{for the RR policy} \\ \frac{1-\varepsilon^{1/r}}{A} + r \frac{1-\varepsilon^{1/r}}{\varepsilon^{1/r}} & \text{for the AP policy.} \end{cases} $$

Note that the difference between the two expressions of the minimum fleet size $s_\varepsilon$ is of the order of $\varepsilon^{1/r}$, which is negligible, for very small thresholds $\varepsilon$ in practice. The parameter $r$ represents the strength of repulsion in the RR policy and that of the adaptivity in the AP policy. For both policies, for a fixed value of $\varepsilon$, the minimum fleet size $s_\varepsilon$ is a decreasing function in $r$. See Figure 3. Figure 3 shows that both policies exhibit a significant performance improvement when increasing the parameter from $r = 1$ to $r = 2$, after which the gains become progressively smaller.

<figure><img src="image_4.png" /><figcaption>Figure 3: Plot of the minimum fleet size $s_\varepsilon = s_\varepsilon(r)$ that guarantees the failure probability to be smaller than $\varepsilon$, for different $\varepsilon$. Increasing the parameter $r$ from $r = 1$ to $r = 2$, $s_{0.01}$ decreases from 100 to less than 20 for both the RR and the AP policies. $A = 5$. The two policies cannot be compared, since the total demand from users is not the same.</figcaption></figure>

# 6. CONCLUSION AND FUTURE WORK

In this paper, we model some load-balancing policies for FF car-sharing systems assuming that the operator can act on the drop-off and pick-up rates of cars. We show that private cars behave as a fast random environment for FF cars. Thus private cars, in addition to the urban characteristics of the service area, determine if the system is in underloaded or overloaded regime.

Adapting mean-field techniques to this framework, we derive the limiting invariant distribution of the number of available spots and of FF cars in any zone of the service area. Explicit expressions for this distribution are obtained for two load-balancing policies: Repulsive Routing (RR) and Adaptive Pick-up (AP). In particular, for both policies, the number of FF cars in a given zone has a negative binomial distribution. We define the failure probability of a FF car-sharing system as the limiting proportion of zones without available FF cars. We show that the probability of failure is a decreasing function of the fleet size parameter $s$. Finally, we compute the minimum fleet size that guarantees that the probability of failure is less than some threshold, as a function of the strength of the incentive policy.

In future work, we will study the influence of incentive policies when the system is not homogeneous. In practice, a natural example is a two-cluster system where the service area is divided into two regions: a high-demand area and a low-demand area. Incentives need to be adapted to the inhomogeneous demand of FF cars.
# ACKNOWLEDGEMENTS

This research benefited from the support of the FMJH Program Gaspard Monge for optimization and operations research and their interactions with data science.

# 7. REFERENCES

[1] S. N. Ethier and T. G. Kurtz. Markov processes: characterization and convergence. John Wiley & Sons, 2009.

[2] C. Fricker, H. Mohamed, and A. Rigonat. Stochastic averaging and mean-field for a large system with fast varying environment with applications to free-floating car-sharing. Accepted to Queueing Systems, 2025.

[3] C. Fricker, H. Mohamed, A. Rigonat, and M. Trépanier. A new stochastic model for carsharing suited to free-floating. Transportation Research Procedia, 82:2395-2409, 2025.

[4] T. G. Kurtz. Averaging for martingale problems and stochastic approximation. In Applied Stochastic Analysis: Proceedings of a US-French Workshop, Rutgers University, New Brunswick, NJ, April 29-May 2, 1991, pages 186-209. Springer, 2005.

[5] K. Lippoldt, T. Niels, and K. Bogenberger. Effectiveness of different incentive models in free-floating carsharing systems: A case study in milan. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pages 1179-1185. IEEE, 2018.

[6] M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE transactions on parallel and distributed systems, 12(10):1094-1104, 2002.

[7] N. Neijmeijer, F. Schulte, K. Tierney, H. Polinder, and R. R. Negenborn. Dynamic pricing for user-based rebalancing in free-floating vehicle sharing: A real-world case. In Computational Logistics: 11th International Conference, ICCL 2020, Enschede, The Netherlands, September 28-30, 2020, Proceedings 11, pages 443-456. Springer, 2020.

[8] F. Spitzer. Interaction of markov processes. In Random Walks, Brownian Motion, and Interacting Particle Systems: A Festschrift in Honor of Frank Spitzer, pages 66-110. Springer, 1991.

[9] N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii, 32(1):20-34, 1996.

# APPENDIX

## A. PRELIMINARIES

**Discussion on the orders of magnitude.** Since the objective for the system is to have one free-floating car per zone, the scaling has been designed so that the fleet size per zone, which is the quantity of interest, is of unit order. We therefore choose the same order of magnitude for the total number of free-floating cars and the number of zones. The number of private cars per zone is proportional to the number of parking spaces per zone, this models well what happens in reality. The choice of having the number of parking spaces per zone (and, therefore, of private cars per zone) of order N is to be in line with Kelly's scaling for loss networks. One could choose other orders of magnitude for this ratio.

**LEMMA A.1 (STABLE M/M/1 QUEUE).** If $L(t)$ is the number of customers in a M/M/1 queue with arrival and service rates respectively $\eta$ and $\nu$ with $\eta < \nu$ then, if $L(0) = 0$, for all $\delta \ge 0$, the process

$$ \left( \frac{L(N^{\delta}t)}{\log^2 N} \right) $$

converges in distribution to (0). In particular, for the convergence in distribution, process

$$ \left( \frac{L(Nt)}{N} \right) $$

converges to (0).

The proof is omitted. See [2].

## B. PROOFS OF SECTION 3

**PROOF OF LEMMA 3.1.** We can construct a coupling $(m_i^N(t), L_m^i(Nt))$ where $(L_m^i(t))$ is the number of customers in a $M/M/1$ queue with arrival rate $\eta$ and service rate $\nu$ and $L_m^i(0) = m_i^N(0)$, where $\eta$ and $\nu$ are properly chosen such that $\eta < \nu$. If the system is in state $(m, v)$, the jumps and the respective rates of process $(m_i^N(t))$ are

$$ \left\{ \begin{array}{ll} -1 & \left( \alpha N \left( w_N - C + \sum_{l=1}^{N} (m_l + v_l)/N \right) + \mu \left( M_N - \sum_{l=1}^{N} v_l \right) P_i(v) \right) \mathbb{1}_{m_i>0}, \\ +1 & \beta(CN - m_i - v_i) + \lambda(v_i) \mathbb{1}_{v_i>0}. \end{array} \right. $$

The rate for jump $-1$ is larger than $\alpha N(w_N - C) \mathbb{1}_{m_i>0}$ and the rate for jump $+1$ is smaller than $\beta CN + \lambda(v_i)$. Recall that the function $\lambda$ is bounded, thus for any fixed $\beta_0 > \beta$, $w_0 < w$ and $N$ large enough, $\beta CN + \lambda(v_i) < \beta_0 CN$ and $\alpha N(w_N - C) \mathbb{1}_{m_i>0} > \alpha N(w_0 - C) \mathbb{1}_{m_i>0}$. Choosing therefore $\eta = \beta_0 C$ and $\nu = \alpha(w_0 - C)$, $(L_m^i(t))$ is the birth and death process with transitions

$$ k \to k + \begin{cases} -1 & \alpha(w_0 - C) \mathbb{1}_{\{k>0\}} \\ +1 & \beta_0 C \end{cases} $$

thus equation (2) holds for $N$ large enough. $\square$

The following lemma is part of the proof of Theorem 3.1.
**LEMMA B.1.** Assume $\beta C < \alpha(w - C)$. The sequence of occupation measures $(\mu_N)$ on state space $\mathbb{R}_+ \times \mathbb{N}^2$ is tight and, for the weak convergence of measures, any limiting point $\mu_\infty$ can be expressed as

$$ \langle \mu_\infty, g \rangle = \int_{\mathbb{R}_+ \times \mathbb{N}^2} g(u, m, v) \pi_u (dm, dv) du \quad (17) $$

for any non-negative Borelian function $g$ on $\mathbb{R}_+ \times \mathbb{N}^2$, where $\pi_u$ is a probability measure on $\mathbb{N}^2$.

**PROOF OF LEMMA B.1.** First, let us prove that for fixed $\varepsilon > 0$, there exists $K_0 > 0$ such that for $K \ge K_0$, $K \in \mathbb{N}$, for every $N \in \mathbb{N}$ and $t \ge 0$,

$$ \mathbb{E}(\mu_N([0, t] \times \mathbb{N} \times [K, +\infty])) < \varepsilon t/2. \quad (18) $$

Using Markov inequality, by definition (4) of $\mu_N$, it holds that

$$ \begin{aligned} \mathbb{E}[\mu_N([0, t] \times \mathbb{N} \times [K, +\infty])] &= \frac{1}{N} \sum_{i=1}^{N} \int_{0}^{t} \mathbb{P}(V_i^N(Nu) \ge K) du \\ &\le \frac{1}{N} \sum_{i=1}^{N} \int_{0}^{t} \mathbb{E} \left( \frac{V_i^N(Nu)}{K} \right) du \\ &\le \frac{1}{N} \int_{0}^{t} \frac{M_N}{K} du = \frac{t M_N}{N K}. \end{aligned} $$

Using that $\lim_{N \to \infty} M_N/N = s$, we get

$$ \limsup_{N \to \infty} \mathbb{E}[\mu_N([0, t] \times \mathbb{N} \times [K, +\infty))] \le \frac{ts}{K}. $$

Thus, there exists $K_1$ and $N_0$ such that, for $N \ge N_0$ and $K \ge K_1$, equation (18) holds. One can then choose $K_2$ such that, for $N < N_0$ and $K \ge K_2$, equation (18) holds. Therefore equation (18) holds for $K \ge K_0 = \sup(K_1, K_2)$ and uniformly in $N$.

Second, let us prove that for fixed $\varepsilon > 0$, there exists $\tilde{K}_0$ such that for any $K \ge \tilde{K}_0$, $K \in \mathbb{N}$, for any $N \in \mathbb{N}$ and $t \ge 0$,

$$ \mathbb{E}(\mu_N([0, t] \times [K, +\infty[ \times \mathbb{N})) < \varepsilon t/2. \quad (19) $$

Using the coupling $(m_i(t), L_m^i(Nt))$ of Lemma 3.1, with $L_m^i(Nt)$ the number of customers in a $M/M/1$ with arrival rate $\beta_0 C$ and service rate $\alpha(w_0 - C)$ for all $\beta_0 > \beta$ and $w_0 < w$, relation $m_i^N(Nt) \le L_m^i(N^2t)$ holds for all $t \ge 0$ and $N$ large enough. This yields

$$ \begin{aligned} \mathbb{E}[\mu_N([0, t] \times [K, +\infty[ \times \mathbb{N}]) &= \frac{1}{N} \sum_{i=1}^{N} \int_{0}^{t} \mathbb{P}(m_i^N(Nu) \ge K) du \\ &\le \frac{1}{N} \sum_{i=1}^{N} \int_{0}^{t} \mathbb{P}(L_m^i(N^2u) \ge K) du \\ &\le \frac{1}{N} \sum_{i=1}^{N} \frac{1}{N^2} \int_{0}^{N^2t} \mathbb{P}(L_m^i(u) \ge K) du \end{aligned} $$

and, by ergodic theorem,

$$ \limsup_{N \to \infty} \mathbb{E}[\mu_N([0, t] \times [K, +\infty[ \times \mathbb{N}]) \le \left( \frac{\beta_0 C}{\alpha(w_0 - C)} \right)^K t $$

for all $\beta_0 > \beta$ and $w_0 < w$. Choosing $\beta_0$ and $w_0$ such that $\beta_0 C < \alpha(w_0 - C)$, it is thus sufficient to choose $K$ large enough to obtain (19) for $N$ sufficiently large. It is then easy to check that (19) holds uniformly in $N$, choosing $K$ sufficiently large.

From equations (18) and (19), for $t \ge 0$ and $\varepsilon > 0$ fixed, there exist $\tilde{K}_0$ such that for any $K \ge \tilde{K}_0$, $K \in \mathbb{N}$,

$$ \inf_N \mathbb{E}(\mu_N([0, t] \times [0, K]^2)) \ge (1 - \varepsilon)t. $$

Thus, since it is tight, the sequence $(\mu_N)$ is relatively compact, due to [4, Lemma 1.3], which is a consequence of Prohorov's theorem (see also [1, Theorem 2.2]). Moreover [4, Lemma 1.4] gives that any limiting point $\mu_\infty$ of this sequence can be represented as in equation (17). $\square$

**PROOF OF THEOREM 3.1.** We just give a sketch of the proof. See analogous details in the proof of [2, Theorem 2]. The main idea is that an averaging principle holds with a fast process and a slow process. The general method for this is described in Kurtz [4].

From the definition of the empirical measure (3), for any function $f$ with finite support on $\mathbb{N}^2$ and $t \ge 0$,

$$ \Lambda^N(t)(f) = \frac{1}{N} \sum_{i=1}^{N} f(m_i^N(t), V_i^N(t)), $$

used in the following in this form

$$ \Lambda^N(t)(f) = \int_{\mathbb{N}^2} f(m, v) \Lambda^N(t)(dm, dv). $$

Let us introduce, for $(m, v) \in \mathbb{N}^{2N}$ and $(i, j) \in \mathbb{N}^2$, the following notation

$$ \Delta_{i,j}(f)(m, v) = f(m + i, v + j) - f(m, v). \quad (20) $$

The functional evolution equation for the empirical measure process is

$$ \begin{aligned} \Lambda^N(t)(f) = \Lambda^N(0)(f) &+ \int_0^t \int_{\mathbb{N}^2} \Delta_{(1,-1)}(f)(m, v) \lambda(v) \mathbb{1}_{\{v>0\}} \Lambda^N(s)(dm, dv) ds \\ &+ \mu \int_0^t \frac{\frac{M_N}{N} - \int_{\mathbb{N}^2} v \Lambda^N(s)(dm, dv)}{\int_{\mathbb{N}^2} p(v) \Lambda^N(s)(dm, dv)} \int_{\mathbb{N}^2} p(v) \Delta_{(-1,1)}(f)(m, v) \mathbb{1}_{\{m>0\}} \Lambda^N(s)(dm, dv) ds \\ &+ \beta C N \int_0^t \int_{\mathbb{N}^2} \Delta_{(1,0)}(f)(m, v) \Lambda^N(s)(dm, dv) ds \\ &- \beta \int_0^t \int_{\mathbb{N}^2} (m + v) \Delta_{(1,0)}(f)(m, v) \Lambda^N(s)(dm, dv) ds \\ &+ \alpha N (w_N - C) \int_0^t \int_{\mathbb{N}^2} \Delta_{(-1,0)}(f)(m, v) \mathbb{1}_{\{m>0\}} \Lambda^N(s)(dm, dv) ds \\ &+ \alpha \int_{\mathbb{N}^2} (m + v) \Lambda^N(s)(dm, dv) \int_0^t \int_{\mathbb{N}^2} \Delta_{(1,0)}(f)(m, v) \Lambda^N(s)(dm, dv) ds \\ &+ \frac{1}{N} \sum_{i=1}^N M_{i,f}^N(t) \end{aligned} \quad (21) $$

where $(M_{i,f}^N(t))$ are square integrable martingales.

Let us choose $f(m, v) = h(m)k(v)$, replace $t$ by $Nt$ and divide by $N^2$ in equation (21). It easy to check that the
martingale term

$$ \left( \frac{M_f^N (Nt)}{N^2} \right) = \left( \frac{1}{N^3} \sum_{i=1}^N M_{i,f}^N (Nt) \right) $$

converges to (0) as $N \to \infty$, together with some of the integral terms. For the remaining terms, Lemma B.1 gives that, when $N \to \infty$,

$$ 0 = \int_0^t \int_{\mathbb{N}^2} k(v) \left( \beta C \Delta_1(h)(m) + \alpha(w-C) \Delta_{-1}(h)(m) \mathbb{1}_{m>0} \right) \pi_u (dm, dv) du, $$

for all $t \ge 0$. Note that assumption (1) is used to prove that the third term in the right-hand side of (21) converges to 0. Let $\pi_t(dm|v)$ be the conditional distribution of $m$ given $v$, and $\pi_{2,t}(dv)$ the marginal distribution of $v$. For almost all $t \ge 0$,

$$ \int_{\mathbb{N}} (\beta C \Delta_1(h)(m) + \alpha(w-C) \Delta_{-1}(h)(m) \mathbb{1}_{m>0}) \pi_t(dm|v) = 0, $$

$\pi_{2,t}(dv)$ almost surely for all functions $h$ with finite support on $\mathbb{N}$. We recognize the integral of the infinitesimal generator of a $M/M/1$ queue with arrival rate $\beta C$ and service rate $\alpha(w-C)$ with $\beta C < \alpha(w-C)$, therefore $\pi_t(dm|v)$ is a geometric distribution with parameter $\beta C/\alpha(w-C)$ for all $v \ge 0$. In particular $\pi_t(dm|v)$ is independent of $v$, thus $\pi_t(dm|v) = \pi_{1,t}(dm)$ and

$$ \int_{\mathbb{N}} \mathbb{1}_{m>0} \pi_t (dm|dv) = 1 - \pi_{1,t}(0) = \frac{\beta C}{\alpha(w-C)}. \quad (22) $$

Choosing then $f(m, v) = k(v)$, replacing $t$ by $Nt$ in (21), and dividing it by $N$, it holds that

$$ \begin{aligned} \frac{\Lambda^N(Nt)(f)}{N} = \frac{\Lambda^N(0)(f)}{N} &+ \int_0^t \int_{\mathbb{N}^2} \Delta_{-1}(k)(v) \mathbb{1}_{\{v>0\}} \lambda(v) \Lambda^N(Nu)(dm, dv) du \\ &+ \mu \int_0^t \frac{\frac{M_N}{N} - \int_{\mathbb{N}^2} v \Lambda^N(u)(dm, dv)}{\int_{\mathbb{N}^2} p(v) \Lambda^N(u)(dm, dv)} \int_{\mathbb{N}^2} \Delta_1(k)(v) \mathbb{1}_{\{m>0\}} p(v) \Lambda^N(Nu)(dm, dv) du \\ &+ \frac{1}{N^2} \sum_{i=1}^N M_{i,k}^N(Nt). \end{aligned} \quad (23) $$

Letting $N \to \infty$, the martingale term and the left-hand side of equation (23) converge to 0. Then Lemma B.1 gives that

$$ 0 = \int_0^t \int_{\mathbb{N}^2} \left( \lambda(v) \Delta_{-1}(k)(v) \mathbb{1}_{v>0} + \mu \frac{s - \int_{\mathbb{N}} v \pi_2(dv)}{\int_{\mathbb{N}} p(v) \pi_2(dv)} \Delta_1(k)(v) \mathbb{1}_{m>0} p(v) \right) \pi_u (dm, dv) du. $$

Conditioning by $m$ and using (22), we get

$$ 0 = \int_0^t \int_{\mathbb{N}} \left( \lambda(v) \Delta_{-1}(k)(v) \mathbb{1}_{v>0} + \mu \frac{\beta C}{\alpha(w-C)} \frac{s - \int_{\mathbb{N}} v \pi_2(dv)}{\int_{\mathbb{N}} p(v) \pi_2(dv)} \Delta_1(k)(v) p(v) \right) \pi_{2,u}(dv) du. $$

Therefore, for almost all $t \ge 0$,

$$ 0 = \int_{\mathbb{N}} \left( \lambda(v) \Delta_{-1}(k)(v) \mathbb{1}_{v>0} + \frac{\mu \beta C}{\alpha(w-C)} \frac{s - \int_{\mathbb{N}} v \pi_2(dv)}{\int_{\mathbb{N}} p(v) \pi_2(dv)} \Delta_1(k)(v) p(v) \right) \pi_2(dv). \quad (24) $$

In the right-hand side of equation (24) is the generator of a birth-and-death process that, when in state $n \in \mathbb{N}$, has birth rate

$$ \mu \frac{\beta C}{\alpha(w-C)} \frac{s - \int_{\mathbb{N}} v \pi_2(dv)}{\int_{\mathbb{N}} p(v) \pi_2(dv)} p(n), $$

and death rate $\lambda(n)$.

The marginal distribution $\pi_2$ has therefore the following expression. For $k \in \mathbb{N}^+$

$$ \pi_2(k) = \pi_2(0) \prod_{i=1}^{k} \left( \mu \frac{\beta C}{\alpha(w-C)} \frac{s - \int_{\mathbb{N}} v \pi_2(dv)}{\int_{\mathbb{N}} p(v) \pi_2(dv)} \frac{p(i-1)}{\lambda(i)} \right) $$

which gives straightforwardly (6). The existence of such $\pi_2$ is guaranteed by lemma B.1.

<figure><img src="image_5.png" /></figure>

### C. PROOF OF SECTION 4

**PROOF OF PROPOSITION 4.2.** Let us detail in this proof that $\lim_{r \to \infty} r\rho(r) = \gamma$. Using (11), we obtain straightforwardly that $r\rho(r) < s$. Thus, for any sequence $(r_n)_n$ converging to infinity, $(r_n\rho(r_n))_n$ is bounded and therefore admits at least one limiting point. Then, rewriting the second term of the left-hand side of (9) as $r\rho(1/r - As/r - A)$, any limiting point satisfies (13). And $\gamma \mapsto 1 - \exp(-\gamma) - A\gamma$ is continuous and non-decreasing from 0 to $+\infty$. Therefore, for fixed $s > 0$, there is a unique $\gamma$ solution of (13). $\square$

### D. PROOF OF SECTION 5

**PROOF OF PROPOSITION 5.1.** Let us denote by $\varphi(\rho) = \pi_{r,\rho(r)}(0) = (1-\rho)^r$ the limiting probability of failure as a function of $\rho$. Then $\pi_{r,\rho(r)}(0)$ as a function of $s$ is given by $\psi = \varphi \circ s^{-1}$ and its derivative by $\psi' = (\varphi' \circ s^{-1}) / (s' \circ s^{-1})$. Differentiating function $\varphi$ with respect to $\rho$ gives $\varphi'(\rho) = -r(1-\rho)^{r-1} < 0$. For the RR policy, for every $\rho \in [0,1)$, the fleet size as a function of $\rho$ is given by

$$ s(\rho) = \frac{1}{A(1-\rho)} \left(1 - (1-\rho)^{r+1} - \rho(1-A\rho)\right), $$

and its derivative by

$$ s'(\rho) = \frac{r(A + (1-\rho)^{r+1})}{A(1-\rho)^2} > 0. $$

For the AP policy, for every $\rho \in [0,1)$, $s(\rho)$ is given by

$$ s(\rho) = \frac{\rho}{A} + r \frac{\rho}{1-\rho} $$

and

$$ s'(\rho) = \frac{1}{A} + \frac{r}{(1-\rho)^2} > 0. $$

Therefore, for both policies, $\psi' < 0$ and we can conclude that $\pi_{r,\rho(r)}(0)$ is a decreasing function of $s$. $\square$