Christine Fricker
email: christine.fricker@inria.fr

Nicolas Gast
email: nicolas.gast@inria.fr.

INCENTIVES AND REDISTRIBUTION IN HOMOGENEOUS BIKE-SHARING SYSTEMS WITH STATIONS OF FINITE CAPACITY

Keywords: Bike-sharing systems, stochastic model, incentives, redistribution mechanisms, mean-field approximation

Bike-sharing systems are becoming important for urban transportation. In such systems, users arrive at a station, take a bike and use it for a while, then return it to another station of their choice. Each station has a finite capacity: it cannot host more bikes than its capacity. We propose a stochastic model of an homogeneous bike-sharing system and study the effect of users random choices on the number of problematic stations, i.e., stations that, at a given time, have no bikes available or no available spots for bikes to be returned to. We quantify the influence of the station capacities, and we compute the fleet size that is optimal in terms of minimizing the proportion of problematic stations. Even in a homogeneous city, the system exhibits a poor performance: the minimal proportion of problematic stations is of the order of (but not lower than) the inverse of the capacity. We show that simple incentives, such as suggesting users to return to the least loaded station among two stations, improve the situation by an exponential factor. We also compute the rate at which bikes have to be redistributed by trucks to insure a given quality of service. This rate is of the order of the inverse of the station capacity. For all cases considered, the fleet size that corresponds to the best performance is half of the total number of spots plus a few more, the value of the few more can be computed in closed-form as a function of the system parameters. It corresponds to the average number of bikes in circulation.

Introduction

Bike-sharing systems (BSS) are becoming important for urban transportation. They are devoted to short trips. A few BSS have been launched since Copenhagen launched its program in 1995. BSS were widely deployed in the 2000s after Paris launched the large-scale program called Velib, in July 2007. Velib consists of 20 000 available bikes and 1500 stations. Currently, there are more than 400 cities equipped with BSS around the world (see [START_REF] Demaio | Bike-sharing: Its History, Models of Provision, and Future[END_REF] for a history of BSS). The popularity of BSS gives rise to a recent research activity.

The concept of BSS is simple: A user arrives at a station, takes a bike, uses it for a while and then returns it to another station. The lack of resources is one of the major issues: a user can arrive at a station that has no bike available, or wants to return her bike at a station with no empty spot. The allocation of resources, bikes and empty places, has to be managed by the operator in order to offer a reliable alternative to other transportation modes.

The strength of such a system is its ability to meet the demand, in bikes and empty spots. This demand is complex. It depends on the time of the day, the day of the week (week or week-end), the season and the weather, but also the location: housing or working areas generate going-and-coming flows; flows are also generated from up-hill to down-hill stations. This creates unbalanced traffic during the day. Moreover, the system is stochastic due to the arrivals at the stations, the origin-destination pairs and the trip lengths. The lack of resources also generates random choices from the users, who must search for another station. These facts are supported by several data analyses, e.g., [START_REF] Borgnat | Shared bicycles in a city: A signal processing and data analysis perspective[END_REF][START_REF] Froehlich | Measuring the pulse of the city through shared bicycle programs[END_REF][START_REF] Nair | Large-scale vehicle sharing systems: Analysis of vélib[END_REF].

When building a bike-sharing system, a first strategic decision is the planning of the number of stations, their locations and their size. Other long-term operation decisions involve static pricing and fixing the number of bikes in the system. Several papers have studied these issues. See [START_REF] Katzev | Car sharing: A new approach to urban transportation problems[END_REF][START_REF] Shaheen | Growth in worldwide carsharing: an international comparison[END_REF][START_REF] Demaio | Will Smart Bikes Succeed as Public Transportation in the United States?[END_REF][START_REF] Demaio | Bike-sharing: Its History, Models of Provision, and Future[END_REF][START_REF] Nair | Fleet management for vehicle sharing operations[END_REF]. They study the static planning problem based on economical aspects and growth trends. Another important research direction concerns bike repositioning: To solve the problem of unbalanced traffic, bikes can be moved by the operator, either during the night when the traffic is low (static repositioning) or during the day (dynamic repositioning). [START_REF] Raviv | Static repositioning in a bike-sharing system: Models and solution approaches[END_REF] study the optimal placement of bikes at the beginning of a day. [START_REF] Chemla | Bike sharing systems: Solving the static rebalancing problem[END_REF] develop an algorithm that minimizes the distance traveled by trucks to achieve a given bike positions, assuming that bikes do not move (e.g., during the night). The dynamic aspects are studied by [START_REF] Contardo | Balancing a dynamic public bike-sharing system[END_REF][START_REF] Schuijbroek | Inventory rebalancing and vehicle routing in bike sharing systems[END_REF][START_REF] Raviv | Optimal inventory management of a bike-sharing station[END_REF], but their model ignores bike moves between periodical updates of the system. These papers rely mainly on optimization techniques.

Redistribution can also be done by users. In most BSS, users have access to the real-time state of the stations, e.g., by using a smartphone. They can choose to take or to return their bikes to a station near their destinations. Moreover they can be encouraged to do so by the system. For example, Paris, via the Velib+ system, offers a static reward by giving free time slots in order to bring more bikes to up-hill stations. It is estimated that the number of people that obtain rewards via Velib+ during the day is equivalent to the number of bikes redistributed by trucks. To compensate for real-time congestion problems, an alternative is to use real-time pricing mechanisms. This type of congestion control mechanism is widely applied in the transportation or car-rental industry, e.g., [START_REF] Guerriero | Revenue management policies for the truck rental industry[END_REF][START_REF] Waserhole | Vehicle sharing system pricing regulation: Transit optimization of intractable queuing network[END_REF]. Nevertheless, its application to BSS is unclear, as the price paid per trip for using BSS is usually low.

A few papers tackle the stochasticity of BSS, or more generally of vehicle rental systems (see [START_REF] Godfrey | An adaptive dynamic programming algorithm for dynamic fleet management, i: Single period travel times[END_REF][START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF] and literature therein). Their first idea was to obtain a simplified asymptotic behavior when the system gets large. This approximation is valid as BSS are large systems and can give qualitative and quantitative properties for the model. In models with product-form steady-state distribution (see [START_REF] George | Asymptotic analysis of closed queueing networks and its implications to achievable service levels[END_REF][START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF]), the asymptotic expansion of the partition function can be obtained via complex analysis (saddle point method), see [START_REF] Malyshev | Condensation in large closed Jackson networks[END_REF], or probabilistic tools, see [START_REF] Fayolle | Asymptotics and scalings for large product-form networks via the central limit theorem[END_REF]. One of the main limitations of these papers is that they ignore that stations have finite capacities and therefore neglect the saturation effect.

Contributions -We present a model of a bike-sharing system and analyze its steady-state performance. The system is composed of a large number of stations and a fleet of bikes. Each station can host a finite number of bikes K, called its capacity. We measure the performance in terms of proportion of so-called problematic stations, i.e., stations with no available bikes or no empty spots.

We study an homogeneous scenario, in which all stations have the same parameters. Our aim is to obtain a simple tractable model. Intuitively, this system in which the flow of bikes between two stations is, on average, identical in both directions, has roughly speaking the best behavior. For more details, see our work on inhomogeneous BSS, [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF]. We investigate the effects of random choices of users and characterize the influence of the station capacity on the performance. We compare incentives and redistribution mechanisms, and we obtain closed-form characteristics of their performance. This model can be straightforwardly extended to model non-homogeneous cities in order to take into account the difference of attractiveness among the stations. The paper by [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF] provides analytical results in the case where the stations can be grouped into clusters of stations that have the same characteristics. These results will be briefly presented and discussed in this paper. The redistribution and incentive mechanisms in an heterogeneous setting are not studied by [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF] but will be included in their upcoming paper, [START_REF] Fricker | Two-choice regulation in heterogeneous closed networks[END_REF].

This homogeneous model also forgets geometry, present in real-world systems where the bikes are returned to neighboring stations in case of lack of available spots. But the homogeneous model study is nevertheless useful: simulations show that the behavior of both systems are very similar. Thus the qualitative and quantitative results obtained for the homogeneous model apply to a system with a local search of an empty spot.

Our first contribution is to study the simplest model without any incentives or redistribution mechanisms. We use a mean-field approximation that enables us to obtain the asymptotic behavior of our model as the system size becomes large. This asymptotic dynamics leads to simple expressions that give qualitative and quantitative results. This method works even if a closed-form (product-form) expression is not available for the original model. We show that the proportion of problematic stations depends on the fleet size and it decreases slowly with the capacity K. For a given capacity, it presents a minimum that is attained at a fleet size called optimally reliable fleet size, which is equal to K/2+λ/µ bikes per station, where λ is the arrival rate of users at a station and 1/µ is the average trip time. This answers the fleet sizing problem. The term λ/µ represents the average number of bikes in circulation. It quantifies the intuitive idea that the greater the demand is, the more bikes must be put in the system. For this fleet size, the proportion of problematic stations is 2/(K + 1).

To improve the situation, we investigate two different directions: incentives and redistribution. We first assume that users have access to real-time information on the system and follow the rules the system gives about where to take or return the bike. The improvement that is obtained in this case is quantified. We show that returning bikes to a non-saturated station does not change significantly the behavior of the stations and the performance with our metric. The situation improves dramatically when users return their bikes to the least loaded station among two, even if only a fraction of the users do this. Indeed we prove that, if all users do this, the proportion of problematic stations can be as low as √ K2 -K/2 . These results are confirmed by simulations in which users choose among two neighboring stations. Again, the optimally reliable fleet size is a little more than K/2.

In Section 5, we then study what we call the redistribution rate . We define the redistribution rate as the ratio of the number of bikes that have to be moved manually by trucks over the number of bikes that are taken by users. It is proved that the redistribution rate that optimizes performance depends on the fleet size and the station capacity. More precisely, the redistribution rate threshold needed to suppress problematic stations is minimal when the fleet size is K/2 + λ/µ bikes per station and is equal to 1/(K -1).

Finally, in Section 6, we discuss the limitations of the model. We describe briefly the differences that will occur when considering a time-or space-inhomogeneous model. We mainly refer to the paper by [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF], whose main result is an extension of the expression of the minimal proportion of problematic stations within a cluster at some optimally reliable fleet size, which generalizes s = K/2 + λ/µ. We also show simulation results of more realistic models that consider various trip-time distributions and take the geometry into account. In all cases, these models behave similarly to the original model. We also simulate a two-choice model where the choice is made at the beginning of the trip, when taking the bike. We introduce then a different performance indicator, the average number of stations visited before returning a bike. We show that, except when the system's geometry is a line, this indicator can be deduced from the proportion of saturated stations. Moreover we show that our model can be extended, while remaining analytically tractable. We detail the case of mean search times that are shorter than the mean travel time, and the case of losses of users arriving at an empty station are replaced by a search of an available bike in another station. These extensions have also been investigated by simulation on models with geometry. Their behaviors are still very similar.

Organization of the Paper -Section 2 presents the model description and the mean-field techniques. Section 3 deals with the basic model results. Section 4 studies incentive mechanisms where a fraction of users choose the least loaded of two stations to return their bike. Section 5 shows that there exists a threshold for the rate of redistribution by trucks which optimizes performance. Section 6 deals with discussions, extensions and simulation validations. Section 7 concludes.

System Model and Mean-Field Analysis

In this section, we present the basic model. Mean-field techniques are used to investigate the performance of homogeneous BSSs. These techniques reduce the study of the stochastic model to the study of the equilibrium point of a set of differential equations. We detail the steps to obtain this result. The other scenarios studied in this paper fit the same framework. We consider a Markovian model of a bike-sharing system with N stations and a fleet of sN bikes (s bikes per station in average). A bike can be either locked at a station or in transit between two stations. In this paper, we focus on the homogeneous bike-sharing model. This model enables us to obtain a closed-form expression for the optimal performance and also, in the next sections, to investigate incentives and redistribution by trucks in this framework, and to quantify their effects. This study is extended to an inhomogeneous model by [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF]. Each station can host K bikes. At each station, new users arrive at rate λ. If there is no bike at this station, the unhappy user leaves the system. If the station is not empty, the user picks up a bike at this station and joins the pool of riding users. The trip time between the two stations is exponentially distributed with mean 1/µ.

After this time, the riding user wants to return her bike. She chooses a destination at random among all stations. If her destination has fewer than K bikes, the user returns her bike to this station and leaves the system. If the station has K bikes, no more bikes can be returned to this station and this station is called saturated. In this case, the user rides to another station. This station is again chosen at random and the trip time is exponentially distributed with mean 1/µ. This process is repeated until she finds a non-saturated station.

As seen in the rest of the paper, our model can be thoroughly analyzed and leads to closed-form results. This model, however, does not incorporate any geographical information. In a real-world system, users who cannot find a bike or cannot return their bike at a given station will try a neighboring station and not just one at random. These modifications unfortunately lead to intractable models. Nevertheless, we show by using simulations in Section 6 that taking into account locality has little effect on the overall performance.

2.3. Mean-Field Limit and Steady-State Behavior. In this section, we prove that the analysis of the system is essentially the analysis of an ordinary differential equation (ODE) as N goes to infinity and that the equilibrium point can be addressed.

Let us denote by Y N k (t) the proportion of stations where k bikes are available at time t. As the system is homogeneous, the process

(Y N (t)) = (Y N 0 (t) . . . Y N K (t)
) is a Markov process. Suppose the process is at (y 0 . . . y K ). There are two types of transitions:

• Bikes picked up. The arrival rate of users in a station that has k bikes is λN y k . When k ≥ 1, it causes the kth coordinate, y k , to decrease by 1/N and y k-1 to increase by 1/N . • Bikes returned. The number of bikes in transit is equal to the total fleet size sN minus the number of bikes locked at the stations, which is equal to N (s -N k=1 ky k ). As trip times are exponentially distributed with mean 1/µ and stations are chosen at random, a user arrives with a bike at a station with k bikes at rate y k µN (s -K k=1 ky k ). When k ≤ K -1, this causes y k to decrease by 1/N and y k+1 to increase by 1/N . The transitions can be summarized by

y → y + 1 N (e k-1 -e k ) at rate λy k N 1 k>0 , y → y + 1 N (e k+1 -e k ) at rate y k µ(sN - K n=0 ny n N )1 k<K
where the k-th unit vector of R K+1 is denoted by e k and 1 k<K is equal to 1 when k < K and 0 otherwise. This process belongs to the family of density-dependent population processes, defined by [START_REF] Kurtz | Approximation of population processes[END_REF]. This means that there exist a set of vector L ⊂ R K+1 and a set of functions {β } ∈L such that the transitions are of the form y → y + /N and occur at rate N β (y). This implies that, from y, the average change in a small interval dt is f (y)dt = ∈L β (y)dt. As f is Lipschitz-continuous, it is shown in [START_REF] Kurtz | Approximation of population processes[END_REF] that as N goes to infinity, for each T > 0, the process (Y N (t), 0 ≤ t ≤ T ) converges in distribution to a deterministic function (y(t), 0 ≤ t ≤ T ), which is the unique solution of the following differential system of equations,

ẏ(t) = K k=0 y k (t) λ(e k-1 -e k )1 k>0 + µ(s - K k=1 ky k (t))(e k+1 -e k )1 k<K (1)
where e k is the k-th unit vector of R K+1 .

The first term corresponds to the rate of arrival of new users at a station, and the second term corresponds to the rate at which users return bikes, which is µ times the proportion of bikes in transit at time t.

The above differential equation rewrites ẏ(t) = y(t)L y(t) where the y(t)L y(t) is the product of the row vector y(t), by the jump matrix L y(t) . This equation contains the mean-field property of the model: This means that, when N tends to infinity, the empirical distribution y(t) of the stations evolves in time as the distribution of some non-homogeneous Markov process on {0, . . . , K}, whose jumps are given by L y(t) , updated by the current distribution y(t). These jump rates are those of an M/M/1/K queue, where the arrival rate µ(s -K k=1 ky k (t)) is time dependent and the service rate is λ. This queue represents the instantaneous evolution of any station, because all the stations have the same evolution due to the homogeneity.

Throughout the paper, we investigate the steady-state behavior of the system. For all variants of the model studied in this paper, the dynamical system has a unique equilibrium point. Note that this fact alone does not imply that the sequence of invariant measures of Y N concentrates on this fixed point: it is necessary to show that the dynamical system does not have long-term oscillations and, in general, the proof of this is difficult. There are different techniques for obtaining this result. In Section 3, we show the absence of oscillations by using a generic Lyapunov function. Although numerical evidences show that this is also the case for the other models, the proof is out of the scope of the paper and the question is not addressed for models with incentives or redistribution.

2.4. Performance Metric and Proportion of Problematic Stations. In this paper, we mainly focus on a quality of service indicator, called the proportion of problematic stations. This proportion is the proportion of stations where either no bikes are available or that are saturated. When the number of stations N goes to infinity, this proportion converges to ȳ0 + ȳK , where ȳ is the unique fixed point of the differential equation.

This metric generalizes the loss probability, used for example in the context of vehicle rental networks by [START_REF] George | Asymptotic analysis of closed queueing networks and its implications to achievable service levels[END_REF], where the station capacities are infinite. Moreover, a user will be satisfied if she can pick up a bike at her chosen place of departure and return it at her chosen destination. In an homogeneous system like ours and if the origins and the destinations are chosen uniformly at random, this occurs with probability 1 -(1 -ȳ0 )(1 -ȳK ) = ȳ0 + ȳK + ȳ0 ȳK ≈ ȳ0 + ȳK . Hence, our metric is close to the limiting proportion of unsatisfied users, who cannot enter the system or return their bike to the station of their choice, which is the performance metric used in [START_REF] Waserhole | Vehicle sharing system pricing regulation: Transit optimization of intractable queuing network[END_REF] and [START_REF] Nair | Fleet management for vehicle sharing operations[END_REF]. The average sojourn time in the system can also be deduced from ȳ0 and ȳK . When a user wants to return a bike to a saturated station, she has to find another station that is not saturated. When this search is done at random, the average number of stations that are visited before finding a spot is 1/(1 -ȳK ) (see details in Section 6.3.1). In Section 6.3, we show that, for a realistic model of geometry (2D grid), the average number of visited stations is close to 1/(1 -ȳK ).

This justifies the choice of this simple metric, though others can be deduced from ȳ0 and ȳK . Indeed, the sum ȳ0 + ȳK hides the relative value of each term, which can be useful to know. Nevertheless, this has the advantage of providing a single indicator of the performance. Our goal is to obtain bounds on this performance criteria. The proportion of problematic stations is not a cost function. In this paper, we do not question the cost or the practical methods for implementing our mechanisms and leave this question for future work. Hence, throughout the paper, the term optimal performance will be understood in term of minimizing this quality of service. It occurs for a value of the fleet size called optimally reliable fleet size.

Basic Model and Optimal Fleet Size

This section is devoted to the basic model. As seen in Section 2.3, the behavior of the system can be approximated by the ODE (1) when the system becomes large. This allows for a complete study of the performance metric as a function of s. We derive the optimal reliable fleet ratio and discuss the influence of the parameters λ/µ and K.

3.1. Basic Model: Steady-State Analysis. The probabilistic interpretation of the ODE (1) is the key argument to obtain its equilibrium point. Indeed, an equilibrium point ȳ of the ODE (1) is the stationary measure of an M/M/1/K queue with arrival rate µ(s -K k=1 k ȳk ) and service rate λ. For ρ ≥ 0, let ν ρ be the invariant probability measure 1 of a M/M/1/K queue with arrival-to-service rate ratio ρ and define ρ(ȳ) = µ(s -k∈{0,...,K} k ȳk )/λ. The equilibrium points of (1) are thus the solutions of the fixed point equation ȳ = ν ρ(ȳ) .

We now prove the existence and uniqueness of the equilibrium point. For each ρ, there exists a unique stationary measure ν ρ . Hence, this equation is equivalent to ȳ = ν ρ where ρ is the solution of

s = λ µ ρ + K k=1 kν ρ (k). ( 2
)
1 For ρ = 1, νρ is the uniform distribution on {0, . . . , K}. For ρ = 1, νρ is geometric:

νρ(k) = ρ k (Z(ρ)) -1 where Z(ρ) = (1 -ρ K+1 )/(1 -ρ) is the normalizing constant.
This equation can be easily explained. The proportion of bikes per station s is the sum of two terms: The mean number of users still riding, ρλ/µ, and the mean number of bikes per station, K k=1 kν ρ (k). The expression of first term can be computed using the arrival rate λ and the probability 1-ν ρ (0) of finding an available bike at a station. Returning a bike at the k-th attempt takes an average time k/µ and occurs with probability

(1 -ν ρ (K))ν ρ (K) k-1 . Thus, the first term is equal to λ(1-ν ρ (0)) +∞ k=1 (1-ν ρ (K))ν ρ (K) k-1 k/µ,
which reduces, after some computation, to ρλ/µ.

The right part of Equation ( 2) strictly increases in ρ. Therefore, for each s > 0, there is a unique ρ solution of Equation ( 2) and thus a unique equilibrium point ν ρ is denoted by ȳ(ρ) in the following.

In [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF], we exhibit a Lyapunov function for this dynamics in a more general setting. It shows that all trajectories of the ODE converge to the unique fixed point. As a consequence, the steady-state empirical distribution of the system concentrates on this unique fixed point. This means that the limiting stationary distribution of the number of bikes at a station is this fixed point, i.e., a geometric distribution on {0, . . . , K} where the parameter ρ is the solution of Equation (2).

Proportion of Problematic Stations.

The next theorem shows the effect of the number of bikes per station s on the performance of the system. The equilibrium point of the ODE ( 1) is ȳ = ν ρ , where ρ is the unique solution of the fixed point equation ( 2), which can be rewritten as a polynomial equation in ρ of order K + 1. Hence, even if solving this equation is possible for very small values of K, finding a closed-from expression for K ≥ 4 is unfeasible. Nevertheless, Equation ( 2) provides an efficient way to achieve a performance study of the system by considering the parametric curve

ρ λ µ + K k=1 kρ k ȳ0 (ρ), ȳ0 (ρ) + ȳK (ρ) {ρ>0} (3)
where, and in the following, ȳ(ρ) is equal to ν ρ . The use of this parametric curve allows us to study efficiently the performance of the system as a function of the number of bikes per station s. These results are summarized in the next theorem and in Figure 1.

Theorem 1. For the homogeneous model, (i) the limiting proportion of problematic stations, ȳ0 + ȳK , is minimal when s = K/2 + λ/µ and the minimum is equal to 2/(K + 1). It goes to one when s goes to zero or infinity. (ii) As K grows, the performance around s = K/2 + λ/µ becomes flatter and insensitive to s and λ/µ.

Proof. Let ϕ(ρ) = ȳ0 (ρ) + ȳK (ρ) = 1 -(ρ K -ρ)/(ρ K+1 -1) and s(ρ) = λρ/µ + K k=1 kρ k (1 -ρ)/(1 -ρ K+1
). Functions ϕ and s are well defined on [0, ∞). The proportion of problematic stations as a function of s is given by ψ = ϕ • s -1 . First we prove that ψ has a minimum at s 0 = s(1) which is 2/(K + 1). For that, differentiating function ϕ with respect to ρ gives

ϕ (ρ) = ρ 2K -1 + K(ρ K-1 -ρ K+1 ) (ρ K+1 -1) 2 .
Differentiating the numerator and studying the variation, it holds that the numerator strictly increases on [0, ∞) and ϕ (1) = 0. Thus ϕ strictly decreases on ]0, 1[, strictly increases on ]1, +∞[ and has a minimum at 1 which is ϕ(1) = 2/(K + 1). This shows the optimal number of bikes per station corresponds to ρ = 1, and thus s(1) = K/2 + λ/µ is the optimal reliable proportion of bikes per station. This leads to a proportion of problematic stations of 2/(K + 1) and concludes the proof of (i).

To prove (ii), note that the second derivative of

ψ = ϕ • s -1 at s 0 = s(1) is ψ (s 0 ) = ϕ (1)/s (1) 2 . An asymptotic expansion of ϕ at ρ = 1 is given by ϕ(ρ) = 2 K + 1 + 1 6
K(K -1) K + 1 (ρ -1) 2 + O((ρ -1) 3 )
and therefore ϕ (1) = K(K -1)/3(K + 1). Moreover, differentiating s gives that s (1) = λ/µ + K 2 /12 + K/6, which leads to

ψ (s 0 ) = K(K -1) 3(K + 1)(λ/µ + K 2 /12 + K/6) 2 ∼ K→∞ 48 K 3 .
This means that ψ is never sharp for the range of values considered in this paper, i.e., K ≥ 10. Moreover, ψ (s 0 ) goes quickly to 0 as K grows.

This theorem indicates that, even for a homogeneous system for which the number of bikes per station is chosen knowing all parameters of the users, the proportion of problematic stations decreases only at rate 1/K. This is not enough for practical situations where, for space constraints and construction costs, station capacities are often fewer than 20 or 30 bikes. A system with 30 bikes per station would lead to a proportion of problematic stations of 2/31 ≈ 6.5%. Although it might be acceptable if this bike-sharing system is used only once in a while, a probability of 6.5% for a station to be problematic is too high for a reliable daily mode of transportation. The results of Theorem 1 are illustrated by Figure 1, which plots the performance as the parametric curve given by Equation ( 3) for two values of the station capacity and three values of λ/µ.

When K is fixed to 30 and λ/µ = 1, the performance is almost equally good with 10 to 20 bikes per station (i.e., s ∈ [K/3; 2K/3]). However, as soon as the number of bikes per station is lower or higher, the performance decreases significantly. The problematic case is mainly due to empty stations at low s versus saturated ones at high s. When the size of the stations is K = 100, the performance is less sensitive to the number of bikes per station. As pointed out by Theorem 1, in this case, the proportion of problematic stations is 2/(K + 1) ≈ 2%: Multiplying the station capacity by 3 divides by 3 the minimum proportion of problematic stations. Having some stations designed to accomodate up to 100 bikes is realistic for stations near a subway for example, but having all stations in a city with 100 spots is very costly in terms of space and installation.

When λ/µ = 10, the situation is similar to the case λ/µ = 1, with curves shifted to the right. The minimum number of problematic stations is the same, only the optimal reliable fleet size is changed. This can be deduced from (3) as the term λ/µ affects only s(ρ)=ρλ/µ+ kρ k ȳ0 (ρ) and not the proportion of problematic stations ȳ0 (ρ)+ȳ K (ρ).

These results suggest that without incentives for users to return their bikes to a non-saturated station or without any load-balancing mechanisms, the implementation of a bike-sharing system will always observe a poor performance, even if the system is homogeneous and there are no preferred areas. In a real system where some regions are more crowded than others (e.g., because of the trips from residential areas to work areas), the situation can only be worse, see [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF]. In the following, we will examine simple mechanisms that improve dramatically the situation.

If People

Return the Bikes to a Non-saturated Station. Before studying incentive or regulation mechanisms, in this section we study a variant of the model where users know which stations are empty or saturated. They always arrive to non-empty stations and return their bikes only to non-saturated stations.

The dynamics of the system are slightly modified as follows. As before, there is a Poisson arrival process in the system at rate N λ, but each arriving user picks at random a station among the non-empty stations. If there are no non-empty stations, she leaves the system. If the user manages to find a bike, then after a time exponentially distributed with parameter µ, she arrives at a non-saturated station picked at random (i.e., with fewer than K bikes), returns her bike to this station and leaves the system. Note that there is always a non-saturated station (this is the case if s < K).

The transitions of (Y N (t)) are now given by

y → y + 1 N (e k-1 -e k ) λy k 1 -y 0 N 1 k>0, y0<1 y → y + 1 N (e k+1 -e k ) y k 1 -y K µ sN - K n=0 ny n N 1 k<K, y K <1 .
The differential equation is replaced by ẏ = f (y) where

f (y) = K k=0 y k λ 1 -y 0 (e k-1 -e k )1 k>0 + µ(s - K k=1 ky k ) 1 -y K (e k+1 -e k )1 k<K .
The function f is discontinuous when y 0 goes to 1 or when y K goes to 1. Nevertheless, it can be shown with elementary arguments that if λ/µ < s < K +λ/µ then the differential equation ẏ = f (y) has a unique solution. In the following, we assume that λ/µ < s < K + λ/µ. As for the previous model, equation ẏ = f (y) can be rewritten as ẏ = yL y . This time, L y is the infinitesimal generator of an M/M/1/K queue with arrival rate µ(sk ky k )/(1 -y K ) and service rate λ/(1 -y 0 ). By the same method as in the previous section, it can be proved that the dynamical system has a unique fixed point ȳ, which is solution of the equation s = λ/µ + K k=1 k ȳk (ρ). Moreover, following the same lines as Tibi [26, Proposition 4.3], the steady-state, denoted by Y N (∞), converges as N gets large, to this fixed point. The limiting steady-state of the number of bikes at a station is, again, geometrically distributed, with parameter ρ given by the previous equation. The fact that the term ρλ/µ is replaced here by λ/µ can be simply explained. Each user is accepted in the system and returns the bike after one trip with mean time 1/µ. There are, on average, λ/µ users riding per station.

When studying the fixed point of the system, we find that the main difference with the original model studied in Section 3.2 is the expression of s. Therefore, the performance of the system is easily plotted by a parametric curve similar to (3). The proportion of problematic stations has a similar shape for this model and the one of the previous section. As before, the minimal proportion is 2/(K + 1) and is attained for s = K/2 + λ/µ. When s is not equal to K/2 + λ/µ, this proportion will be higher than in the classic model. This is illustrated in Figure 2 where the proportion of problematic stations for that model is compared with the model studied in Section 3.1. For small s, the less satisfactory behavior of the regulated system is due to the fact that every user can enter the system. This resembles the influence of a larger λ in Figure 1. For large s, this poor behavior of the system is related to the improvement on the customer trip time. It has the same effect as the influence of 1/µ in the basic system. This shows that, although forcing people to go to a non-saturated or non-empty station reduces the unhappy users because anyone can pick up or leave a bike at anytime, it makes the system more congested and degrades the situation for users who are not aware of such mechanisms.

Incentives and the Power of Two Choices

In this section, we consider that, when a user wants to return her bike, she indicates two stations and the bike-sharing system indicates to her which one of the two has the least number of bikes available. We show that, when the two stations are picked at random, the proportion of problematic stations diminishes as √ K2 -K/2 (instead of 1/K in the original model). The performance is thus improved dramatically, and even if only a small percentage of users obey this rule. This result is similar to the well-known power of two choices that has been proved to be a very efficient load balancing strategy, see [START_REF] Mitzenmacher | The power of two choices in randomized load balancing[END_REF].

4.1. The Two-Choice Model and Its Steady-State Analysis. We consider an homogeneous model with N stations and s bikes per station. As before, users arrive at rate λ in each station and pick up a bike if the station is not empty. Otherwise, they leave the system. When a user chooses her destination, instead of choosing one station, she picks two stations at random, travels and returns the bike to the one that has the lowest number of bikes available.

Let u k (t) be the proportion of stations with k or more bikes at time t (k ∈ {0 . . . K}) i.e., u k (t) = y k (t) + • • • + y K (t). The state of the system can be described by the vector (u k (t)) k∈{0,...K} that is such that u

K (t) ≤ u K-1 (t) ≤ • • • ≤ u 0 (t) = 1.
There are two types of transitions for the Markov process. Suppose (u(t)) is at u = (u 0 , . . . , u K ). The first one is a transition from u to u-e k , when a user picks up a bike from a station with k bikes. This happens at rate N λ(u k -u k+1 1 {k<K} ). The second type is a transition from u to u + e k , when a user returns a bike to a station with k bikes. The number of bikes locked at stations is

K k=0 ky k = K k=1 u k .
Hence, there are N (s -k≥1 u k ) bikes in transit. As a user chooses the least loaded among two stations, a user returns a bike at a station with k -1 bikes at rate µN

(u 2 k-1 -u 2 k )(s - K k=1 u k ).
As in Section 2, as N grows large, the behavior of the system can be approximated by the dynamics of the following ODE:

uk (t) = -λ(u k (t) -u k+1 (t)) + µ(u 2 k-1 (t) -u 2 k (t))(s - K k=1 u k (t)), (4)
for k ∈ {1, . . . , K} and u 0 (t) = 1 and u (t) = 0 for > K.

The following theorem shows that these incentives dramatically improve the performance compared to the original model where users go to a station at random (Theorem 1). For a given capacity K, the optimal proportion of problematic stations goes from 2/(K + 1) in the original model to

√ K2 -K/2 .
Theorem 2. Assume that all users obey to the two-choice rule. Then, the corresponding dynamical system, given by (4) has a unique fixed point. The proportion of problematic stations is lower than 4

√ K 2 -K/2 for all s ∈ [K/2 + λ/µ; K -log 2 K - 3 + λ/µ].
Proof. First show that the ODE (4) has a unique fixed point. Let ρ := µ(s -k≥1 ūk )/λ. The key point is to reduce the equation giving the fixed point to a first order recurrence equation. Indeed, a direct recurrence gives that a fixed point must satisfy ū0 = 1 and for all k ≤ K:

ūk+1 = ρ(ū 2 k -1) + ū1 (5)
with ūK+1 = 0.

For all k ≥ 1 and x ∈ [0; 1], define ūk (x) by ū0 (x) = 1 and ūk+1 (x) = ρ(ū k (x) 2 -1) + x. By induction on k, there is an increasing sequence

x 1 < x 2 < x 3 • • • < ρ such that x → ūk (x) is strictly increasing on [x k-1 , ρ] and ūk (x k ) = 0. Indeed, • This is true for k = 1 because ū1 (x) = x. • Then, if it is true for some k ≥ 1, then ūk+1 is increasing on [x k , ρ] because x → ūk (x) is increasing and positive on [x k ; ρ]. Moreover, ūk (x k-1 ) = x k-1 -ρ < 0 and ūk+1 (ρ) = ρ(ū 2 k (ρ) -1) + ρ = ρ(ū 2 k (ρ)) > 0. This shows that there exists a unique x k such that ūk (x) = 0 on [x k-1 , 1].
A fixed point of Equation ( 4) is a vector (ū 1 (x), ū2 (x), . . . ūK (x)) such that ūk (x) ≥ 0 and ūK+1 (x) = 0. By the property stated above, for a fixed ρ, there is a unique fixed point, which is (ū 1 (x K+1 ), . . . ūK (x K+1 )). Moreover, s = k≥1 ūk + ρλ/µ is increasing in ρ, which implies that there is a unique fixed point ρ when s is fixed.

Let k ≤ K and assume that ρ ≤ 1. If ū1 ≥ ρ, a direct recurrence shows that ūk ≥ ρ 2 k -1 for k ≤ K + 1 , which contradicts the fact that ūK+1 = 0. Therefore, ū1 < ρ. Hence, for all 1 ≤ k ≤ K,

ūk+1 = ρ(ū 2 k -1) + ū1 = ρū 2 k + (ū 1 -ρ) < ρū 2 k ≤ ū2 k which implies that ūk ≤ ū2 k-1 1
. As ūK+1 = 0, using Equation ( 5), ( 6)

0 = ūK+1 = ρ(ū 2 K -1) + ū1 ≤ ρ(ū 2 K 1 -1) + ū1 ≤ ū2 K 1 + ū1 -ρ.
Let δ = 1 -ρ and ε = ρ -ū1 ≥ 0. Using Equation ( 6),

(7) 0 ≤ (ρ -ε) 2 K -ε ≤ (1 -ε) 2 K -ε ≤ exp(-2 K ε) -ε. If ε ≥ K2 -K , then (1 -ε) 2 K -ε ≤ exp(-K) -K2 -K
, which is less than 0 for all K ≥ 1. This contradicts Equation ( 7) and shows that ε ≤ K2 -K . The proportion of empty stations is ȳ0 = 1 -ū1 = δ + ε. The proportion of saturated stations is ȳK = ūK , which is such that ρ(ū 2 K -1) + ū1 = 0. Thus, ūK = (ρ -ū1 )/ρ. This shows that, for all ρ ∈ [1 -2 -K/2 ; 1], the proportion of problematic stations is less than

ȳ0 + ȳK = δ + ε + ε/ρ ≤ 2 -K/2 + K2 -K + K2 -K 1 -2 -K/2 .
This quantity is less than 4 √ K2 -K/2 for all K ≥ 1 and is asymptotically equivalent to √ K2 -K/2 . The fleet size s equals K k=1 ūk + ρλ/µ, thus is an increasing function of ρ.

Moreover, ūk ≤ ū2 k-1 1 ≤ ρ 2 k-1 . Hence, when ρ = 1 -2 -K/2 , K k=1 ūk ≤ K k=1 (1 -2 -K/2 ) 2 k-1 ≤ K k=1 exp(-2 k-1-K/2 ) = K/2-1 i=-K/2 exp(-2 i ) < K/2.
This shows that if

s ≥ K/2 + λ/µ, ρ ≥ 1 -2 -K/2 . When ρ = 1, a direct induction on k shows that ūk ≥ max(0, 1 -2 k ε). Let j be such that 1 -2 j ε ≥ 0 > 1 -2 j+1 ε. For such a j, j + 1 ≥ log 2 ε = K -log 2 K. Hence K k=1 ūk ≥ j k=1 1 -2 k ε ≥ j -(2 j+1 -2)ε ≥ j -2 j+1 ε ≥ K -log 2 K -3.
This implies that, for all s

∈ [K/2 + λ/µ; K -log 2 K -3 + λ/µ], ρ ∈ [1 -2 -K/2 ; 1].
Assume now that only a fraction of the users follow this rule and that the others go to a station at random. This could happen if the users are rewarded, when they obey the two-choice rule, like in the Velib+ system. To model this behavior, we assume that each user obeys to the two-choice rule with probability r and otherwise chooses only one station and returns the bike to it. The dynamics are similar to Equation ( 4) and an equilibrium point ū satisfies the following equations: ū0 = 1 and

ūk -ūk+1 = ρ r(ū 2 k-1 -ū2 k ) + (1 -r)(ū k-1 -ūk ) for k ∈ {1 . . . K}. (8)
In this case, the fixed point Equation ( 5) becomes ūk+1 = ρ(r(1 -ū2 k ) + (1 -r)(1ūk )) + ū1 . The proof of the uniqueness of the solution of Equation ( 5) can be easily adapted to show that Equation (8) also has a unique fixed point.

4.2.

Impact on the Performance. Due to the uniqueness of the solution ū, the proof of Theorem 2, especially Equation ( 5), provides an efficient way to compute ū as a function of ρ. This shows that, if ρ is fixed, the number of bikes in the system is s(ρ) = λρ/µ + K k=1 ūk (ρ). The performance indicator can be plotted by using a parametric curve of parameter ρ. These results are reported in Figure 3 and indicate that the performance of the system is radically improved compared to the original case (Figure 1), even if 20% of users obey the two-choice rule.

In Figure 3(a) we report the proportion of problematic stations as a function of the proportion of bikes per station when everyone follows the two-choice rule. We observe that the optimal performance of the system is much better than in the original system (here K = 30 and λ/µ = 1). Although in the original system, the proportion of problematic stations is at best around 7%, here the proportion of problematic stations can be as low as 10 -6 (this is lower than the bound of Theorem 2, which is 2 √ 31 • 2 -30/2 ≈ 3 • 10 -4 ). Moreover, this curve is rather insensitive to variations in the number of bikes: The proportion of problematic stations is less than 10 -3 if s is between 10 and 27 bikes. An interesting phenomenon occurs when the average number of bikes per station s exceeds the capacity of the station. In this case, there is a higher proportion of problematic stations for the two-choice model than for the original situation. This is explained by the fact that when a user obeys the two-choice rule, it is easier for her to return a bike. Hence, when more users obey the two-choice rule, there are fewer bikes in transit and the stations are more occupied. This negative effect only occurs when s ≥ 30, which confirms Theorem 2: Performance is low for s less than a value K -log 2 K -3+λ/µ close to K.

On Figure 3(b), the average number of bikes per station is fixed, s = 16 = K/2 + λ/µ, and the proportion r of users who obey the two-choice rule varies from 0 to 1. This shows that the proportion of problematic stations diminishes rapidly as soon as the number of users obeying the rule grows. Moreover, the decrease is approximately exponential: if 25% more users obey the rule, the proportion of problematic stations is roughly divided by 10.

Optimal Redistribution Rate

Balancing the number of bikes in various areas in a city is one of the major issues of bike-sharing systems. A widely adopted solution is the use of trucks to move bikes from saturated stations to empty ones. This redistribution mechanism can equalize the one-directional flows of travelers, for example from residential areas to work areas, but also the imbalances due to the choices of users. In this section the minimal redistribution rate needed to suppress any problematic station is investigated, and we conclude by showing that it decreases as the inverse of the station capacity. Our analysis assumes that bikes are moved one by one. This assumption will be relaxed in the simulations presented in Section 6.5, thus showing that a larger truck size does not affect qualitatively the performance.

The Redistribution Model and Its Steady-State Analysis.

We consider a homogeneous model of bike-sharing systems with N stations equipped with a truck that visits the stations to adjust their load. The user behavior is the same as in Section 2. The arrival rate at any station is λ and a bike trip takes a time exponentially distributed of mean 1/µ. A truck knows the station occupancies at any time. It goes to the most loaded station, picks up a bike and returns it to the least loaded station. The trip time of the truck is neglected (the bikes are assumed to move instantaneously from highly loaded to lightly loaded stations). This description amounts to one truck that moves bikes at rate N γ. The resulting Markov model is the same if there is δ(N ) trucks moving bikes at rate N γ/δ(N ). In the rest of the section, we study the effect on the performance of the ratio γ/λ. This ratio is the average number of bikes per second that are moved manually by the operator divided by the number of bikes per second taken by regular users.

As in Section 4, let u k (t) be the proportion of stations that have k bikes or more available at time t. In particular, u 0 (t) = 1 and u K+1 (t) = 0. There are three kinds of transitions in the system: arrivals and departures of users and redistribution. The fluid model transitions corresponding to the user arrivals and departures are the same as in Equation ( 1) with a number of bikes in transit of N (s -

K k=1 u k ).
Moreover, the redistribution part only affects the most loaded and least loaded stations, i.e., stations that have k bikes available, where k is such that no stations have less less than k bikes available (u k-1 =1) or no stations have more than k bikes available (u k+1 = 0). This shows that the expected variation of u during a small time interval is equal to f (u) = (f 0 (u) . . . f K (u)), where for all k ∈ {1, . . . , K-1},

f k (u) = λ(u k+1 -u k )+µ s - K k=1 u k (u k-1 -u k )+    γ if u k-1 = 1 and u k < 1 -γ if u k+1 = 0 and u k > 0 0 otherwise
The function f (u) is not continuous in u. Hence, the ODE u = f (u) is not well defined and can have zero solutions. To overcome this discontinuity problem, it has been shown by [START_REF] Gast | Mean field limit of non-smooth systems and differential inclusions[END_REF][START_REF] Gast | Markov chains with discontinuous drifts have differential inclusion limits[END_REF], that this ODE can be replaced by a differential inclusion uk ∈ F (u), where F (u) is the convex closure of the set of values f (u ) for u in a neighborhood of u. This differential inclusion is a good approximation of the stochastic system as N grows. In particular, as with classic ODE, if all the solutions of the differential inclusion converge to a fixed point, then their stationary measures concentrate on this point as N goes to infinity, see [START_REF] Gast | Markov chains with discontinuous drifts have differential inclusion limits[END_REF].

In our present case, the differential inclusion is

uk ∈ λ(u k+1 -u k ) + µ s - K k=1 u k (u k-1 -u k ) + G k (u), (9)
where

G(u) =        (a 0 . . . a i , 0 . . . 0, -b j • • • -b K ) s.t.        i k=1 a k = K k=j b k = γ a k = 0 if u k < 1 b k = 0 if u k+1 > 0 a k ≥ 0, b k ≥ 0.       
To ease the presentation, the details of its construction are omitted. The construction is similar to Section 4.3 of [START_REF] Gast | Markov chains with discontinuous drifts have differential inclusion limits[END_REF]. This leads to the following result. Theorem 3. Assume that a truck moves bikes from the most loaded station to the least loaded one at rate γN . If x = min(s-λ/µ, K-s+λ/µ) and γ * = 2λ 2x -x 2x 2x-1 then the fixed point of the dynamical system (9) satisfies:

• If γ ≥ γ * , then there is no problematic station.

• If γ < γ * , the proportion of problematic stations decreases with γ.

The quantity γ * is called the optimal redistribution rate. Setting γ = γ * is not necessarily optimal in terms of cost but it corresponds to a key of the performance: When γ < γ * , the proportion of problematic station decreases almost linearly and is zero when γ > γ * .

Proof. Let us assume that s ≤ K/2 + λ/µ. The other case is symmetric and can be treated similarly. The proportion of problematic stations is non-increasing in the redistribution rate γ. We define the vector u = (u 0 , u 1 , . . . , u K ) by

u k = 1 -(k -1) γ λ if k ≤ 2x = 2(s -λ µ ) 0 otherwise
Let us show that when γ = γ * , u is a fixed point of the differential inclusion (9), i.e., there exists g ∈ G(u) such that Equation ( 9) is equal to zero. Let g = (g 0 , g 1 , . . . , g K ) be a vector such that g 1 = γ, g 2s = λu 2s -γ, g 2s +1 = -λu 2s and g i = 0 otherwise. The vector g belongs to G(u), defined in Equation ( 9). Moreover, by a direct computation,

K k=1 u k = 2x k=1 1 -2(k -1) 2x -x 2x 2x -1 = x = s - λ µ .
In particular, µ(s -

K k=1 u k ) = λ.
Plugging it in Equation ( 9),

• for k = 1, λ(u 2 -u 1 )µ(s - K k=1 u k )λ(u 0 -u 1 ) + γ = λ(u 2 -u 1 ) + γ = 0. • for k ∈ {2 . . . 2s -1}, λ(u k+1 -u k ) + µ(s - K k=1 u k )(u k-1 -u k ) = λγ - λγ = 0. • for k = 2s , λ(u 2s +1 -u 2s )+µ(s- K k=1 u k )(u 2s -1 -u 2s )+λu 2s - γ = 0 • for k = 2s + 1, λ(u 2s +2 -u 2s +1 ) + µ(s- K k=1 u k )(u 2s -u 2s +1 ) + λ -γu 2s = 0
This proves that u is a fixed point of the differential inclusion [START_REF] Froehlich | Measuring the pulse of the city through shared bicycle programs[END_REF]. Using monotonicity arguments as in Theorem 2, we can show that this fixed point is unique. However, the proof is quite technical, hence omitted. As the proportion of problematic stations is zero for u, this concludes the proof of the theorem.

We now consider the case ρ < 1 (which corresponds to s < K/2 + λ/µ and γ < γ * ). Define z(ρ

) := (1 -ρ + (ρ K -ρ)γ)/(1 -ρ K+1 ) and a sequence x(ρ) = (x 0 . . . x K ): • If ρ K-1 (ρz + γ) > γ, then define x k (ρ) = ρ k z(ρ) for k ∈ {1 . . . K -1} and x K (ρ) = ρ K z(ρ) -γ. • Otherwise, let x 0 (ρ) = (1 -ρ) and x k =      ρ k (1 -ρ) if ρ k+1 (1 -ρ) > γ ρ k (1-ρ)-γ 1-ρ if ρ k (1 -ρ) > γ > ρ k+1 (1 -ρ) 0 otherwise
It is straightforward to verify that for all ρ, x(ρ) is a fixed point of the differential equation [START_REF] Froehlich | Measuring the pulse of the city through shared bicycle programs[END_REF]. Moreover, the quantity k x k (ρ) is an increasing function of ρ. This shows that the differential equation has a unique fixed point (for γ < γ * ). 5.2. Impact on the Performance. Theorem 3 shows that the optimal redistribution rate decreases with the station capacity. The optimal redistribution rate is minimal for s = K/2 + λ/µ. In this case, moving bikes from saturated to empty stations at rate λ/(K -1) suffices to avoid the existence of problematic stations. When x = min(s -λ/µ, K -s + λ/µ) is an integer, the optimal redistribution rate simplifies in γ * = λ/(2x -1). These results are illustrated in Figure 4. The station capacity is set to K = 10 and µ = +∞ (the trip time is negligible). The proportion of stations that have x bikes available is plotted as a function of x. Two fleet sizes s = K/2 = 5 and s = 7 are compared, according to various values of γ: γ = 0, γ = γ * 5 = 1/9 (the optimal redistribution rate for s = K/2) and γ = γ * 7 = 1/5 (the optimal redistribution rate for s = 7).

In both cases, the occupancy distribution concentrates around s as γ increases. When s = 5, the occupancy distribution is uniform for γ = 0. As expected, there is no problematic station when γ ≥ γ * 5 = 1/9. When s = 7, the occupancy distribution is geometric for γ = 0 (see Section 3.1). For γ = 1/9 < γ * 7 , there is no empty station and the occupancy distribution is truncated geometric. When γ = γ * 7 , the occupancy distribution is uniform on {5 . . . 9} and there is no problematic station.

Validation of the Model: Extensions and Simulations

6.1. Time-and Space-Inhomogeneous Systems. In this paper, we focus on homogeneous bike-sharing systems. This means that the travel demand is constant with time and that this time is the same for any pair of origin and destination. The model presented in Section 3.1 captures the main features of these systems, i.e., the loss of users who cannot find a bike or the travel of users who have to search for an available spot when returning a bike. As we consider a homogeneous model, its performance is naturally described in terms of the proportion of problematic stations in steady-state.

A natural extension of these results is to consider space-inhomogeneity and timeinhomogeneity. Space-inhomogeneity often occurs in cities where some stations are geographically higher or lower than others, which creates a flow from one region of the city to another. Our basic model can be directly extended to this case, for example, by considering clusters of stations that have a similar level of popularity. The steady-state behavior of such a model is analyzed by [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF]. This extension enables us to compute the fleet size that is optimal in terms of minimizing the proportion of problematic stations in a given cluster. Because of working hours or week-ends, bike-sharing systems are often time-inhomogeneous. Modeling these phenomena can be done by considering the waves of people going from housing to working areas in the morning and coming back in the evening, as in [START_REF] Waserhole | Pricing techniques for self regulation in vehicle sharing systems[END_REF]. In this case, the proportion of problematic stations does not reflect the performance of the system and the definition of a performance metric is not clear and might depend on the situation. Characterizing and understanding such systems is an issue beyond the scope of this paper, and we plan to tackle it in future work. 6.2. Distribution of Trip Times.

6.2.1.

One-Choice Model: Insensibility to the Distribution of Trip Times. In order to obtain a tractable model, we choose the inter-arrival times of users and trip times to be exponentially distributed. This leads to a Markovian model that has a compact representation. We investigate the influence of more realistic distributions by using simulation. Our preliminary simulation results indicate that if the average trip time has an influence on the performance, the actual distribution has little effect. The behavior of a system with general trip-time distribution is very similar to a system where trip times have an exponential distribution with the same mean.

To verify this assumption, we compare four possible trip-time distributions:

( In all cases, the average trip time is 1/µ. We simulate the four cases on a system composed of N = 100 stations. Apart from the trip distribution, the model is exactly the same as in Section 2.2. Users arrive according to a Poisson process and there is no geometry. The results are reported in Figure 5.

For each distribution, we plot the proportion of problematic stations for this distribution minus the proportion of problematic stations for the original model. The results are shown as a function of the fleet size s for two situations: λ = µ (Figure 5(b)) and λ = 10µ (Figure 5(b)). The results reported in Figure 5 are the average over 100 simulations. The errorbars are the 95% confidence interval. We observe that, for a fixed value of λ/µ, the average difference is always small and is almost smaller than the confidence interval. However, we recall that the average trip duration 1/µ does have an influence (see Figure 1 and Figure 10).

We conclude that the trip distribution has a negligible effect on the performance. The performance of the system depends only on the average trip time 1/µ. Note that we also simulate a case where the trip time is exponentially distributed but when the time between two arrivals of customers follows one of the four distributions. The results, not reported here, show that the inter-arrival time distribution also has a negligible effect on the proportion of problematic stations.

6.2.2. Two-Choice Model with Delays: Longer Trip Times Degrades the Performance. In this section, we study by simulation the effect of the average trip time on the performance of the two-choice policy with another two-choice model described as follows. Note that such a model seems analytically much more difficult.

It is an homogeneous model with N = 100 stations and s = K/2 + λ/µ bikes per station. Users arrive at rate λ = 1 in each station and pick up a bike if the station is not empty. When a user picks up a bike, she chooses a destination where she wants to return the bike. To do so, she picks two stations at random and chooses to the one that has the largest number of empty spots. She arrives at her destination after a trip time with exponential distribution. If her destination has no available spots, she tries another station at random. This model has two differences with the two-choice model of Section 4. First, we assume that users choose the least loaded station before beginning their trip. Furthermore, in the new model, a user who cannot return her bike to her destination picks a station at random and does not repeat the two-choice rule. We simulate this model for four trip-time distributions (exponential, log-normal, uniform and deterministic). We plot in Figure 6 the proportion of problematic stations as a function of the average trip time, 1/µ. In each case, the capacity of station is K = 30 and the fleet size is equal to s = K/2 + λ/µ. We observe that, as expected, the performance for the two-choice model degrades as the trip time increases. This is explained by the delay in the information: when the trip time is long, a station that had few bikes available when the user departs does not necessarily still have few bikes when the user returns. The performance of the original model is not affected by the variation of the average trip time, because the fleet size is equal to s = K/2 + λ/µ. We compare the two models (one-choice and two-choice). For a very long average trip time, the performance when the two-choice rule is applied can even be worse than when this rule is not applied. Although counterintuitive, this phenomena can be explained by the delays: for example, let us consider that all trips have a duration of 10 minutes. Then, a station that has only a few bikes available at time t will have many users who will decide to ride to it between time t and time t + 10. But these users will not arrive before time t + 10. As a consequence, it is likely that this station will experience a burst of arrivals after time t + 10, causing more problems than if the choices were made at random. As shown in Figure 6, this phenomena is exacerbated when the trip-time distribution is more concentrated (the proportion for problematic stations increases when going from deterministic to uniform to log-normal to exponential distribution).

We want to emphasize that this problem occurs only when the trip time is very long compared to the arrival rate (about 50 when the distribution is log-normal). Hence, we conjecture that the problem would not occur in a realistic scenario. We plan to study this question in a future work. 6.3. Influence of Geometry on the Performance Metric. Our theoretical results and closed-form formula strongly rely on the assumption that the model ignores geometry. In real-world systems, finding or returning a bike can induce a local search for an available bike or an available spot. Studying such systems analytically is out of reach. This section presents simulation results that show that the influence of geometry on the proportion of problematic station is limited, both for the basic model and the two-choice model. In Section 6.3.1 we show, however, that it has an effect when other metrics are considered, such as the time needed to return a bike.

The model. We consider two representations of geometry represented in Figure 7 and 8: a 2D grid and a single line. The 2D grid is a schematic representation of a homogeneous city center like that of Manhattan. This situation is a good representation of many bike-sharing systems: the stations are placed quite evenly on a plane and each station has a few neighbors (here, four) spread around it. The 1D line is a more extreme case, which corresponds to a city spread along a single road. We expect the imbalances due to random choices to have more effect in the 1D line than in the 2D grid. We simulate the two models. Users arrive at each station with rate λ. If the station is empty, the user does not enter the system. Otherwise, she picks up a bike. In the one-choice case (see Figure 7), she chooses a destination at random. If this station is saturated, she performs a random walk on the neighbors of the destination until she finds a non-saturated station. In the two-choice case (see Figure 8), the user chooses the least loaded station among two neighbors. Again, the user performs a local search if the station is saturated.

The proportion of problematic stations for all cases is reported in Figure 7 and Figure 8 for µ = +∞. In both cases, the models were simulated with N = 25, N = 100 and N = 400 stations. Each point represents the average over 20 independent simulations. The error bars indicate 95% confidence intervals but most of the time are too small to be seen. We compare these values with the theoretical bounds of the models without geometry: 2/(K + 1) for the one-choice model (Figure 7) and √ K2 -K/2 for the two-choice model (Figure 8). In all cases, the performance exhibits the same trend in the models with geometry as that of theoretical bounds. In particular, the performance obtained for the 2D grid are mostly independent of N and are very similar to the theoretical bounds. This shows that the bounds obtained in Theorems 1 and 2 are representative of more realistic systems, even if they are obtained on models that do not take into account the geometry. 6.3.1. Average Number of Visited Stations. We now consider a different performance indicator that is the average number of stations that the user has to travel to before she can return her bike. This metric is an indicator of how much time is necessary to return a bike and knowing this is critical for users.

In the original model without geometry, this metric can be easily computed as a function of the proportion of saturated stations. Let p be this proportion. With probability 1 -p, the original destination is not saturated and the user visits only one station. Otherwise (with probability p) the user chooses another destination at random and repeats this operation until she finds a non-saturated station. As the new destination is chosen at random, it also has a probability p of being saturated. Hence, the number of visited stations before returning a bike is, on average, (

∞ i=0 (1 + i)p i = 1/(1 -p). 1 - p)
In our models with geometry (line or 2D grid), we consider that users perform a local search to return their bikes: if a destination is saturated, the user chooses one of the two (or four) neighbors and repeats the operation until she finds an available spot. This implies that the neighbors of a saturated station are likely to receive more bikes than stations not located nearby. Hence, the neighbors of a saturated station are more likely to be saturated than others. This creates local saturation and increases the average number of stations that a user has to visit before being able to return her bike.

We simulate the three models and compute the average number of stations that a user visits before finding an available spot. The results are reported in Figure 9. In Figure 9(a), we plot the average number of visited stations as a function of the fleet size s. This figure is to be compared with Figure 1 and Figure 10 for the one-choice case and with Figure 3 for the two-choice case. The capacity of the station is K = 30. When the number of bikes per station is low (less than 15), there are almost no saturated stations. In this case, users successfully return their bike at their chosen destinations, most of the time. When the number of bikes is close to 30, we observe that the average number of visited stations rises quickly in the case of the line. In all cases, the results are plotted for the four trip-time distributions, but the curves are indistinguishable. For the 2D model, the average number of visited stations is slightly higher than the case without geometry but remains similar.

To ease the comparison between the two metrics, we plot the average number of visited stations as a function of the proportion of saturated stations in Figure 9(b). As indicated before, when the new destination is chosen at random, the average number of visited stations is 1/(1 -p); where p is the proportion of saturated stations. We observe in Figure 9(b) that the 2D grid has a similar behavior as the Average number of stations that have to be visited before returning a bike. We compare the models with and without geometry for different fleet sizes and incentive strategies. Due to the local search, the average number of visited stations grows much faster in the case of a line than for the 2D grid. The 2D grid case is similar to the model without geometry. model without geometry. When the geometry is represented by a line, the number of visited stations is higher but it has the same order of magnitude. In particular, when 30 percent or less of the stations are saturated, the average number of visited stations is lower than 2.5, and lower than twice the one without geometry. We remark that having 30 percent of the stations that are saturated corresponds to an extreme situation 2 . To conclude, our simulations show that a 2D grid exhibits a performance similar to the theory. As the positioning of stations is similar to a 2D grid in many bikesharing systems, this implies that the basic model reflects the behavior of realistic scenarios.

6.4. Adding Features to the Model (Search at Arrival, Shorter Search Time When Returning). The features of the homogeneous model can also be changed, while keeping the model analytically tractable. For example, instead of leaving, a user who arrives at an empty station can randomly visit other stations to find a bike. If the re-attempt times are exponentially distributed with mean 1/λ , then the loss of users or their avoidance of empty stations can be seen as the two extreme cases λ = 0 and λ = +∞. The model can also be modified to take into account that searching for a non-saturated station is faster than traveling.

These modifications do not change the nature of the model: the occupancy of a station is still geometrically distributed. Only the influence of the fleet size s changes. For example, if, when a user returns her bike and finds her first choice saturated, the re-attempt times are exponentially distributed with mean 1/µ , then 2 In our simulation, each station can host up to 30 bikes. Having more than 30 percent of stations that are saturated occurs when there is a fleet of more than 25 bikes per station for the line and more than 30 bikes per station for the 2D grid.

Equation ( 2) is replaced 3 by ( 10)

s = λ µ ρ 1 + ν ρ (K) µ µ -1 + K k=0 kν ρ (k).
It is easy to prove that Equation (10) has a unique fixed point. Thus the limiting stationary distribution of the number of bikes at a station has still a geometric distribution on {0, . . . , K} with parameter ρ solution of Equation [START_REF] Gast | Mean field limit of non-smooth systems and differential inclusions[END_REF]. It allows also to plot (see Figure 10) the proportion of problematic stations as a function of s and to prove that the minimum is also 2/(K + 1) obtained for an optimally reliable size K/2 + λ/µ 1/(K + 1) + λ/µ K/(K + 1), lower than K/2 + λ/µ. Moreover we simulate this model and report the proportion of problematic stations as a function of the fleet size per station s in Figure 10. We plot the results for λ/µ = 1 (Figure 10(a)) and λ/µ = 10 (Figure 10(b)). In each case, we compare the theoretical prediction of Equation ( 10) with a simulation for N = 100 and the two models with geometry presented in Section 6.3. We set µ = 5µ and we vary and compare the four trip-time distributions (exponential, deterministic, log-normal and uniform). In all cases, the trip-time distribution has a negligible effect on the performance: for a given configuration, the relative difference between the proportions of problematic stations is at most 0.15%. The geometry does have an effect, but the overall behavior is similar. As mentioned in Section 6.3, the 3 To see this, the proportion s of bikes per station is the sum of two terms: the mean number of bikes per station K k=0 kνρ(k) and the mean number of riding users per station. This term is the product of the effective arrival rate λ(1 -νρ(0)) times the mean riding time. The mean riding time is 1/µ + (1 -νρ(K)) +∞ k=0 νρ(K) k k/µ because it is the sum of the mean trip time 1/µ and k/µ if the user returns at the (k + 1)-th attempt, i.e. with probability (1 -νρ(K))νρ(K) k . It leads to the result.

performance of the 2D model is similar to the performance of a model without geometry. 6.5. Influence of Truck Capacity. In the redistribution model presented in Section 5, we assume that bikes are moved individually by a truck. This leads to a simple formula for the optimal redistribution rate. In practice, however, bikes are moved by trucks that can contain a few tens of bikes. This section reports simulation results of the model described in Section 6.3 where a truck of capacity C is added. To obtain a fair comparison, the rate at which the truck visits the stations is set inversely proportional to the truck capacity. Hence, with this scaling, having a larger truck capacity leads to a poorer performance: the balance achieved when bikes are moved one by one at rate 10 is better than when bikes are moved ten by ten at rate 1.

The simulated model is composed of N stations that are placed in a 2D grid, as in Figure 7(a). Users move as in the one-choice model of Section 6.3: At each time step, a user arrives at one station picked at random, picks up a bike if this station is not empty, and performs a local search if the targeted destination is saturated. At each time step, with probability γ/C, a truck transports bikes from the station that has the highest number of bikes and places them in the station that has the lowest number of bikes. The truck tries to equalize the number of bikes between the two stations but cannot move more than C bikes at a time. The case C = 1 corresponds to the model described before. The maximum number of bikes per time slot that can be moved by truck does not depend on C and is equal to C(γ/C) = γ. The proportion of problematic stations are reported in Figure 11 for two stations capacities: K = 15 and K = 30. Recall s = K/2. For K = 15, simulation results for C = 1, C = 3 and C = 5 are compared with the theoretical values obtained from the fixed point analysis. For K = 30, simulation results for C = 1, C = 5 and C = 10 are compared with the theoretical values. The vertical lines represent the optimal redistribution rate γ * , obtained from Theorem 3. We observe that the theoretical model (with a truck capacity of one) predicts qualitatively the performance of the simulated models. This prediction is an optimistic estimation of the simulated values. Moreover, as expected, the performance decreases with the truck capacity.

In conclusion, in an homogeneous system, the optimal redistribution rate depends on the capacity of the station and leads to a great improvement of the system performance. It can be shown that combining this redistribution mechanism with the two-choice incentives, introduced in the previous section, leads to an optimal redistribution rate close to O( √ K2 -K/2 ).

Conclusion and Future Work

In this paper, we investigate the influence of the station capacities on the performance of homogeneous bike-sharing systems. Using a stochastic model and a fluid approximation, we provide analytical expressions for the performance. They are summarized in Table 1. The optimal fleet size is approximately K/2 for all models. Without using incentives, the capacity has only a linear effect on the performance or on the optimal redistribution rate. For this purpose, an incentive to return bikes to the least loaded station among two improves dramatically the performance, even if a small proportion of users accept to do this. Moreover, even if this model does not take into account any geographic aspect of the system, simulations show that these results also hold when considering simple geometric models with local interactions.

Minimal proportion of problematic stations

Optimal fleet size s Original model 2/(K + 1) s = K/2 + λ/µ Two-choice √ K2 -K/2 s -λ/µ ∈ [K/2; K -log 2 (K)] Regulation 0 if γ ≥ λ/(K -1) s = K/2 + λ/µ Table 1. Summary of the main results: influence of the station capacity K on the proportion of problematic stations.

Our results prove that the effect of random choices on the performance should not be neglected when studying the performance of a bike-sharing system. Even in a completely balanced system, they dramatically affect the performance. A natural extension of this work is to consider stations with different parameters. The steady-state performance of such a system is given by [START_REF] Fricker | Mean field analysis for inhomogeneous bike sharing systems[END_REF]. It proves that, without repositioning via incentives or trucks, performance is very poor. One interesting question is whether the steady-state performance can be used as a metric in a system with varying operation conditions, such as peak-hours and non-peak hours. Our work can serve as a building block for studying the effect of incentives and redistribution mechanisms. Studying practical implementations of these mechanisms in real-world systems is postponed for future work. Moreover, the transient behavior of such mechanisms in a city where the attractiveness of stations varies over time could be studied.

1

  The capacity of the stations is K = 30. Number of bikes per station: s Proportion of problematic stations λ/µ=0.1 λ/µ=1 λ/µ=10 (b) The capacity of the stations is K = 100.

Figure 1 .

 1 Figure1. Proportion of problematic stations as a function of the number of bikes per station for two values of the size of stations K. On the x-axis is the average number of bike per station s. For both scenarios, we plot λ/µ = 0.1, λ/µ = 1 and λ/µ = 10.

1

  Number of bikes per station: s Proportion of problematic stationsforcing to non-empty/non saturated without forcing

Figure 2 .

 2 Figure 2. Proportion of problematic stations as a function of the number of bikes per station when we force people to go to a nonsaturated station compared to the proportion if we do not force people. Values for K = 30 and λ/µ = 1.

  Proportion of problematic stations as a function of the number of bikes per station s for r = 1 (everyone obeys the rule) and r = 0. obeying the two-choice rule Proportion of problematic stations (b) Proportion of problematic stations as a function of the proportion of users obeying the two-choice rule (the y-axis is in logscale).

Figure 3 .

 3 Figure 3. Performance of the system in a two-choice system: 3(a) when everyone obeys the two-choice rule and the number of bikes per station varies. 3(b): when the number of bikes per station is 16 and r varies ( K = 30 and λ/µ = 1).

5 0 9 0 7 = 1 / 5 Figure 4 .

 597154 Figure 4. Illustration of Theorem 3: distribution of station occupancy. The station capacity is K = 10. Two fleet sizes s = 5 and s = 7 and three redistribution rates γ = 0, γ = 1/9 and γ = 1/5 are compared.

1 )

 1 Original model -The trip times are exponentially distributed with mean 1/µ. (2) Deterministic -The trip times are all equal to 1/µ. (3) Log-normal -The trip times follow a log-normal distribution with mean and standard deviation 1/µ. (4) Uniform -The trip times are uniformly distributed on [0; 2/µ].

= 10 Figure 5 .

 105 Figure 5. Difference between the proportion of problematic stations when the trip follows another distribution minus the one when the trip follows an exponential distribution. The vertical bars indicate the 95% confidence interval for the mean.

Figure 6 .

 6 Figure 6. Two-choice model where the users choose their destination before riding their bike: proportion of problematic stations as a function of the average trip duration. The performance degrades as the average trip time increases. We compare the four distribution of trip times. For the one-choice model, the performance does not depend on the trip-time distribution.

  local search if saturated (a) 2D grid of N stations.

  local search if saturated (b) Line of N stations.

Figure 7 .

 7 Figure 7. Influence of the local search for the one-choice model. Proportion of problematic stations as a function of the station's capacity K for two geometric models: 2D grid and the line. The parameters are s = K/2 and N = 25, 10, 400.

  Two-choice model on a 2D grid of N stations. least loaded of two neighbors (b) Two-choice model on a line.

Figure 8 .

 8 Figure 8. Influence of geometry on the two-choice model. Proportion of problematic stations as a function of the station's capacity K for the 2D grid and the local search.

  ave number of visited stations (return) 1D line (one or two-choice) one-choice (no-geometry or 2D grid) two-choice (no-geometry or 2D grid) no geometry 1D line 2D grid (a) Average number of visited stations before returning as a function of the fleet size s. Average number of visited stations as a function of the proportion of saturated stations.

Figure 9 .

 9 Figure 9. Average number of stations that have to be visited before returning a bike. We compare the models with and without geometry for different fleet sizes and incentive strategies. Due to the local search, the average number of visited stations grows much faster in the case of a line than for the 2D grid. The 2D grid case is similar to the model without geometry.

10 Figure 10 .

 1010 Figure 10. Proportion of problematic stations as a function of the fleet size s when the search around a saturated destination are 5 times faster that trip time (µ = 5µ). The results are ploted for the four trip-time distributions but the curves are indistinguishable (they are within 0.15%).

Figure 11 .

 11 Figure 11. Proportion of problematic stations as a function of the redistribution rate γ/λ. We compare the theoretical analysis with simulations for various truck capacities. The theoretically optimal redistribution rate is γ * = 1/(K -1).

  Proportion of the N stations where k or more bikes are available at t.

	ȳ	Equilibrium point of the corresponding ODE.
	U N k (t) u k (t)	Limit of U N k (t) as N tends to infinity (described by an ODE).
	ū	Equilibrium point of the corresponding ODE.
	2.2. Homogeneous Bike-Sharing Model.
	2.1. Main Notation List.
	N	Number of stations.
	s	Average number of bikes per station (the total number of bikes is sN ).
	K	Number of slots in a station, also called capacity of the station.
	λ	Arrival rate of users at a station.
	1/µ	Average trip time.
	Y N

k (t) Proportion of the N stations where k bikes are available at time t. y k (t) Limit of Y N k (t) as N tends to infinity (described by an ODE).

This work is partially supported by the EU project QUANTICOL, 600708.