Ariel Waserhole

Vincent Jost

Vehicle Sharing System Pricing Regulation: A Fluid Approximation

We study self regulation through pricing for Vehicle Sharing Systems (VSS). Without regulation VSS have poor performances. We study possible improvements of the VSS using (pricing as) incentive. We take as base model a Markovian formulation of a closed queuing network with finite buffer and time dependent service time. This model is unfortunately intractable for the size of instances we want to tackle. We present a fluid approximation constructed by replacing stochastic demands by a continuous deterministic flow (keeping the demand rate). It gives a deterministic and continuous dynamics and evolves as a continuous process. The fluid model can be thought of as the limit of a scaled Markovian model, in which the fleet, the station capacities and the demands are scaled by a common factor. A reusable benchmark and an experimental protocol is created for the general Vehicle Sharing System optimization problem. We discuss the convergence of the scaled model to the fluid limit. We conduce some experimental studies.

Introduction

1.1 Context [START_REF] Shoup | The High Cost of Free-Parking[END_REF] reports that, based on a sample of 22 US studies, car drivers looking for a parking spot contribute to 30% of the city traffic. Moreover cars are used less than 2 hours per day on average but still occupy a parking spot the rest of the time! Could we have less vehicles and satisfy the same demand level?

Recently, the interest in Vehicle Sharing Systems (VSS) in cities has increased significantly. Indeed, urban policies intend to discourage citizens to use their personal car downtown by reducing the number of parking spots, street width, etc. VSS seem to be a promising solution to reduce jointly traffic and parking congestion, noise, and air pollution (proposing bikes or electric cars). They offer personal mobility allowing users to pay only for the usage (sharing the cost of ownership ).

We are interested in short-term one-way VSS where vehicles can be taken and returned at different places (paying by the minute). Associated with classic public transportation systems, short-term one-way VSS help to solve one of the most difficult public transit network design problem: the last kilometer issue [START_REF] Demaio | Bike-sharing: History, impacts, models of provision, and future[END_REF]. Round-trip VSS, where vehicles have to be returned at the station where they were taken, cannot address this important issue.

The first large-scale short-term one-way VSS was the bicycle VSS Vélib' (2007). It was implemented in Paris in 2007 and now has more than 1200 stations and 20 000 bikes selling around 110 000 trips per day. It has inspired several other cities all around the world; Now more than 300 cities have such a system, including Montréal, Bejing, Barcelona, Mexico City, Tel Aviv [START_REF] Demaio | Bike-sharing: History, impacts, models of provision, and future[END_REF].

One-way Vehicle Sharing Systems: a management issue

One way systems increase the user freedom at the expense of a higher management complexity. In round trip rental systems, while managing the yield, the only stock that is relevant is the number of available vehicles. In one-way systems, vehicles are not the only key resource anymore: parking stations may have limited number of spots and the available parking spots become an important control leverage.

Since first bicycle VSS, problems of bikes and parking spots availability have appeared very often. Reasons are various but we can highlight two important phenomenons: the gravitational effect which indicates that a station is constantly empty or full (as Montmarte hill in Vélib' (2007)), and the tide phenomenon representing the oscillation of demand intensity along the day (as morning and evening flows between working and residential areas).

To improve the efficiency of the system, in the literature, different perspectives are studied. At a strategic level, some authors consider the optimal capacity and locations of stations. [START_REF] Shu | Bicycle-sharing system: Deployment, utilization and the value of re-distribution[END_REF] propose a stochastic network flow model to support these decisions. They use their model to design a bicycle VSS in Singapore based on demand forecast derived from current usage of the mass transit system. [START_REF] Lin | Strategic design of public bicycle sharing systems with service level constraints[END_REF] consider a similar problem but formulate it as a deterministic mathematical model.

At a tactical level, other authors investigate the optimal number of vehicles given a set of stations. [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF] study the fleet sizing problem with constant demand and no parking capacity. Fricker and Gast (2012), Fricker et al. (2012) consider the optimal sizing of a fleet in "toy" cities, where demand is constant over time and identical for every possible trip, and all stations have the same capacity K. They show that even with an optimal fleet sizing in the most "perfect" city, if there is no operational system management, there is at least a probability of 2 K+1 that any given station is empty or full. At an operational level, in order to be able to meet the demand with a reasonable standard of quality, in most bicycle VSS, trucks are used to balance the bikes among the stations. The objective is to minimize the number of users who cannot be served, i.e., the number of users who try to take a bike from an empty station or to return it to a full station. The problem is to schedule truck routes to visit stations performing pickup and delivery. In the literature many papers deal already with this problem. A static version of the bicycle VSS balancing problem is treated in [START_REF] Chemla | Bike sharing systems: Solving the static rebalancing problem[END_REF] and a dynamic one in [START_REF] Contardo | Balancing a dynamic public bike-sharing system[END_REF].

A study on leverage for self regulated VSS

A new type of VSS has appeared lately: one-way Car VSS with Autolib' (2011) in Paris and Car2go (2008) in more than 10 cities (Vancouver, San Diego, Lyon, Ulm...). Due to the size of cars, operational balancing optimization through relocation with trucks seems inappropriate. Another way for optimizing the system has to be found.

This study is part of a work investigating different optimization leverage for self regulation in VSS. Using operation research we want to estimate the potential impact of:

• Optimizing the system design (station capacity, fleet size);

• Using pricing techniques to influence user choices in order to drive the system towards its most efficient dynamic;

• Establishing new protocols, for instance with parking spot reservations and/or users spatial and temporal flexibility.

Regulation through pricing

The origin of Revenue Management (RM) lies in airline industry. It started in the 1970s and 1980s with the deregulation of the market in the United States. In the early 1990s RM techniques were then applied to improve the efficiency of round trip Vehicle Rental Systems (VRS), see [START_REF] Carroll | Evolutionary change in product management: Experiences in the car rental industry[END_REF] and [START_REF] Geraghty | Revenue management saves national car rental[END_REF]. One way rental is now offered in many VRS but usually remains much more expensive than round trip rental. One way VRS RM problem literature is recent. [START_REF] Haensela | Revenue management in the car rental industry: A stochastic programming approach[END_REF] model a network of round trip car VRS but with the possibility of transferring cars between rental sites for a fixed cost.

For trucks rental on the contrary, companies such as Rentn'Drop in France or Budget Truck Rental in the United States are specialized in the one way rental offering dynamic pricing. This problem is tackled by [START_REF] Guerriero | Revenue management policies for the truck rental industry[END_REF] that consider the optimal managing of a fleet of trucks rented by a logistic operator, to serve customers. The logistic operator has to decide whether to accept or reject a booking request and which type of truck should be used to address it.

Results for one way VRS are not directly applicable to VSS, because they differ on several points: 1) Renting are by the day in VRS and by the minute in VSS with a change of scale for the demand time tolerance; 2) One way rental is the core in VSS (for instance only 5% of round trip rental in Bixi [START_REF] Morency | Insight into the Montreal bikesharing system[END_REF]), and it is classically the opposite in car VRS; 3) There is usually no booking in advance in VSS, it is a first come first served rule, whereas usually trips are planned several days in advance in VRS. At the best of our knowledge there is no results in the RM literature dedicated to pricing in VSS.

2 Model: An intractable Markov Decision Process

Restriction to a simple protocol

In a real context, a user wants to use a vehicle to take a trip between an original (GPS) location a, and a final one b, In a real context, a user wants to use a vehicle to take a trip between an original (GPS) location a, and a final one b, during a specified time frame. On a station based VSS, he tries to find the closest station to location a with a vehicle to take and the closest station to location b with a parking spot to retrieve it. All along this process user's decisions rely on several correlated inputs such as: trip total price, walking distance, public transportation competition, time frame... A time elastic GPS to GPS demand forecast, linked to a user's behavior decision protocol choosing its origin/destination stations and time frame seems closer to reality but introduces a big complexity (the use of utility function for instance). Therefore, in this study we are going to consider a simple station to station demand forecast with real time reservation for a specified trip. When a user takes a vehicle he has to engage himself to retrieve the vehicle at a specified time to a destination station. In counterpart the system reserves him a parking spot to ensure the feasibility of his trip. Having such reservation protocol simplifies greatly the system specification because it avoids to define the user's behavior when trying to drop a vehicle at a full station. Finally, it amounts to considering a demand for the following simplified protocol:

1. A user asks for a vehicle at station a (here and now), with destination b and rental duration µ -1 a,b ; 2. The system offers a price (or rejects the user = infinite price); 3. The user accepts the price, pays, takes the vehicle and a parking spot is reserved in b or leaves the system.

A Vehicle Sharing System Stochastic Model

Stochastic framework

We define now a framework to model a stochastic VSS with the protocol defined in the Section 2.1. In a city, there is is a fleet of N vehicles and a set M (|M| = M) of stations with capacity K a , a ∈ M. There is an elastic demand D = M × M between each station. This demand is periodic piecewise constant on a set T of time steps. . Before going to the destination station (server) b, the vehicle (job) passes by a transportation state (infinite server) (a -b) with a service rate proportional to the number of vehicles n a,b already in transit (in the buffer): n a,b µ t a,b . To represent the reservation of parking spot at destination, there is a constraint linking the buffer capacities of server a and of servers (b -a) representing vehicles in transportation towards a:

K ′ a + b∈M K ′ b,a ≤ K a .
A way to imagine it is to consider that vehicles in transit occupy already a parking spot at destination:

K ′ a = K a -b∈M n b,a ≥ 0. a a-a b-a b-b b a-b K ′ a,b K ′ a,a K ′ b,b K ′ b,a K ′ a K ′ b λ t b,a λ t a,b λ t a,a λ t b,b n a,a µ t a,a

Continuous-time Markov chain formulation

Assuming that all durations follow exponential distributions, the stochastic VSS model becomes Markovian. If a price p t a,b is set for all trips (a, b) ∈ D at all time steps t ∈ T , the closed queuing network can be formulated as a continuous-time Markov chain on a set S of states: • The changing between two piecewise constant demand time steps giving a transition rate τ t between states (. . . , t) and states (. . . , t + 1 mod|T |).

S = n a ∈ N : a ∈ M, n a,b ∈ N : (a, b) ∈ D, t ∈ T / i∈M∪D n i = N & n a + b∈M n b,a ≤ K a , ∀a ∈ M, ∀t ∈ T . A state s = (n a : a ∈ M,
Note that there is an exponential number of states: For one time-step, without transportation time and with infinite station capacities there are N +M -1 N states. For instance for a relatively small system with N = 150 vehicles and M = 50 stations it already gives roughly 10 47 states!

Model optimization

Stochastic VSS pricing problem

We want to maximize the VSS average revenue. We use as leverage the possibility to change the price to take a trip which will, assuming an elastic demand, influence the demand for such trip. Seeing the VSS as a closed queuing network, its evolution can be described explicitly through a continuous-time Markov chain. This VSS Markovian model is our reference to evaluate a policy. We call this problem the stochastic VSS pricing problem. Prices can be discrete, i.e. selected in a set of possibilities, or continuous i.e. chosen in a range. Pricing policies can be dynamic, i.e. dependent on system's state (vehicles distribution), or static i.e. independent on system's state, set in advance and only function of the trip.

Markov Decision Process curse of dimensionality

The continuous-time Markov chain of the VSS Markovian model leads to a Markov Decision Process (VSS MDP model). There is a set Q of possible discrete prices for each trip at each time step. A trip (a, b) ∈ D at price p q a,b , q ∈ Q has a demand (transition rate) λ a,b (p q a,b ) = λ q a,b . Solving the VSS MDP model computes the best dynamic system state dependent discrete pricing policy. MDPs are known to be polynomially solvable in the number of states |S| and the number of actions |A| available in each state. There exists efficient solutions methods such as value iteration, policy iteration algorithm or linear programming, we refer to [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] textbook.

The VSS MDP model is a pricing problem where the action space A(s) in each state s ∈ S is the Cartesian product of the available prices for each trip, i.e. A(s) = Q M . However, to avoid suffering from this exponential explosion, we can model this problem as an Action Decomposable Markov Decision Process (Waserhole et al., 2012b). It is a general method based on the eventbased dynamic programming [START_REF] Koole | Structural results for the control of queueing systems using event-based dynamic programming[END_REF] to reduce the complexity of the action space to

A(s) = Q × M.
However, there is another problem with the VSS MDP model, the explosion of the state space with the number of vehicles and stations. This phenomenon is known as the curse of dimensionality. The VSS Markovian model can be efficiently evaluated though Monte-Carlo simulation however for its optimization we have to look at approximations or simplifications to produce solutions in a reasonable time.

Literature review

VSS stochastic optimization In the VSS literature, only simple forms of this closed queuing network model with the relationship to the underlying continuous-time Markov chain have been studied. George and Xia (2011) consider a VSS with only one time step (stable demand), one price (no pricing) and infinite station capacities. Under these assumptions, they establish a compact form to compute the system performance using the BCMP network theory [START_REF] Baskett | Open, closed, and mixed networks of queues with different classes of customers[END_REF]. They solve an optimal fleet sizing problem considering a cost to maintain a vehicle and a gain to rent it. Fricker and Gast (2012) consider simple cities that they call homogeneous. These cites have a unique fixed station capacity (K a = K), a stable (one time step) arrival rate, uniform routing matrix (λ t a,b = λ M ) and a unique travel time (µ t a,b

-1 = µ -1
). With a mean field approximation, they obtain some asymptotic results when the number of stations tends to infinity (M → ∞): if there is no operational regulation system, the optimal sizing is to have a fleet of K 2 + λ µ vehicles per station which corresponds in filling half of the stations plus the average number of vehicles in transit ( λ µ ). Moreover, they show that even with an optimal fleet sizing, each station has still a probability 1 K+1 to be empty or full which is pretty bad since these cities are perfectly balanced. In another paper, Fricker et al. (2012) extend to inhomogeneous cities modeled by clusters some analytical results and verify experimentally some others.

For homogeneous cities, Fricker and Gast (2012) also study a heuristic using incentives called "the power of two choices" that can be seen as a dynamic pricing. When a user arrives at a station to take a vehicle, he gives randomly two possible destination stations and the system is directing him to the least loaded one. They show that this policy allows to drastically reduce the probability to be empty or full for each station to 2 -K 2 . Finally, none of these models dedicated to VSS includes time-varying service demands, pricing or full heterogeneity.

Queuing network with time-varying rates

There is a wide literature on queuing networks and MDPs. We refer to the textbooks of [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] or [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF] to provide the foundation for using MDP for the exact optimization of stationary queueing systems. We focus here our review here on time-varying rates for the average reward criterion.

In the literature, queuing networks with time-dependent parameters are called either dynamic rates queues, time varying rates queues or unstationnary queues. When dealing with Markovian systems we also speak about inhomogenous MDP (in opposition to classic MDP called homogeneous). There are many researchers who have extended the MDP framework to develop policies for nonhomogeneous stochastic models with infinite actions spaces. [START_REF] Yoon | Optimal pricing and admission control in a queueing system with periodically varying parameters[END_REF] consider both pricing and admission controls for a multiserver queue with a periodic arrival and service rate over an infinite time horizon. They use a pointwise stationary approximation [START_REF] Green | The pointwise stationary approximation for queues with nonstationary arrivals[END_REF] of the queueing process: an optimization problem is solved over each disjoint time interval where stationarity is assumed. In his PhD thesis, [START_REF] Liu | Many-Server Queues with Time-Varying Arrivals, Customer Abandonment and Non-Exponential Distributions[END_REF] develops deterministic heavy-traffic fluid approximations for many-server stochastic queueing models. His main focus is on systems that have time-varying general arrival rates and service-times distributions.

Blocking effect

When considering queuing networks with finite capacities arises blocking effects when a queue is full. [START_REF] Balsamo | Analysis of queueing networks with blocking[END_REF] define various blocking mechanisms. [START_REF] Osorio | An analytic finite capacity queueing network model capturing the propagation of congestion and blocking[END_REF] review the existing models and present an analytic queueing network model which preserves the finite capacity of the queues and uses structural parameters to grasp the between-queue correlation.

Blocking mechanisms differ either in the moment the job is considered to be blocked (before or after-service) or in the routing mechanism of blocked jobs. For our VSS queuing network model, we have to distinguish two cases depending on the rental reservation policy:

• If there is no parking spot reservation, when a user tries to return a vehicle at a full station we are facing a Repetitive Service Blocking (RS). Two solutions might be investigated then: 1) Either the user can choose a new destination independently from the one he had selected previously, until he finds one not full. This is know as RS-RD (random destination). It is the blocking mechanism chosen by Fricker and Gast (2012). 2) Or if he can't modify the destination station, he has to wait for a free parking spot. This is known as RS-FD (fixed destination).

• If the user has to reserve a parking spot at destination, the blocking mechanism is of type Blocking Before Service (BBS). However, in our case, when considering transportation times, reserving a parking spot at destination imply a non usual constraint linking the capcity of the transportation time queues and the station queues as explained in the Section 2.2.2.

A Fluid Approximation

The fluid model is constructed by replacing the stochastic demands by a continuous flow with the corresponding deterministic rate. It gives a deterministic and continuous dynamics and evolves as a continuous process. Optimizing the fluid model to give heuristics on the stochastic model is a well know technique. It is derived as a limit under a strong-law-of-large numbers, type of scaling, as the potential demand and the capacity grow proportionally large [START_REF] Gallego | Optimal dynamic pricing of inventories with stochastic demand over finite horizons[END_REF].

Applications of this principle are available in the literature to deal with revenue management problems, see [START_REF] Maglaras | Revenue management for a multiclass single-server queue via a fluid model analysis[END_REF] for instance. However, to the best of our knowledge, there is no direct approach available for a general case including our application. Nevertheless, there are some papers on theorizing the fluid approximation scheme: Meyn (1997) describes some approaches to the synthesis of optimal policies for multiclass queueing network models based upon the close connection between stability of queueing networks and their associated fluid limit models; [START_REF] Bäuerle | Optimal control of queueing networks: An approach via fluid models[END_REF] generalizes it to open multiclass queueing networks and routing problems.

To sum up, what goes out of all studies is that the fluid model might not be easily constructed and, even if found, the convergence might not be trivial to prove. Sometimes, little modifications called tracking policy have to be made on the solution to be asymptotic optimal or simply feasible but, in any case, the fluid approximation is known to give a good approximation and also an upper bound on optimization [START_REF] Bäuerle | Asymptotic optimality of tracking policies in stochastic networks[END_REF].

The Fluid Model

A plumbing problem

The fluid approximation can be seen as a plumbing problem. Stations are represented by tanks connected by pipes representing the demands. Vehicles are considered as a continuous fluid evolving in this network. The volume of a tank represents the capacity of a station. The length of a pipe represents the transportation time between two stations. The section of a pipe between two tanks a and b represents the demand between stations a and b, it ranges over time from 0 to the maximum demand Λ t . Figure 2 schemes an example with 2 stations. We model a system that has no dynamic interaction with the user. The decisions are static and have to be taken before, once for all. They amount to setting the width of a pipe by changing the price to pass flow in it: the higher the price is, the smaller the pipe (demand) will be.

For a given policy (prices/demands) the deterministic evolution of the system is defined by different constraints. First, if a pipe (a demand) exists and there is some flow (vehicles) available in the tank (station), according to gravity first come first serve law : the flow has to pass through the pipe until no flow is availabl and if there is not enough flow to fulfill all pipes (demands), there should be some equity between them. In other words, the proportion of filling up of all pipes should be equal. Secondly, if it the arrival tank of a pipe is full, it might be impossible to fulfill this pipe. In this case, another equity rule should be applied to all pipes discharging into this tank. In other words, for each pipe, if its discharging tank is full, it has the same proportion of filling up as the other pipes discharging in this tank, otherwise, it has the same proportion of filling up as the other pipes coming from its source tank. We call equity issues the problem of respecting the arrival departure equity to model the evolution of the flow.

λ t a,b λ t b,a K a K b µ b,a -1 Control Station a Station b
Figure 2: A Plumbing Problem.

The model

In the Appendix A, we propose a mathematical formulation for a discrete controls (prices) fluid optimization. However, this formulation is rather complicated, and it seems complex to model the evolution of the fluid process for discrete prices. Indeed, for a fixed price and finite station capacities, the equity issues between arrival and departure give a non linear dynamic. An example is provided in the Appendix A.

To avoid dealing with the equity issues, we develop a continuous pricing fluid optimization model. The trick is to always fill the pipes, in other words to set the flow between two stations exactly to the demand for taking this trip. Let Λ t a,b be the maximum demand of users that want to take a trip at time step t between stations a and b. If we assume that there exists a price p(λ t a,b ) to obtain any demand λ t a,b ∈ [0, Λ t a,b ], with a proper price selection it becomes always possible to fill all pipes. In a nutshell, it amounts to considering that the demand is continuous and surjective in [0, Λ t a,b ]. An example is schemed Figure 3. Note it is possible that the maximum demand Λ can be obtained with the minimum price that is negative if the system pays the user. More formally we can define the fluid model for continuous prices as follows:

Continuous price fluid model:

• A continuous space replaces the discrete one:

S F = n a ∈ R : a ∈ M, n a,b ∈ R : (a, b) ∈ D, t ∈ [0, T ] / i∈M∪D n i = N & n a + b∈M n b,a ≤ K a , ∀a ∈ M, ∀t ∈ [0, T ] .
• A continuous flow with deterministic rate λ t a,b replaces the discrete stochastic demand.

• A deterministic transportation time of duration µ t a,b -1 replaces the stochastic one.

• A continuous control on the prices p t a,b implies an admission of a deterministic demand flow

λ t a,b ∈ [0, Λ t a,b ].
In the literature, e.g. [START_REF] Maglaras | Revenue management for a multiclass single-server queue via a fluid model analysis[END_REF], it is classic to interpret this model as an asymptotic limit of a s-scaled problem sequence.

s-scaled stochastic continuous pricing problem:

• A scaled discrete space, with R := {1, . . . , s} and for any set X:

X s = { 1 s , 2 s , . . . , |X|}: S(s) = n a ∈ N s : a ∈ M, n r a,b ∈ N s : ((a, b), r) ∈ D × R, t ∈ T s / i∈M∪D×R n i = N & n a + r∈R b∈M n r b,a ≤ K a , ∀a ∈ M, ∀t ∈ T s .
• The state space now contains fractions instead of integers and the basic unit corresponding to a vehicle (job) and a time step is 1/s.

• Each time step is divided in s parts with duration following a general distribution with mean (sT ) -1 .

• The route and the transportation times from station a to station b is represented by s servers in series with rate µ t,r a,b (s) = sµ t a,b .

• The maximum time-varying transition rates are accelerated by a factor s: Λ t a,b (s) = sΛ t a,b . • There is a continuous control on the prices for each trip, at each time step. Any demand

λ t a,b (s) ∈ [0, Λ t a,b (s)] can be obtained at a price p t a,b (s) = 1 s p t a,b (f rac1sλ t a,b (s)).
The above scaling allows the convergence of not only the rewards, but also of the state process.

SCSCLP formulation

We build now a mathematical programming model for the fluid approximation of the stochastic VSS pricing problem with continuous prices.

A Continuous Quadratic Program

For all time t ∈ [0, T ], we define the following variables: the available stock at station a; r a (t) the number of parking spots reserved at station a.

We build now a Continuous Quadratic Program (CQP) giving the policy maximizing the system revenue. We use the trick to set the prices p such that, at any time, the demand λ is exactly equal to the flow y passing between two stations, i.e. y t a,b = λ t a,b .

Fluid CQP (1)

max (a,b)∈D T 0 λ a,b (t) × price(λ a,b (t)) dt (Gain) (1a) s.t. a∈M s a (0) = N, (Flow initialization) (1b) s a (0) = s a (T ), ∀a ∈ M, (Flow stabilization) (1c) s a (t) = s a (0) + t 0 (b,a)∈D λ b,a (θ -µ -1 b,a ) -λ a,b (θ) dθ, ∀a ∈ M, ∀t ∈ [0, T ], (Flow conservation) (1d) 0 ≤ λ a,b (t) ≤ Λ t a,b , ∀a, b ∈ M, ∀t ∈ [0, T ], (Max demand) (1e) r a (t) = b∈M µ -1 b,a 0 λ b,a (t -θ) dθ, ∀a ∈ M, ∀t ∈ [0, T ], (Reserved Park Spot) (1f) s a (t) + r a (t) ≤ K a , ∀a ∈ M, ∀t ∈ [0, T ], (Station capacity) (1g) s a (t) ≥ 0, r a (t) ≥ 0, ∀a ∈ M, ∀t ∈ [0, T ], (1h)
Equation (1b) initializes the flow with the N vehicles available. Equations (1c) constrain the solution to be stable, i.e. cyclic over the horizon. Equations ( 1d) is a continuous version of the classic flow conservation. Equations (1e) constrain the flow on a demand edge to be less or equal than the maximum demand. Equations (1f) set the reserved parking spot variable. Equations (1g) constrain the maximum capacity on a station and the parking spot reservation: For a station the number of reserved parking spots plus the number of vehicles already parked should not exceed its capacity.

Note that this model assumes that there is an "off period" between the cycling horizons where all vehicles are parked at a station. However, if it is not the case, only some small changes have to be made in the flow equations.

Literature review on Continuous Linear Program

Because the CQP (1) is not linear, it is hard to solve as it is. To obtain an efficient solutions technique, in the next section we transform CQP (1) into a special call of Continuous Linear Programs (CLP).

CLP are introduced by [START_REF] Bellman | Bottleneck problems and dynamic programming[END_REF]. Although many studies have been made on general CLP, they remain difficult to solve exactly [START_REF] Anderson | Linear programming in infinite-dimensional spaces: theory and applications[END_REF]. Recently [START_REF] Bampou | Polynomial approximations for continuous linear programs[END_REF] propose a generic approximation scheme for CLP, where they approximate the policies by polynomial and piecewise polynomial decision rules. Fluid relaxations are a specially structured class of CLP called State Constrained Separated Continuous Linear Programs (SCSCLP). [START_REF] Luo | A new algorithm for state-constrained separated continuous linear programs[END_REF] introduce SCSCLP, establish strong duality, and proposed a convergent class of algorithms for this problem. Their algorithm is based on time discretization and removes redundant breakpoints but, solves quadratic programs in intermediate steps. The complexity of solving SCSCLP is still open, in fact, the size of the optimal solutions may be exponential in the input size. In the absence of upper bounds on storage, SCSCLP are called Separated Continuous Linear Programs (SCLP). [START_REF] Ej Anderson | Some properties of a class of continuous linear programs[END_REF] characterize extreme point solutions of SCLP. For problems with linear data, they show the existence of an optimal solution in which the flow-rate functions are piecewise constant with a finite number of pieces. [START_REF] Weiss | A simplex based algorithm to solve separated continuous linear programs[END_REF] presents an algorithm which solves SCLP in a finite number of steps, using an analog of the simplex method. [START_REF] Fleischer | Efficient algorithms for separated continuous linear programs: the multicommodity flow problem with holding costs and extensions[END_REF] provide a polynomial time algorithm with a provable approximation guaranty for SCLP.

A SCSCLP for transit optimization

Assuming a continuous surjective demand, to maximize the average number of trips sold by the system, we can consider an implicit pricing. The optimization problem amounts then only to setting the demand λ ∈ [0, Λ] in order to maximize the throughput of the system. In this approach we let to an economist the task to set the proper price in order to obtain a demand of λ.

To obtain a CLP that maximizes the number of trips sold, we change the objective function of CQP (1) and keep all its constraints since they linear. It gives the following SCSCLP program. (Fluid linear dynamic) (2b)

An approximate SCSCLP for revenue optimization

If the price/demand function gives a concave gain function, to maximizes the revenue of the system, we can make a linear approximation of CQP (1) and obtain an approximate SCSCLP.

Approximate Fluid SCSCLP -Revenue maximization

max (a,b)∈D T 0 gain a,b (t) dt (Gain) s.t. gain a,b (t) ≤ a 1 (a, b, t) × λ a,b (t) + b 1 (a, b, t) . . . a k (a, b, t) × λ a,b (t) + b k (a, b, t) ( gain a,b (t) ≤ λ a,b (t) × price(λ a,b (t))) (1b) -(1h).
(Fluid linear dynamic)

Discussion

Advantages/Drawbacks of fluid approach

The main advantage of this model is to consider time dependent demands providing a macro management of the tide phenomenon. It gives static policies but may also help designing dynamic ones [START_REF] Maglaras | Dynamic pricing strategies for multiproduct revenue management problems[END_REF], a simple way is to make a multiple launch heuristic.

To provide an efficient solution method for the revenue maximization, we assumed a continuous surjective demand function and a concave gain. For instance p(λ) = λ -α with α ∈ [0, 1]. Nevertheless, if we tolerate randomized pricing policy, our solutions technique can works for general demand functions.

A weakness of this approach is that there is no control on the static policy time step. Indeed, the optimal solution might lead to change the price every 5 minutes which seams not suitable in practice. Moreover, since it is a deterministic approximation, this model doesn't take into account the stochastic aspect of the demand. We suspect that for stations with small capacities, it can be a problem since the variance of the demand could often lead to the problematic states: empty or full.

Questions & Conjectures

Fluid model as an asymptotic limit To the best of our understanding, CQP (1) is a fluid approximation of the VSS stochastic problem. It is classic to formulate it as the asymptotic limit of a s-scaled problem when s → ∞. In simulation (Section 4.4), Fluid SCSCLP (2) seams to converge toward the s-scaled problem defined in the Section 3.1.2. However, we don't have any mathematical proof of such convergence.

Conjecture 1 Static optimal policies (and their values) of the s-scaled problem converge toward optimal policies of fluid model CQP (1) when s → ∞.

Fluid model as an upper bound One would expect that the uncertainty in sales in the stochastic problem results in lower expected revenues. It is shown in many applications, as in [START_REF] Gallego | Optimal dynamic pricing of inventories with stochastic demand over finite horizons[END_REF]. However, for our application, as we show in the next section, we have been able to prove that the fluid optimal value function gives an upper bound only for stable demands.

Conjecture 2 The value of CQP (1) optimal solution is an upper bound on dynamic policies of the s-scaled problem (∀s).

Note that if Conjecture 1 and 2 are verified, it implies that static policies given by CQP (1) are asymptotically dominant over dynamic ones for the s-scaled problem when s → ∞.

Stable demand case

If we consider a stable demand (λ t = λ), the steady-state fluid model can be reduced to the following LP (3).

Stable demand fluid LP

(3) max (a,b)∈D λ a,b (Transit) (3a) s.t. (a,b)∈D λ a,b = (b,a)∈D λ b,a , ∀a ∈ M, (Flow conservation) (3b) 0 ≤ λ a,b ≤ Λ a,b , ∀(a, b) ∈ D, (Maximum Demand) (3c) (a,b)∈D 1 µ a,b λ a,b ≤ N, (Nb. of vehicles) (3d) b∈M 1 µ a,b λ a,b ≤ K a , ∀a ∈ M. (Station capacity) (3e)
The objective function (3a) maximizes the throughput. Equations (3b) preserve the flow conservation. Equations (3c) constrain the maximal demand on each trip. Equation (3d) constrains the number of vehicles in the system belong Little's law. Equations (3e) constrain the reservation of parking spot with respect to the station capacity.

To understand better stable demand fluid LP (3), a more natural formulation is to consider explicitly where are all the N vehicles: either in a station, represented by variables s a > 0; or in transit, no more than 1 µ a,b λ a,b at the same time for trip (a, b). The number of vehicles in the system and the parking spot reservation constraints can be then represented by the following equations:

(a,b)∈D 1 µ a,b λ a,b + a∈M s a = N, b∈M 1 µ a,b λ a,b + s a ≤ K a , ∀a ∈ M.
However, if N ≤ a∈M K a , these equations are defining the same space as Equation ( 3d) and (3e).

Theorem 1 For stable demands, stable demand fluid LP (3) optimal value function gives an upper bound on dynamic policies.

Proof : We show that we can construct from any dynamic policies a solution of stable demand fluid LP (3) with same value. Consider a dynamic pricing policies (state dependent) implying a continuous-time Markov chain with for all state s ∈ S a transition rates λ s a,b ≤ Λ a,b for trip (a, b) ∈ D. Under this policy, the system is stationary and ergodic under very general conditions. Therefore, we can look at its stationary distribution π on its state space S that satisfies the following equations: The average throughput of the system is equal to (a,b)∈D λ ′ a,b . λ ′ satisfies the flow conservation constraints and the capacity constraints of the stable demand fluid LP (3):

(a,b)∈D λ ′ a,b = (b,a)∈D λ ′ b,a , ∀a ∈ M, 0 ≤ λ ′ a,b ≤ Λ a,b , ∀(a, b) ∈ D.
Flow conservation constraints are respected because otherwise it would mean that in the dynamic policy's stationary state, a station receives more vehicles that it is sending which is absurd. The capacity constraints are also respected since s∈S π s = 1. The constraints regarding the number of vehicles available and the reservation with respect to the station capacities are also trivially respected in the continuous-time Markov chain:

(a,b)∈D 1 µ a,b λ ′ a,b ≤ N, b∈M 1 µ a,b λ ′ a,b ≤ K a , ∀a ∈ M.
Finally, λ ′ a,b is solution of stable fluid demand LP (3) with the same objective value. It proves that stable demand fluid LP ( 3) is an upper bound on any dynamic policies.

For time-varying demand we can use stable fluid LP (3) to make a pointwise stationary approximation heuristic [START_REF] Green | The pointwise stationary approximation for queues with nonstationary arrivals[END_REF]. It won't give an upper bound anymore, however, it is an heuristic policy easy to compute.

Remark 1 For infinite capacities, when the number of vehicles tends to infinity, stable fluid LP (3) amounts to solving a Maximum Circulation problem. Waserhole and Jost (2012) show that Maximum Circulation gives the best dynamic policy when the number of vehicles tends to infinity.

Simulation

To measure the real performance of our optimization strategies, we would need the have access to the VSS global demand. However, the only precise data available are the trips sold by current systems. The unserved demand is hidden and it is an issue to build it from the exploitation data (a problem of censored demand). Anyway, even if rebuild, new leverage such as pricing or reservation protocol are hard to estimate. It involves complex psychological, social and economical issues. We would need real life experiments to validate our strategies. Moreover, these experiments are expensive so we have a need to roughly estimate their impacts. Therefore, we propose in this article a simple benchmark to evaluate and compare different regulation strategies. The instances composing it are toy cities, simple on purpose, in order to understand and isolate the impact of the different characterized phenomenons.

Creation of benchmark

Sources

In the literature, many data-mining studies have been done on bike VSS such as [START_REF] Côme | Model-based clustering for BSS usage mining: a case study with the vélib system of paris[END_REF]. They generally focus on stations clustering analyses. Their goal is to find groups of stations with similar temporal usage profiles (incoming and outgoing activity/hour) taking into account the week-days /week-end discrepancy. They usually report the same phenomenon: there are roughly two day patterns, a week day and a week-end day. For instance, as schemed in Figure 4a, a typical week day has two tides: a morning and an evening commute. [START_REF] Côme | Model-based clustering for BSS usage mining: a case study with the vélib system of paris[END_REF] develops also a trips activity recognition. He correlates trips clustering and spatial analysis. Figure 4b represents the spatial distribution of morning tides. We are going to use these analyses to specify a benchmark.

Instances

A city formed with stations on a grid We consider a VSS implemented in a city where stations are positioned on a grid of width w, length l and travel time unity t min = 15 (closest distance between two points of the grid). A number M = l × w of stations are positioned at regular interval on this grid and the distance to go from one to another is computed thanks to the Manhattan distance in time. There are a unique station capacity K = 10 and a number N = M × V p × K of vehicles with V p being the proportion of vehicles per station.

Demand In the many data-mining studies done bike VSS such as Côme ( 2012), it appears that demand is pretty regular along the weeks. We focus hence on a typical week day that we approximate as schemed in Figure 4a: A day lasts 12 hours (say from 6h00 to 18h00). At the end of each day, all vehicles must return to a station. We take as base a fully homogeneous city, i.e. there is same demand for all trips: Λ t a,b = Λ, ∀(a, b) ∈ D, ∀t ∈ T . We only consider one way trips: Λ t a,a = 0, ∀a ∈ M, ∀t ∈ T . Instance "M w × l IΛ s [GΓ] [T Θ]" has to be read as follows: it is an homogeneous city with M stations spread on a grid of size w times l, with a demand intensity Λ s per station per minute (Λ s = (M -1) × Λ) and with possibly a gravitational effect of intensity Γ or a tide effect of intensity Θ.

Tides pattern

We introduce a morning and an evening tides of equal intensity Θ. We divide the day into three periods, morning from 6h to 9h, middle of the day from 9h to 15h and evening from 15h to 18h. The city is split into two equal sub grids: L and R.

1. In the morning there is Θ times more demands than normal for trips going from a station l ∈ L to a station r ∈ R, Θ 2 less in the opposite direction and between stations in R, i.e. Λ [6,9] l,l = Λ, Λ [6,9] l,r = ΘΛ and Λ [6,9] r,l = Λ [6,9] r,r = Θ -2 Λ.

2. In the middle of the day, there is no demand between L and R and Θ 2 less demand between stations in L, i.e. Λ 3. In the evening, there is an opposed tide as in the morning from r ∈ R to l ∈ L, i.e. Λ In the following we use a tide Θ = 6.

Gravitation pattern

We introduce a gravitation of factor Γ. We increase by a factor Γ the demands for trips going from a station l ∈ L to a station r ∈ R while we decrease the opposite demand by the same factor Γ, i.e. Λ a,b = Γ × Λ and Λ b,a = Γ -1 × Λ for (a, b) ∈ L × R and Λ a,b = Λ otherwise. In the following we use a gravitation Γ = 3.

Normalization To decorrelate the tide phenomenon from the simple increase of demands, we normalize the overall demand in order to keep in average the same number of demands as in a full homogeneous city, i.e. the average number of trip requests per day is the same for instances 24 6x4 I0.3, 24 6x4 I0.3 T3 and 24 6x4 I0.3 G3.

Sizing

Demand intensity and fleet sizing To simulate the behaviour of a VSS we have to set the number of vehicles available. Fricker and Gast (2012) study the relationship between demand intensity and the vehicles proportion V p in function of the station capacity K. For a perfect homogeneous city with an arrival rate Λ s per station and a unique transportation time of mean µ -1 the best sizing for a system without any control is V p = 1 K ( K 2 + Λs µ ). Contrary to us, they consider a protocol without reservation of parking spot at destination and in our homogeneous cities the transportation time is not unique. Nevertheless, as shown in Figure 5a, we observe a similar dependence to the demand intensity: The more intense the demand is, the higher the vehicles proportion needs to be.

When considering unbalanced city, with gravitation phenomenon, as shown in Figure 5b, we observe a mustache effect with two local optimums. It corroborates the experience of Fricker et al. (2012) with unique transportation times and no reservation protocol. With a tide phenomenon, we also observe a similar mustache in Figure 5c. The best vehicle proportion depends on the demand intensity, it ranges around 0.45%. [START_REF] George | Fleet-sizing and service availability for a vehicle rental system via closed queueing networks[END_REF] prove that for infinite station capacities the number of trips sold is concave in function of the number of vehicles. When considering station capacity, for non homogeneous cities, as in Figure 5b or 5c, we observe that the function doesn't seam to be concave anymore. In our opinion, these observations indicate that a proper fleet sizing has to be considered when studying other leverage.

A reasonable demand? Figure 6a represents the number of trips sold in function of the demand intensity for an homogeneous city and a tide city with for both their optimal fleet sizing. The number of trips sold is compared to the average number of requests. We observe that for both cities the number of trips sold seams to be concave when considering the best sizing for each intensity. However, for a given proportion of vehicles, for a tide city it doesn't seam to be concave anymore as schemed in Figure 6b.

In Vélib' (2007) Paris there are approximately 150 000 trips sold per day for about 1400 stations. Considering that the majority of these trips are made during 18 hours of the day it gives approximately an arrival intensity of 0.1 clients per station per minute. In Vélib ' (2007) this number of trips represents the final satisfied demand, that is sold without special pricing policy. By simulation, as shown in Figure 6a, to serve 0.1 clients per minute amounts to serving ≈ 1750 clients per day. In an homogeneous city, serving 0.1 clients per minute would hence need an actual demand around 0.15 clients. In a tide city, the function trip sold/demand is almost flat and it is not even sure that it is possible to serve this number of clients.

4.2 Is there any potential gain for pricing policy? An experimental study

Experimental protocol

Optimizing the Number of trip sold In this experimental study, to avoid to consider a complex demand elasticity function we focus on optimizing the number of trips sold by the system. Therefore, we only have to consider that there exists a continuous surjective demand function, with a maximum possible demand Λ, i.e. there exists a price to obtain any demands between 0 and Λ. We take as reference the number of trips sold by a generous policy, setting all prices to their minimum value in order to have for all trips the maximum demand possible λ = Λ. We evaluate the performance, in term of number of trips sold of two pricing policies and two Upper Bounds (UB): 1) The fluid SCSCLP (2) model (Fluid ) gives a static policy and an UB conjectured for dynamic policies and time-dependent demands; 2) The stable fluid (3) PSA model (S-Fluid ) gives a static policy and an UB on dynamic policies only for stable demands.

Note that in practice, if the maximum demand Λ could be obtained at a negative price (paying the user), we should rather compare the pricing policy to the minimum acceptable price policy. We would then need to pay attention to the trade off between the number of trips sold and the generated gain but this is beyond the scope of this paper.

Simulation We compare our 2 pricing policies and 2 UBs to the generous policy on the same scenario: a simulation of the stochastic base model on 250 days with similar demand patterns (using a 10 days warm up). We use a reservation protocol, i.e. users have to book a parking spot at destination in order to take a vehicle.

Figure 7 reports the number of trips sold of our pricing policies on different instances containing 24 stations of capacity K = 10. In Figure 7a and 7b, the demand is stable therefore Fluid and S-Fluid are almost equivalent. There is only a little difference due to the off period (night) between two following days considered by Fluid but not by S-Fluid. In Figures 7c and7d, we introduce a tide phenomenon implying hence time-dependent demands. The value given by stable fluid solution method is hence not giving an UB anymore.

Preliminary results

Influence of the demand intensity We look at the influence of the demand intensity in an homogeneous city. In Figure 7a we compare the performance in an homogeneous cities of the generous policy and fluid heuristic policy (Fluid≈S-Fluid). Each policy is simulated either with its best fleet sizing computed greedily or with a sizing 50%.

With an optimal fleet sizing, the generous policy dominates strictly the fluid policy that is even sometimes much worse. But for a given fleet sizing, here 50% of the parking spot, we see that the performance of the optimization is related to demand intensity: the higher the demand intensity is, the higher the improvement of the fluid heuristic will be.

We explain this phenomenon as follows: We are working on an homogeneous city, the only leverage available is then to use the difference in transportation times. If the fleet sizing is not optimized for the incoming demand the fluid can increase the number of trips sold by the system by favoring short distance trips.

Influence of the gravitation In Figure 7b we compare the performance of the generous policy and the fluid and stable fluid heuristic policies on a city with gravitation. Fluid and S-Fluid are drown on this figure to show that they are almost equivalent. We see that applying static fluid policies provides an increase of roughly 30% while the UB on for any dynamic policies is around 90%.

Influence of the tides In Figure 7c and 7d we study the optimization gap of the fluid policies on a tide city with two different intensities. Note that since we are here considering time dependent demand S-Fluid is not giving an UB anymore. We note that Fluid performs slightly better than S-Fluid. On Figure 7d Fluid improves only a little S-Fluid but for sizing implying 33% less vehicles.

SCSCLP uniform time discretization

In the previous simulations, to compute the fluid SCSCLP (2), we used a discrete time approximation, with 5 minutes time steps, to transform the SCSCLP (2) into a LP solvable by a classic solver. It is a classic way to approximate a CLP through a time discretization with time steps of fixed length. It is not optimal, however, since in our case we are looking at a general behavior having a small error isn't a big issue and as we see on Table 1 taking a 5 minutes time step seems to ensure reasonable results.

Note that for time step divisors there is a monotonic increase in the Fluid simulated value and the Fluid UB gap. However, even if the general tendency is in the increase there are examples of smaller time steps being less efficient than bigger ones (for instance in Table 1 For continuous prices optimization, the fluid UB and the fluid heuristic policy are computed thanks to the SCSCLP (2). For the generous price policy, we have no efficient algorithm computing the fluid model value for one price. However, we see that it seams also to converge toward a conjectured discrete price fluid value.

Optimizing real scale systems

The UB given by the fluid model with or without reservation are surprisingly exactly the same on the tested instances. Moreover, the heuristic produced are giving only slightly different results, and within 0.55% of difference, the model without reservation is even giving better heuristic policies.

When designing heuristics it is important to consider their abilities to handle real size system. In Figure 9 we compare the computation time of fluid with and without reservation. The fluid with reservation is much slower in practice, see Figure 9a, even if it seams to be in the same order of complexity, see Figure 9b.

For big system, it could then be of interest to relax the parking spot reservation constraints in optimization models.

A Discrete price fluid model Proof : A simple evaluation for a given price, hence a given demand λ, presents a non linear dynamic. Figure 12 shows an example with integer data where the instantaneous flow is an irrational number.

The example is built as follows: There is 6 stations, at time t a and d are not empty, c and f are not full, b is empty and e is full. All instant demands (λ t ) have for intensity 1. For a matter of simplicity, in the sequel, the time parameter (t) will be implicit. Using the paradigm of arrival .

Figure 1 :

 1 Figure 1: VSS stochastic model: A closed queuing network with periodic time-varying rates.

  n a,b : (a, b) ∈ D, t ∈ T ) represents the vehicles distribution in the city space (in station or in transit) at a given time. At time step t, n a is the number of vehicles in station a ∈ M, n a,b the number of vehicles in transit between stations a and b serving a trip demand (a, b) ∈ D. The transition rates between states are either: • The taking of a vehicle at a station a to go to a station b giving a transition rate λ t a,b (p t a,b ) between states (. . . , n a , . . . , n a,b . . . , t) and states (. . . , n a -1, . . . , n a,b + 1, . . . , t) with n a > 0 and n b + c∈M n c,b < K b ; • The arrival of a vehicle at a station b from a station a giving a transition rate n a,b µ t a,b between states (. . . , n b , . . . , n a,b . . . , t) and states (. . . , n b + 1, . . . , n a,b -1, . . . , t) with n a,b ≥ 1;

Figure 3 :

 3 Figure 3: Elastic demand λ t a,b ∈ [0, Λ t a,b ].

  λ a,b (t) the demand to go from station a to station b at time t + µ -1 a,b with price p(λ a,b (t)); s a (t)

Fluid

  be the average throughput for the trip(a, b)

  Spatial distribution of morning tides. A two types of station approximation.

Figure 4 :

 4 Figure 4: Source Côme (2012).

Figure 5 :

 5 Figure 5: Sizing the number of vehicles in the system varying demand intensity.

  (a) Number of trips sold compared to the number of requests for cities with optimal fleet sizing.(b) The number of trips sold in function of the demand intensity is not concave for a given fleet size.

Figure 6 :

 6 Figure 6: Number of trips sold in function of demand intensity: A flat function.

  (a) Varying demand intensity: Instance 24 4x6 I1-6. (b) Gravitation: Instance 24 4x6 I3 G3. (c) Tide low intensity: Instance 24 4x6 I1 T6.(d) Tide higher intensity: Instance 24 4x6 I1 T6.

Figure 7 :

 7 Figure7: Sizing the number of vehicles in the system with a pricing regulation.

Figure 8 :

 8 Figure 8: Asymptotic convergence of s-scaled problem and fluid model on instance 4 2x2 I3 T3.

Figure 9 :

 9 Figure 9: Influence of fluid model reservation constraint on computation time.

  possible trips (= M × M), t a,b (t) the transportation time between station a and b = µ -1 a,bλ a,b (t) the transition rate of demands from station a at time t to station b, P a,b (t) the set of prices to go from station a to b at time t at time t + t a,b at price p(λ a,b (t)), N the number of cars available, Λ(price) the function giving the demand for a given price. Variables at time t: p + a (t) the proportion of requests accepted among those willing to leave station a, p - a (t) the proportion of requests accepted among those willing to arrive at station a, that have been accepted to take a vehicle at their departure station, y a,b (t) the flow leaving station a at time t and arriving at station b at time t + t a,b , y dep a,b (t) the flow accepted to leave station a but not yet accepted to arrive at station b, y ref a,b (t) the flow refused by station b returning to station a (one has y dep a,b (t) = y ref a,b (t) + y a,b (t)), s a (t) the available stock at station a, r a (t) the number of parking spots reserved at station a (flow in transit toward a).

Figures

  Figures 10 and 11 schemes an instance with its corresponding variables.

FigureFigure 11 :

 11 Figure 10: Variables for 2 stations.

Figure 12 :

 12 Figure 12: Discrete price plumber is non linear dynamic. Exhibition of an irrational solution, here x = -1± √ 5 2

  , the demand follows a Poisson distribution of parameter λ t a,b (p t a,b ) function of the proposed price p t a,b . All durations follow general distributions: transportation time to go from station a to station b at time step t has for mean 1/µ t a,b , the time step duration t ∈ T has for mean 1/τ t . Hence, the total periodic horizon length has for mean T = t∈T 1/τ t .

	2.2.2 Closed queuing network model
	For a fixed price p t a,b implying a fixed demand λ t a,b for every trips (a, b) ∈ D and every time steps t ∈ T we model this stochastic VSS by a closed queueing network with finite buffers and periodic time-varying service times as schemed in Figure 1.
	Each station a ∈ M is represented by a server a with a buffer of size K ′ a . Time dependent service rate λ t a of server a is equal to the average number of users willing to take a vehicle at station a: λ t a = (a,b)∈D λ t a,b .
	Vehicles are N jobs routing in the network. At time t, a user taking a vehicle for a trip λ t a,b (a, b) ∈ D is represented by a job processed by server a with routing probability λ t a

To go from station a ∈ M to station b ∈ M at the period (t mod |T |) ∈ T

Table 1 :

 1 2 and 5 minutes time steps). 8% -55.6 % -33.9% -10.3% -1.8% -2.2% 6.4% 2.5% Fluid UB Rel. Gain. -70.5 % -38.4% -6.2% 23.4 % 38.6% 36.1% 57.3% 45.3% Time discretization (in min.) convergence for the instance 024 4x6 I3 T3 with station capacity 10.

	Time step	180	90	60	45	30	20	15	12
	Fluid Gain. -82.Time step 10	8	6	5	4	3	2
	Fluid Rel. Gain.	5.4%	5.9%	6.2%	7%	6.1% 7.3% 6.8%
	Fluid UB Rel. Gain. 52.3%	52.9% 54.5% 58.4% 54.4% 58.6% 57.2%

Remark 2 Without the flow stabilization constraint, it would be easy to compute the value of a solution with one price. A simple iterative algorithm on the horizon would work. With flow stabilization constraint it is not clear that cycling on that iterative algorithm would lead to a stationary solution.

A.2 A non linear dynamic

The previous non linear program might not the simplest formulation of the discrete price optimization. However, since discrete price optimization is not a linear problem. Therefore, the discrete price dynamic can't be model with a linear program.

Lemma 1 The discrete price dynamic can't be model with a linear program. which is an irrational number. The flow dynamic for a given price is hence not linear.