1 Introduction

The world of transportation has witnessed a mini-revolution in June 2007 with the launching of the Vélib’ bicycle sharing system in Paris. Initially 20,000 bicycles were deployed over 1200 free-access stations. In the first year 200,000 users registered and 26 million bicycles were rented. Since then, the phenomenon has known a considerable growth. While Vélib’ was not the first bicycle sharing system, it was the first one of any major significance. The Vélov’ system in place in Lyon, which dates from 2005, is believed to be the oldest one still in existence. However, such systems have been tested in Europe since the 1960s. Public bicycles were first introduced in Amsterdam in 1965, within the so-called white bicycle plan, but most of these earlier systems ended up in failure because of theft and vandalism. Bicycle sharing really took off with the advent of communication and information technologies which allow for automatic billing and monitoring. In June 2014, there were over 712 bicycle sharing systems in the world, involving over 800,000 bicycles (Wikipedia 2018a). For interesting historical accounts, see DeMaio (2009), Shaheen and Cohen (2007) and Kumar et al. (2013).

In parallel, a number of car sharing systems have also been put in place. Again, the first one (Autolib’) was set up in Paris in 2007. Currently (July 2017), the world’s largest car sharing networks are Zipcar with over 767,000 members and 11,000 vehicles in several countries such as Austria, Canada, France, Spain, the United Kingdom, the United States and Turkey, and Car2Go with 2,500,000 members and 14,000 cars in several countries such as Austria, Canada, China, Denmark, Germany, Italy, the Netherlands and the United States (Wikipedia 2018b). Navigant Consulting (see Berman et al. 2013) predicts that the number of car sharing members will grow over 12 million worldwide by 2020 and will generate in excess of US$ 6 billion in revenue. According to Shaheen and Cohen (2007) the growth and expansion of car sharing systems will be fuelled by high energy costs, limited and expensive parking, improved technologies and increased demand for personal vehicle access in developing countries.

Car and bicycle sharing systems have given rise to a fast growing industry operating according to new specific business models, which people are just now beginning to understand. The reader is referred to Perboli et al. (2017) for a methodology developed to compare business models of car sharing companies, where the features taken into account are customer segments, products and services offered, communication channels with the customers, customer relationships, operating assets, revenue streams, key activities, partnerships, and cost structure. The central operational problem faced by shared mobility systems operators is to maintain an adequate number of vehicles in every station. Indeed, too many vehicles can impede their return, whereas too few may translate into lost demand. However, as noted by Médard de Chardon et al. (2016), there is a lack of clear goals in some systems, such as profit optimization or service level considerations, and a lack of fit between rebalancing policies and the stated or perceived goals.

Locating stations, choosing the number of vehicles per station, moving vehicles between stations, inciting users to change their destination, are all managing decisions guided by the need to provide a good quality of service, at both end-stations. Providing effective tools to support these decisions constitutes an important motivation for researchers in this new field, especially for operational researchers. However, shared mobility systems have also attracted the attention of researchers in other areas, such as transport economics, urban planning, sociology, and data mining, see for instance Vogel et al. (2011), Midgley (2011), Efthymiou et al. (2013) and Cômes and Oukhellou (2014), and also the already mentioned paper by Médard de Chardon et al. (2016), where the authors have analyzed data patterns associated with the stations of nine bicycle sharing systems and developed a number of managerial insights that can be useful for the design of such systems. Data mining actually plays an important role in determining the values of the parameters in most of the operational research models.

Our purpose is to survey the main operational research issues arising in shared mobility systems as well as the methods that have been proposed to address them. This topic has already been reviewed by Laporte et al. (2015). However, it is still very active and several interesting publications have appeared since that date. Here we incorporate the most recent developments. We will restrict our survey to systems made up of stations where users can take or return a vehicle. Note, however, that some car sharing systems (for example Car2Go) do not operate with stations. The shared vehicles can be bicycles or cars. To our knowledge, no other type of vehicle sharing exists.

We will successively examine station location, fleet dimensioning, station sizing, rebalancing incentives, and vehicle repositioning. For each of these topics, we provide an overview on the literature and describe one or more solution approaches that seemed important to us. This work is partially based on a preliminary survey by Meunier (2014).

2 Station location

As noted in the introduction, bicycle availability is a key factor of success of a bicycle shared system. But it is also crucial that users should be able find stations within a convenient walking distance from their origin and their destination. Budget and space availability constrain the number of stations and their locations and challenge the design of a system having a good performance. Several works have been devoted to this topic. In this section, we present a series of papers in which the location issue has been explicitly taken into account.

Lin and Yang (2011) proposed the first operational research study of the station location problem for a bicycle sharing problem. They have modeled the problem as a non-linear integer program which simultaneously considers the location of stations and user flows, as well as the location of bicycle lanes, with an objective function combining the operators’ and users’ criteria. Their model was solved by LINGO on a small example. Lin et al. (2013) have formulated the problem as a joint hub location and inventory model and have expressed it as an integer non-linear program. The model was solved by CPLEX on instances containing up to 30 origins, 30 destinations and 80 candidate bicycle stations.

Several researchers have worked on real-life problems and data. Martinez et al. (2012) have presented a model to simultaneously optimize the location of shared bicycle stations, the fleet dimension, and the relocation of bicycles throughout the day. Their model was solved through a simple relocation heuristic and was applied to data from the city of Lisbon. Kumar and Bierlaire (2012) developed a mathematical model to locate electric car sharing stations in and around the city of Nice. The model takes into account the attractiveness of the stations to the users located in their vicinity, as well as the distance between users and facilities. The results of the model were used to make recommendations to Auto Bleue which manages the car sharing service in Nice. In particular the authors recommended caution before adding new stations in order to minimize the impact of cannibalization. Correia and Antunes (2012) have developed three mixed integer linear programming models aimed at determining the best number, location, and size for the depots of a one-way car sharing system, each corresponding to a trip selection scheme. Their models were tested on data from the city of Lisbon. The authors showed that 75 depots needed to be located to fully satisfy the demand.

Martens (2007) studied a number of policies initiatives to promote the use of bicycle sharing systems in the Netherlands. She emphasizes the importance of locating parking spacing close to railway stations, as well as security issues. Nair and Miller-Hooks (2014) have modeled the operator’s revenue maximization problem as a bilevel program. More details are given below. Another station location problem with a game-theoretic approach was formulated by Chow and Sayarshad (2014) in a more general framework aimed at evaluating the impact of designing a transportation network when there already exists a network. The authors have applied their model to the bicycle-sharing system of Toronto (Bike Share Toronto—formerly BIXI Toronto) and were able to make concrete subsidy recommendations.

Li et al. (2016a) have used a continuous approximation model (see, e.g., Franceschetti et al. 2017) to determine the location and size of facilities in an electric vehicle sharing system. This approach partitions the plane into hexagonal cells, each of which containing a single station. It is assumed that each user can access a station within a set time limit (on foot, for example). Given a cell and a station located in its center, one can compute the total access cost over a time period assuming stochastic travel demands with Poisson distributions having a relatively high mean. Probability computations can be used to determine the size of a station in order to achieve a certain service reliability. The partition is obtained through a constructive procedure that first meshes the plane into basic units which are then agglomerated to form cells of feasible sizes by sweeping the plane only once. Computational results are presented on the transportation network of Sioux-Falls City in North Dakota.

To our knowledge, the Nair and Miller-Hooks (2014) approach is the only one based on bilevel programming. The problem under study consists of determining the best locations for the stations, as well as their capacities and their initial vehicle inventories, subject to a budget constraint. The quality of a solution is given by the expected revenue, seen as a linear function of user flows. The operator can relocate vehicles.

This leads naturally to a bilevel program. A mathematical program is a bilevel program when the values of some variables are optimal solutions of another optimization problem, called the lower-level problem, solved by one or several different decision makers. The main objective function together with the other constraints is the upper-level problem. Here, the lower-level problem allows computing the value of the user flows for a given choice of the decision variables (locations and capacities of the stations, initial inventories). The user flows have an impact on the durations of the possible trips. Each user selects a trip of minimum duration, while this duration depends on the trips selected by the other users. If the users act in a non-cooperative way, which is the case in the model considered here, the user flows yield a Nash equilibrium: each user chooses a best response to the choices of the other users. The Nash equilibrium here is actually called a Wardrop equilibrium because there is a continuum of users. It turns out that this equilibrium can be computed via a minimization problem, see Spiess and Florian (1989).

The constraints of the upper-level problem are the logical constraints linking the decision variables and the budget constraint. The set of possible locations for the stations, supposed to be finite, is denoted by P. In a compact way, the bilevel program they deal with is of the form

$$\begin{aligned} \begin{array}{ll} \text{ maximize } &{} F(\varvec{v}) \\ \\ \text{ subject } \text{ to } &{} G(\varvec{x},\varvec{y},\varvec{z})\le \varvec{0}\\ \\ &{} \begin{array}{ll} \min &{} f(\varvec{v},\varvec{w}) \\ \\ \text{ s.t. } &{} g(\varvec{x},\varvec{y},\varvec{z},\varvec{v},\varvec{w})\le \varvec{0}\end{array} \\ \\ &{} \varvec{x}\in \{0,1\}^P,\; \varvec{y},\varvec{z}\in \mathbb {Z}_+^{P} \\ \\ &{} \varvec{v}\in \mathbb R_+^{P\times P\times K},\;\varvec{w}\in \mathbb R_+^{P\times K}. \end{array} \end{aligned}$$

Variables \(\varvec{x}\), \(\varvec{y}\), and \(\varvec{z}\) are the upper-level variables of the model. The variable \(x_i\) is a binary variable equal to one if and only if a station is opened at i. The variable \(y_i\) is the number of parking slots opened at the station located at i, and the variable \(z_i\) is the number of vehicles initially parked at the station located at i, if there is such a station. The variables \(\varvec{v}\) and \(\varvec{w}\) are the lower-level variables of the model. The variable \(v_{ijk}\) is the user flow from location i to location j relative to the origin-destination (OD) pair k. The variable \(w_{ik}\) is the waiting time at location i of the network relative to the OD pair k.

The operator wants to maximize his revenue, modeled has a function \(F(\varvec{v})\) of the flows. He can set the variables \(\varvec{x}\), \(\varvec{y}\), and \(\varvec{z}\), while satisfying constraints modeled as \(G(\varvec{x},\varvec{y},\varvec{z})\le \varvec{0}\). These constraints are the logical constraints between \(\varvec{x}\), \(\varvec{y}\), and \(\varvec{z}\), and the budget constraint. For a choice of these variables, the users make a decision that minimizes their travel time, leading to certain values for the variables \(\varvec{v}\) and \(\varvec{w}\). The functions f and g are respectively the objective function and the constraints of the minimization problem modeling the Nash-Wardop equilibrium.

Bilevel programs are generally hard to solve, see Colson et al. (2007) for a survey. Nair and Miller-Hooks (2014) assume that all functions involved are linear in every variable. Even in this case, the problem is hard, but a standard technique, applied by the authors, consists of replacing the lower-level program by the Karush–Kuhn–Tucker conditions characterizing the optimal solution. Using additional binary variables, the resulting complementary constraints can then be replaced by linear constraints. The bilevel model is thus reformulated as an integer linear program which they solve by CPLEX. This method seems to be suitable for networks with no more than 40 vertices. The experiments also show that the optimal design is potentially inefficient for users and that subsidies to operators are probably required to incite them to design a user-efficient system.

3 Fleet dimensioning

The first paper to consider the fleet dimensioning problem in a shared mobility system is probably that of George and Xia (2011). Their approach is based on tools from queueing theory. Fricker and Gast (2016) also used a queueing approach to analyze the effect of bicycle station capacity on system performance. These two approaches are detailed below.

Before presenting the George-Xia and Fricker-Gast approaches, we mention the work by Shu et al. (2013) who addressed the following questions related to the management of a bicycle sharing network. Given stations locations, how many bicycles should be deployed in order to capture demand and thus ensure the system’s viability? Given travel patterns, how should the bicycles be distributed? What should be the size of the stations? The authors have developed a stochastic network flow model and, by making a number of hypotheses, they were able to cast their problem as a linear program. They conducted a numerical analysis using transit data from Singapore. The authors stressed the importance of deploying the right number of bicycles at the right locations because this affects their utilization rate and the way in which these circulate within the system. Note that the paper by Nair and Miller-Hooks (2014), discussed in Sect. 2 about the station location issue, also addressed the problem of setting the initial inventory of bicycles in each station.

In the system considered by George and Xia (2011), users arrive at a station i according to a Poisson process of rate \(\lambda _i\) and choose a destination station j with probability \(p_{ij}\). The duration of a trip between two stations i and j follows a general distribution with a finite mean. This distribution is assumed to be the same for all users but depends on i and j. The model assumes that the vehicles are exclusively relocated by the users and that each station has an infinity capacity. They are interested in the availability as a measure of quality of service, defined as the percentage of users able to find a vehicle available at the steady state.

These authors model their system as a closed queueing network consisting of nodes of two types, “single-server” and “infinite-server”, and in which the customers in the queueing terminology are the vehicles. The single-server node set N is used to model the stations and the infinite-server node set T is used to model the trips between the stations. There exists an arc from each station \(i\in N\) to each possible trip \(t\in T\) starting at i, and an arc from each trip t to the station i at which it ends. A vehicle at station i is waiting to be served by a user with an exponential service rate \(\lambda _i\). When it is served, it arrives at an infinite-server node with a service time distributed according to the trip duration distribution. The system is closed because the vehicles are not allowed to leave it. Using general results for closed queueing networks, they derive a closed-form formula for the steady-state probability.

The computation of this formula is unfortunately very expensive, except for the case of a small number of stations and vehicles. The authors are, however, able to derive from their results general principles for designing a vehicle shared system with improved availability. They are moreover interested in determining the right number of vehicles to put in the system in order to maximize the operator’s profit. They use the following variables to model their optimization problem, defined at steady-state, when the number of vehicles is m. Denote by \(A_i(m)\) the probability of finding a vehicle for a user arriving at station i (i.e. its availability). Also denote by \(L_{t}(m)\) the expected number of vehicles at node t, i.e. currently making trip t. George and Xia formulate the problem as

$$\begin{aligned} \max _{m\in \mathbb {Z}_+} \sum _{t\in T}r_{t}L_{t}(m)-\sum _{i\in N}p_i\lambda _i(1-A_i(m))-cm, \end{aligned}$$

where \(r_{t}\) is the per-unit time income obtained from a vehicle doing trip t and \(p_i\) is the penalty incurred when a user does not find a vehicle at station i. The quantity c is a per-unit time maintenance cost for each vehicle. George and Xia prove that the function to maximize is concave in m and propose several methods to approximately solve the problem. Here the difficulty lies in the computation of \(A_i(m)\) and \(L_{t}(m)\) for any given m. They validate their formula and the approximation methods through experiments and simulations run on a toy model.

Fricker and Gast (2016) considered a model with the following features. The users arrive at each station according to a Poisson process at the same rate \(\lambda \). The trip durations are all exponentially distributed with the same average value \(1/\mu \). The destination station is chosen uniformly at random among the stations, which are assumed to have finite capacity C (contrasting with the George-Xia infinite capacity assumption). If a user does not find an available vehicle to start a trip, he leaves the system. If he does not find an available slot where to leave his vehicle after a trip, he starts a new trip. As in the George and Xia (2011) model, the vehicles are exclusively relocated by the users. Fricker and Gast focus on the number of problematic stations at the steady-state, i.e. stations having no vehicles or no free slots. They study the system when the number n of stations goes to infinity, via mean-field limit techniques. They prove that the number of problematic stations is minimized when the average number of vehicles per station (total number of vehicles divided by the number n of stations) is \(C/2+\lambda /\mu \). The optimum is then about \(n/(C+1)\). They also make a non-intuitive observation: the behaviour of the system worsens if the users only arrive at stations containing vehicles, and finish their trips at stations with available slots.

4 Station inventory

Station inventory refers to determining the ideal number of vehicles to locate at each station. We present four papers on that topic. Interestingly, each of them formalizes the problem in a distinctive way and proposes an approach relying on a different technique from optimization.

In Nair and Miller-Hooks (2011) the goal is to relocate the vehicles at a minimum cost, while satisfying at best the demand. An interesting feature of this approach is that the satisfaction of the demand is modeled via probabilistic constraints. The relocation process is taken into account in a rough way, and is supposed to take place before the system opens.

More formally, each station i has a capacity \(C_i\) and an initial number of vehicles at station i is denoted \(V_i\). The demand in vehicles at station i is denoted \(\zeta _i^v\) and the demand in available slots, that is the number of vehicles that will be returned at i, is \(\zeta _i^s\). Both are random variables of known distributions. The demand must be satisfied with a probability at least p. The cost of relocating vehicles from station i to station j is denoted by \(a_{ij}\) and there is an additional penalty \(\delta \) for each moved vehicle. The mathematical program to be solved is thus

$$\begin{aligned}&\text {minimize} \displaystyle {\sum _{i,j\in N}(a_{ij}x_{ij}+\delta y_{ij})}&\end{aligned}$$
(4.1)
$$\begin{aligned} \text {subject to }&&\nonumber \\&Pr\left( \begin{array}{ll} \displaystyle {V_i+\sum _{j=1}^n(y_{ji}-y_{ij})+\zeta _i^{s}\ge \zeta _i^{v}}, &{} i\in N \\ \displaystyle {C_i-V_i+\sum _{j=1}^n(y_{ij}-y_{ji})+\zeta _i^{v}\ge \zeta _i^{s}},&{} i\in N\end{array}\right) \ge p&\end{aligned}$$
(4.2)
$$\begin{aligned}&\displaystyle {\sum _{j\in N}y_{ij}\le V_i}&i\in N \end{aligned}$$
(4.3)
$$\begin{aligned}&\displaystyle {\sum _{j\in N}y_{ji}\le C_i-V_i}&i\in N \end{aligned}$$
(4.4)
$$\begin{aligned}&y_{ij}\le M x_{ij}&i,j\in N \end{aligned}$$
(4.5)
$$\begin{aligned}&y_{ij} \ge 0 \text{ and } \text{ integer },\; x_{ij}\in \{0,1\}&i,j\in N. \end{aligned}$$
(4.6)

The variable \(x_{ij}\) is a binary variable indicating whether vehicles are moved from i to j. The integer variable \(y_{ij}\) is the number of vehicles moved from i to j. Constraint (4.2) states that the whole demand must be completely satisfied with a probability at least equal to p. Constraints (4.3) state that the number of vehicles moved from a station i cannot exceed the initial inventory \(V_i\) and constraints (4.4) state that the vehicles moved to a station i cannot exceed the station capacity \(C_i\). Constraints (4.5) form the logical constraints linking x and y.

The authors addressed this stochastic program through two different algorithms, both relying on the notion of p-efficient points introduced by Prékopa (1990) for solving efficiently stochastic programs whose randomness appears only in the right-hand side of the constraints. In the first algorithm the non-convex probability constraints are transformed into a disjonction of mixed integer linear programs. It is an exact algorithm, which is very time-consuming. The second algorithm exploits a limited assumption on the independence of the random variables to adapt an approach by Dentcheva et al. (2002). This leads to an algorithm which is similar to column generation where only columns that improve the objective function are generated. The master problem is a convexified linear relaxation of the original problem, which makes this second algorithm only an approximation algorithm. Extensive computational experiments were carried out on real data from the Singapore car sharing system with 14 stations, a total capacity of 202 spaces, and 94 vehicles. Simulation studies were conducted and the proposed solutions strategies where found to be robust. In addition, trade-offs between redistribution costs and level of service were investigated.

Raviv and Kolka (2013) focused on a single station with C slots. Let \(D_k\) be the k th demand occurring at the station, which can be a demand for a vehicle or a demand for a slot. It is a random variable taking the value \(-\,1\) if it is a demand for a slot, and the value 1 if it is a demand for a vehicle. The demand \(D_k\) is assumed to follow a non-homogeneous Poisson process, with distinct parameters for the slot demand and the bicycle demand. Non-homogeneous means that these parameters evolve over time.

The authors introduce an inventory variable \(I_k\) equal to the number of vehicles at the station right after the k th demand has occurred. This yields the following dynamic system:

$$\begin{aligned} I_k=\left\{ \begin{array}{l@{\quad }l} 0 &{} \text{ if } I_{k-1}-D_{k-1}<0 \\ C &{} \text{ if } I_{k-1}-D_{k-1}>C \\ I_{k-1}-D_{k-1} &{} \text{ otherwise. }\end{array} \right. \end{aligned}$$

In order to measure the performance of a station, the authors model the total user dissatisfaction over time as follows:

$$\begin{aligned} \sum _{k=1}^{m}\left( p\max \{0,-I_{k-1}+D_{k-1}\}+h\max \{0,I_{k-1}-D_{k-1}-C\}\right) , \end{aligned}$$

where m is the total number of events considered, and p and h are two positive real numbers representing the cost of not satisfying a user demand, respectively for a vehicle and a slot. The quantity \(\max \{0,-I_{k-1}+D_{k-1}\}\) is 1 if a user does not find a bicycle at step k, and \(\max \{0,I_{k-1}-D_{k-1}-C\}\) is 1 if a user does not find a slot at step k. This dissatisfaction measure is thus the total number of users not finding a bicycle, plus the total number of users not finding a slot, weighted differently.

The purpose is to compute the value of \(I_0\) minimizing the total user dissatisfaction. Raviv and Kolka (2013) proved the convexity of this dissatisfaction seen as a function of \(I_0\), and devised an approximation method to estimate it. An interesting feature of this model is that it neglects the interactions between stations, thus reducing the problem to the case of a single station. The authors assume that the system will evolve in an optimal way, for example, by minimizing the number of users who cannot find a bicycle. They conducted a study based on the Tel-O-Fun bicycle sharing system of Tel Aviv which consists of 129 stations, 2542 parking slots, and about 1000 bicycles. They carried out extensive tests which confirmed that the proposed method can feasibly be applied.

Vogel et al. (2014) tackled the imbalance problem by means of an allocation and relocation model. They used a mathematical integer programming formulation in order to determine optimal fill levels at the stations while minimizing the expected bicycle relocation cost for a typical demand. The model was solved through a matheuristic combining large neighbourhood search with an exact integer linear programming solver. Results were presented on data from the Citybike Wien system.

In the system considered by Datner et al. (to appear), users may not find a bicycle at their desired starting station, and they may not find an available rack at their destination, in which case they will have to roam to a nearby station that has spare capacity. Both situations generate a level of dissatisfaction that can be minimized by setting adequate inventory levels at each station at all time. In their mathematical model, the authors discretize time into epochs. The model is solved heuristically by searching for initial inventory levels that minimize the expected dissatisfaction level over the planning horizon. The search is performed iteratively starting from an initial inventory level at each station and estimating at each iteration the expected total dissatisfaction level. This is achieved by simulating the system by means of a user behaviour model. The heuristic was tested on real bicycle sharing systems of different sizes: Hubway in Boston, Capital Bikeshare in Washington D. C., and Divvy in Chicago. The results were found to be superior to those yielded by two alternative heuristics: “Half”, in which each station is initially half filled, and “R&K”, which follows the method of Raviv and Kolka (2013) described above. It was also shown that the performance of the algorithm is not highly sensitive to the starting solution.

5 Rebalancing incentives

As noted in the introduction, the need to rebalance stations by redistributing vehicles among them over time is central to the success of a shared mobility system. Incentives can be used to encourage users to pick up vehicles at stations having a large supply and to return them to low-inventory stations. The Paris Vélib’ system provides financial incentives to users who return their bicycle to given stations. Such incentives are called static because they apply at all time. One could conceivably envisage the use of dynamic incentives which could vary throughout the day, but we are not aware of any of such system in practice.

Chemla et al. (2013a) and Pfrommer et al. (2014) have both studied a dynamic pricing system. They assume that the price paid by users depends on the current state of the system and on the station at which the bicycle is returned, independently of its origin. Chemla et al. focus on the reduction of saturated stations and compute the optimal price by using the dual solution of a Monge-Kantorovitch problem. Pfrommer et al. formulate the pricing problem by means of optimal control theory. Singla et al. (2015) incorporated in this model a learning mechanism to shape the user utility function, and enriched it by taking into account a budget constraint for the operator. They were able to test their methodology on historical data. Another work with a dynamic pricing aspect is due to Waserhole (2013) and Waserhole et al. (2013a, b). They considered a system in which users reveal their itinerary and are immediately informed of the price they must pay. The underlying objective is the maximal system usage in terms of number of trips or total utilization time. These researchers have developed a number of complexity results and some approximation algorithms related to this problem, and have proposed a number of interesting open problems.

Three papers propose dynamic incentives that are not directly related to the price.

Di Febbraro et al. (2012) have investigated dynamic relocation problems arising in a one-way car sharing system. They assumed that the users will sometimes be requested to relocate their car at the end of their trip to a nearby station having a shortage of cars. Their aim is to minimize the rejection ratio of reservations in any period of the day. The authors modeled the system as a discrete event system, coupled with a relocation process based on the solution of an integer linear program. Using data from the city of Turin, they showed that the number of rejected reservations could be reduced significantly when car relocations were performed exclusively by users. As a result they stressed the importance of offering adequate discounts to users in order to incite them to relocate their car.

Kaspi et al. (2014) studied system regulation through parking reservation policies. In particular they investigated a policy in which users must state their destination at the time of booking and the system reserves a parking space until they arrive at their destination. The performance of the system was measured in terms of excess time, defined as the difference between the actual journey time and the shortest possible time between the desired origin and destination. Using a Markovian model the authors showed that under realistic demand rates this policy improves the performance of the system. They performed a simulation study on the Tel-O-Fun bicycle sharing system of Tel Aviv and showed that the excess time could be reduced by between 14 and 34%. In a related paper Kaspi et al. (2016) have compared several parking reservation policies and have studied their worst-case performance bounds. Using data from the Capital Bikeshare system of Washington (232 stations) and the Tel Aviv (130 stations) Tel-O-Fun systems they confirmed that the parking policy considered by Kaspi et al. (2014) is the best.

In the paper already presented in Sect. 3, Fricker and Gast (2016) also study the impact of the following modification in the way the users choose their destination. Instead of choosing a unique destination at random (one-choice model), the users choose two stations at random, and then go to the least loaded (two-choice model). In this case, the number of problematic stations is about \(4n\sqrt{C}2^{-C/2}\), for a whole range of possible values for the average number of vehicles per station. This simple change, which can be interpreted as a kind of incentive, has thus a dramatic impact on the performance of the system. Moreover, the improvement remains about the same, even if only a small proportion of the users follow this policy, since the decrease in the number of problematic stations is approximately exponential in the number of users following it. This work may suggest some ways of improving the management of such a system. However, some results are heavily dependent on the choice made in the modeling. For instance, the authors show through simulations that the two-choice model can even increase the number of problematic stations, for instance when the trip durations are deterministic and long with respect to \(1/\lambda \).

6 Vehicle repositioning

Vehicle repositioning can either be static or dynamic. In the first case it typically takes place during the night while in the second case it occurs throughout the day. Most of the research on vehicle repositioning concerns the static case, partly because it is easier to model and also because the impact of repositioning is more important during the night.

6.1 Static case

Raviv et al. (2013) were probably the first to study the static case. These authors present two models: one based on an arc index which forbids each truck to visit several times a same station, and a second one based on a time index which is much more flexible. In both cases, the objective function—to be minimized—is the weighted sum of user dissatisfaction and total travel time. The user dissatisfaction is modeled as a convex piecewise linear function depending on the number of bicycles in each station. We describe the time index model now a bit more thoroughly.

The set of stations without the depot is indicated with N and with \(N_0\) otherwise. There is a fleet of trucks, denoted by V, used for repositioning bicycles. The time is discretized and a truck passes through a node at instant t which is defined by taking into account the travel time \(t'\) between two consecutive nodes. They assume that user dissatisfaction can be represented as the sum of piecewise linear functions, one for each station i. They linearize these functions in a standard way, by adding a family of constraints characterized by parameters \(a_{iu}\) and \(b_{iu}\). The decision variables are the following:

  • \(x_{ijtv}\) binary variables indicating if a truck v starts traveling from station i to station j at time t;

  • \(y_{itv}^L\) number of bicycles loaded at time t;

  • \(y_{itv}^U\) number of bicycles unloaded at time t;

  • \(y_{ijtv}\) number of bicycles carried by truck v at time t;

  • \(s_{it}\) bicycle inventory level on station i at time t;

  • \(g_i\) user dissatisfaction incurred at station i.

The model is the following:

$$\begin{aligned}&\text {minimize} \sum _{i \in N} g_i + \alpha \sum _{i,j \in N_0}\sum _{t=1}^{T'}\sum _{v \in V} t'_{ij}x_{ijtv}&\end{aligned}$$
(6.1)
$$\begin{aligned} \text {subject to }&&\nonumber \\&g_i \ge a_{iu} + b_{iu} s_{iT'}&\quad&i \in N, u = 0,\dots ,c_i -1 \end{aligned}$$
(6.2)
$$\begin{aligned}&s_{i0} = s_{i}^0&\quad&i \in N_0 \end{aligned}$$
(6.3)
$$\begin{aligned}&s_{it} = s_{it-1} + \sum _{v \in V} (y_{itv}^U - y_{itv}^L)&\quad&i \in N_0, t = 1,\dots ,T' \end{aligned}$$
(6.4)
$$\begin{aligned}&s_{it} \le c_i&\quad&i \in N_0, t = 1,\dots ,T' \end{aligned}$$
(6.5)
$$\begin{aligned}&\sum _{j \in N_0} x_{0j0v} = 1&\quad&v \in V \end{aligned}$$
(6.6)
$$\begin{aligned}&\sum _{j \in N_0} x_{j0,t-t'_{j0},v} = 1&\quad&v \in V \end{aligned}$$
(6.7)
$$\begin{aligned}&\sum _{j \in N_0} x_{ji,t-t'_{ji},v} = \sum _{k \in N_0} x_{iktv}&\quad&i \in N_0, t = 1,\dots ,T',v \in V \end{aligned}$$
(6.8)
$$\begin{aligned}&\sum _{j \in N_0} y_{ji,t-t'_{ij},v} = \sum _{k \in N_0} y_{iktv} + (y_{itv}^U - y_{itv}^L)&\quad&i \in N_0,t = 1,\dots ,T',v \in V \end{aligned}$$
(6.9)
$$\begin{aligned}&y_{itv}^L \le \min \{c_i,k_v\} \sum _{j \in N_0} x_{ijtv}&\quad&i \in N_0, t = 1,\dots ,T',v \in V \end{aligned}$$
(6.10)
$$\begin{aligned}&y_{itv}^U \le \min \{c_i,k_v\} \sum _{j \in N_0} x_{ijtv}&\quad&i \in N_0, t = 1,\dots ,T',v \in V \end{aligned}$$
(6.11)
$$\begin{aligned}&y_{ijtv} \le k_v x_{ijtv}&\quad&i \in N_0, t = 1,\dots ,T',v \in V \end{aligned}$$
(6.12)
$$\begin{aligned}&x_{ijtv}\in \{0,1\},\; y_{ijtv}\, s_{it}, g_i\ge 0&\quad&i,j \in N_0, t = 1,\dots ,T',v \in V, \end{aligned}$$
(6.13)

where \(t'_{ij}\) is the travel time between nodes i and j, and \(T'\) is the length of time horizon.

The objective function (6.1) is the weighted sum of two terms: user dissatisfaction and travel time. Constraints (6.3)–(6.5) represent the bicycle inventory at each station for each time period. Constraints (6.6)–(6.8) are the classical flow conservation constraints which state that a truck entering a node must exit it. Constraints (6.9)–(6.11) define the loading and unloading values. Constraints (6.12) link the use of an arc with the maximum load on the truck traversing that arc

The limit of the model is the discretization of the time. The authors extended the formulation by adding some constraints which combine the continuous and discrete representation of time. The authors make systematic use of integer linear programs which are solved by CPLEX. This approach is computationally expensive and considerably restricts the size of the instances that can be solved within reasonable time. The authors therefore propose a two-phase heuristic. They first solve the routing part by removing the integrality constraints on time and they then solve the loading and unloading subproblem.

Forma et al. (2015) later presented a three-step matheuristic for the same problem. In the first step, the stations are clustered on the basis of geographical and bicycle inventory criteria. In the second step a truck is assigned to each cluster. The truck routes within the cluster while tentative inventory decisions are made for each station. In the third step the original repositioning problem is solved assuming that the stations of the same cluster are visited consecutively. The last two steps are formulated as mixed integer linear programs which are solved by CPLEX. This heuristic was tested on instances involving up to 200 stations and three trucks. It was shown to outperform previous algorithms for the same problem.

Schuijbroek et al. (2017) worked on a simplified version of the time indexed model of Raviv et al. (2013) introduced above: mainly for tractability reasons, inventory levels of the stations are not tracked anymore along the repositioning process. Their model is also different in the way user dissatisfaction is computed. For a pick-up station i the authors state that the ratio between the expected satisfied pick-up demand over the expected total pick-up demand should be at least equal to a predefined value \(\beta _i^-\) which is the desired level of service for station i. In a similar way for a delivery station i, they state that the ratio between the expected satisfied rack demand over the expected total rack demand and this ratio should be at least equal to a predefined value \(\beta _i^+\). Knowing these parameters \(\beta _i^-\) and \(\beta _i^+\), they compute the minimal and maximal levels of inventory that should be present at a station by modeling it as single server queueing system (as done for instance by George and Xia (2011) cited in Sect. 3). With respect to the time index model by Raviv et al. (2013), the objective function contains only the cost calculated as the sum of the travel times, while for the level of service the following two constraints are imposed:

$$\begin{aligned} \tiny s_i^0 + \sum _{t \in T}\sum _{v \in V} (y^+_{itv} - y^-_{itv}) \;&\ge \;s_i^{\min } \end{aligned}$$
(6.14)
$$\begin{aligned} s_i^0 + \sum _{t \in T}\sum _{v \in V} (y^+_{itv} - y^-_{itv}) \;&\le \;s_i^{\max }, \end{aligned}$$
(6.15)

where \(y^+_{itv}\) and \(y^-_{itv}\) are the variables indicating the quantity of bicycles picked-up or delivered in a node i by truck v at the instant t. This model is solved through a cluster-first, route-second heuristic which yields high quality solutions on real instances.

Benchimol et al. (2011) proposed a simple model whose merit is mostly academic. They consider a single truck that repositions bicycles in order to bring the inventory of each station to a predetermined value. Their objective is to minimize the routing cost. The authors have studied the complexity of the problem. They also developed approximation algorithms and proved that the problem is polynomially solvable when the graph is a tree. They left the complexity status of the case when the graph is a cycle as an open question. Krumke et al. (2013) developed an approximation algorithm for a similar case but using several trucks instead of only one.

Chemla et al. (2013b) revisited the Benchimol et al. model and proposed a relaxation of the problem yielding lower bounds. The main difference between the Chemla et al. (2013b) model and those already presented above is that it deals with a single truck problem, as opposed to a multi-truck problem. The authors propose a model based on the maximum number of times a single truck can pass through a node, which can be computed a priori. The idea of counting the number of times a truck passes through a node means that one can disregard the passage time at a node.

Since the model seems to be still intractable, they introduce two relaxations based on the idea of collapsing the graph. The only condition required by the remaining constraints and variables is that the solution must form a Eulerian subgraph. The first relaxation uses two sets of variables: the \(\varvec{z}\) variables indicating which arcs are used and the \(\varvec{y}\) variables being the number of bicycles moved on each arc. The second relaxation is based only on the \(\varvec{z}\) variables:

$$\begin{aligned}&\text {minimize} \sum _{(i,j) \in A} c_{ij} z_{ij} \end{aligned}$$
(6.16)
$$\begin{aligned} \text {subject to}&\nonumber \\&\sum _{j\in N} z_{ij} = \sum _{j\in N} z_{ji}&i \in N \end{aligned}$$
(6.17)
$$\begin{aligned}&\sum _{i\in N\setminus {\{0\}}} z_{0i} = 1 \end{aligned}$$
(6.18)
$$\begin{aligned}&\sum _{(i,j) \in \delta ^+(S)} z_{ij} \ge \mu (S),&S \subseteq N\setminus \{0\} \end{aligned}$$
(6.19)
$$\begin{aligned}&\sum _{(i,j) \in \delta ^+(S)\setminus \delta (0)} z_{ij} \ge \left\lceil \frac{d(S)}{Q}\right\rceil&S \subseteq N \end{aligned}$$
(6.20)
$$\begin{aligned}&z_{ij} \ge 0 \text{ and } \text{ integer }&(i,j) \in A. \end{aligned}$$
(6.21)

The set \(\delta ^+(S)\) is defined by \(\{(i,j) \in A : i \in S; j \in \bar{S}\}\). The parameter Q is the capacity of the truck. The quantity d(S) is defined as \(\sum _{i \in S} d_i\) , where \(d_i\) is the number of bicycles to be added to station i when it is positive, and the number of bicycles to be removed from i when it is negative. The quantity \(\mu (S)\) is equal to 1 if there is at least one station i in S with \(d_i\ne 0\), and 0 otherwise. Constraints (6.17) are the flow conservation constraints. Constraints (6.18) state that only one truck is used. Constraints (6.19) impose connectivity. Constraints (6.20) ensure that the total inventory of any subset S of stations is brought to its target value, while respecting the capacity of the truck.

An interesting feature of the Chemla et al. (2013b) paper is the proof that given a routing solution, it is possible to check whether it is feasible in terms of the number of bicycles loaded and unloaded by solving a maximum flow problem. The latter property was embedded within a tabu search framework capable of computing high quality solutions within reasonable times.

This approach was improved in the work by Erdoğan et al. (2015). The improvement consists of using a logarithmic exact encoding of the integer variables modeling the multiple visits, which was an issue of the previous approach. Rainer-Harbach et al. (2015) proposed an efficient local search algorithm and some variations of it for a generalization of this problem, considering the case of multiple trucks and with a target inventory value that is not a hard constraint, but imposed as a penalty in the objective function. Di Gaspero et al. (2013a, b) applied constraint programming to the same problem. The difficulty of the static repositioning problem with a fleet of trucks relies on the fact that multiple visits to stations are allowed. It seems that there is yet no efficient exact method for solving this variant.

Erdoğan et al. (2014) proposed the first exact algorithm for this problem in the context were the inventory of each station must lie within a predetermined interval. They developed and implemented a Benders decomposition scheme and a branch-and-cut algorithm for this problem. Instances involving up to 50 stations were solved to optimality. The problem considered by Erdoğan et al. assumes that the truck visits each station at most once, whereas Chemla et al. allow multiple visits to a same station.

Dell’Amico et al. (2014) studied the static repositioning problem for the case where each station has a specific positive or a negative demand. The authors considered a fleet of capacitated trucks used to redistribute the bicycles throughout the network. Their objective function is to minimize the total routing cost. They view the problem as a one-commodity pickup-and-delivery capacitated truck routing problem. The authors propose four mixed integer linear programming formulations for the problem, which they solve by branch-and-cut. In order to assess the quality of their algorithms the authors introduce 60 benchmark instances derived from 22 real bicycle sharing systems of diverse sizes. The sizes of the instances vary from 13 to 116 stations. The authors were able to optimally solve all instances involving 50 stations and obtained relatively low optimality gaps in most of the remaining cases.

Bruglieri et al. (2014) addressed the repositioning problem for a car-sharing system with electric vehicles. They model the problem via an integer linear program for which two different solving techniques are proposed: one based on CPLEX, and another on a simple effective heuristic. They apply these methods on the instances derived from the Milan road network.

Szeto et al. (2016) considered a single-truck static repositioning problem in which the objective is a weighted sum of penalties for unmet customer demand and routing costs. The problem was solved by means of an enhanced version of a local search metaheuristic called chemical reaction optimization (CRO), which performed better than a truncated version of CPLEX and than the original CRO version.

Kloimüllner and Raidl (2017) observed than in large bicycle sharing systems, bicycles are typically picked up in full trucks loads as opposed to partial loads. Making this restriction considerably simplifies the modeling of the problem and has only a marginal effect on solution quality, namely on the case of Citybike Wien. The authors modeled the bicycle repositioning problem as a selective unit-capacity pickup and delivery problem with time budgets and solved it by applying a logic-based Benders decomposition technique combined with a branch-and-check procedure. They optimally solved instances with up to 120 stations for the single-truck case and up to 70 stations for the general case.

Ho and Szeto (2017) considered a single truck variant of the arc indexed model of Raviv et al. (2013), and with only the user dissatisfaction term in the objective function. They developed a hybrid large neighbourhood search metaheuristic to solve it, with an application of tabu search to the most promising solution. This algorithm was able to solve instances involving up to 518 stations and five trucks. It outperformed a truncated application of CPLEX and the previous matheuristic of Forma et al. (2015).

Finally, Bulhões et al. (2018) considered the problem of bicycle repositioning with a bound on the number of times each truck can visit a station—for tractability purpose—and where the cost function has a term for the time spent in the loading and unloading process. The authors presented an integer linear programming formulation for the problem, which they solved by branch-and-cut. They also developed an iterated local search metaheuristics employing efficient move evaluation procedures. Experiments conducted on 1,325 new benchmark instances ranging from 10 to 200 vertices showed that multiple visits are only useful for stations whose capacity does not exceed 20. The average gap between the heuristic solution value and the lower bound provided by the branch-and-cut procedure increases with the number of trucks. It was also shown that the number of multiple visits tends to decrease when more trucks are used.

We end this subsection with two repositioning problems occurring in bicycle sharing systems a bit different from most of those studied in this survey. The first one involves bicycles of different types, while the second one works with bicycles that can be left in stations, as usual, but also almost anywhere.

Li et al. (2016b) investigated a static bicycle repositioning problem with multiple bicycle types (for example, one-seat and two-seat bicycles), where bicycles that are in short supply at some stations can be substituted by other bicycle types. This leads to two strategies called substitution and occupancy. The authors formulated the problem as a mixed integer linear program in which the objective function to be minimized consists of the routing cost, penalties for unmet demand, and penalties associated with the substitution and occupancy strategies. Under the substitution strategy, bicycles of a given type that are in short supply at a station can be substituted by bicycles of a different type. Under the occupancy strategy, bicycles of a given type can be placed in a truck compartment dedicated to bicycles of a different type. The problem was modeled as a mixed integer linear program and solved by means of a hybrid genetic metaheuristic with adaptive diversity control for the routing aspect, and a greedy heuristic to determine the loading and unloading decisions at the stations, as well as the substitution and occupancy strategies. Tests showed that the proposed algorithm can yield high-quality solutions within short computing times.

In free-floating bicycle sharing (FFBS) bicycle users can station and lock their bicycle on a standard rack, on any solid frame such as a fence or a lamp-post, or in a standalone mode. Pal and Zhang (2017) modeled and solved a bicycle repositioning problem in this context. The model can accommodate FFBS as well as conventional bicycle stations, as well as one or several repositioning trucks. It was solved by means of a hybrid nested large neighbourhood search metaheuristic with variable neighbourhood descent. Tests were carried out for the single-truck case on benchmark instances as well as on three new set of instances: two related to the Share-A-Bull Bikes program at the Tampa campus of the University of Florida, and one based on the Divvy system in Chicago. Computational results indicate that the algorithm can handle instances of realistic sizes within reasonable computing times. They also confirm that it can deal with the increase in instance size due to the introduction of the FFBS mode within a classical station-based system.

6.2 Dynamic case

There exist some interesting papers on the dynamic case. In contrast to the static case, the users also move the vehicles. The decision maker has to take this feature into account when he decides to perform repositioning. Lu (2013) and Sayarshad et al. (2012) have demonstrated the potential impact of good repositioning policies during the day. These authors do not model in detail the truck routes used for the repositioning, but consider a cost function that aggregates the unsatisfied demand and the estimated repositioning cost. Other authors such as Caggiani and Ottomanelli (2013), Chemla et al. (2013a), and Pfrommer et al. (2014) consider the routes of the relocations performed by the trucks more finely, and consider the case when the trucks have to react in an on-line manner to the current state of the system. This line of research has not yet been fully explored partly because of the modeling difficulties it involves. Note, however, that Krumke et al. (2013) have studied a theoretical version of this problem. These authors obtained a competitive algorithm yielding a bounded deviation with respect to the optimum. All other papers presented in this section deal with the case when the time-dependent demand is known in advance and the truck operations are planned off-line.

Angeloudis et al. (2014) considered the so-called strategic repositioning problem in the context of bicycle sharing. They assume that the stations will be visited on a regular basis throughout the day by a fleet of trucks based at various depots. These trucks should reposition bicycles so as to bring the inventory level of each station close to a target level. The routes are such that any station may be visited by more than one truck. The duration of the truck routes must lie within some intervals which would allow the same truck to perform several tours during the same day. The authors solve the problem in two steps. They first design the truck routes by solving a multi-truck routing problem. They then solve a flow assignment problem to determine the number of bicycles of each arc of each route in order to respect the truck capacity and to bring the inventory level of the station close to its target. The solution methodology was tested on a sample of 30 stations in central London.

Kek et al. (2009) considered a dynamic car relocation problem in which cars must be relocated throughout the day by employees working on different shifts. They formulated the problem as a mixed integer linear program whose objective minimizes a generalized cost that includes relocation cost, staff cost, and penalty costs for rejected demands or rejected truck returns to specific stations. The authors developed a simulator to generate instances based on data collected from the intelligent community truck system (ICVS) which they solved by CPLEX. Using data from a car sharing company in Singapore they showed that their system can reduce staff cost by 50% and car relocations by around 40%.

Contardo et al. (2012) modeled and solved the dynamic case as follows. The time is discretized into T periods. The dynamic aspect of the problem is taken into account by associating a demand f(i, t) for empty racks or bicycles at each station i and each period t. The authors consider a fleet of trucks available for repositioning. They work on a space-time graph whose vertices are the pairs (i, t), for each station i and each time period t (to which vertices for the initial positions of the trucks and a “final state” vertex are added). There are four families of variables: the variables \(y_{(i,t)}\) representing shortage and excess of bicycles at station i for the period t; the variables \(z_{(i,t)}\) representing the number of bicycles left at station i for the period t; the variables \(w_{a,k}\) being binary variable indicating whether truck k traverses arc a in its route; the variables \(x_{a,k}\) being the number of bicycles carried by truck k along arc a. Apart from the w variables, all other variables are continuous. The objective function minimizes the unmet demand. The constraints of the model are the following:

  1. (1)

    flow conservation constraints at each station for each time period;

  2. (2)

    constraints stating that each arc is used at most once;

  3. (3)

    constraints that link the use of an arc with the maximum load of the truck traversing it;

  4. (4)

    flow conservation constraints;

  5. (5)

    non-negativity constraints on variables x, y, and z.

The model is solved by Dantzig–Wolfe decomposition and Benders decomposition.

Kloimüllner et al. (2014) adapted the methods proposed in Rainer-Harbach et al. (2015) to cope with the dynamic case. Interesting features of their approach are a strongly multiobjective function and the fact that they avoid time discretization of the demand function.

Ghosh et al. (2017) developed a large-scale dynamic repositioning and routing model that jointly considers routing costs and future expected demands. They developed two solution methodologies, one based on a natural decomposability of the model into bicycle repositioning and truck routing, the other based on the aggregation of stations. They tested their algorithms by performing simulations on instances containing user movements generated from two real data sets. These tests confirmed that the proposed approach can reduce lost demand and also increase the profit of the bicycle sharing system.

The paper by Zhang et al. (2017) considers a dynamic bicycle repositioning system in which repositioning operations can take place during busy periods as opposed to only during the night when no new user arrivals are expected. The proposed methodology globally considers inventory level forecasts, user arrival forecasts, bicycle repositioning and truck routing. The authors model the problem in a multi-commodity time-space network, which results in a non-linear problem. The model is linearized and solved heuristically in a rolling-horizon mode. The first stage solves the linear relaxation of the model, while the second stage solves a set covering model to assign routes to the repositioning trucks. The authors have conducted extensive simulation experiments on benchmark test-beds to validate and assess their methodology. They concluded that it yields high-quality solutions very efficiently. They also compared their results to those obtained under a night-only repositioning policy to demonstrate the relative superiority of their approach.

Finally, Chiariotti et al. (2018) use a discretization of time and historical data to compute an approximation of the “survival time” of each station in the network. They then compute the cost of replenishing a station and a reward derived from it. This enables them to determine the set of nodes to include in the next replenishment tour. The authors assume that each such tour is executed by means of a single uncapacitated truck. The resulting Traveling Salesman Problem is then solved by means of a nearest-neighbour heuristic. The method was tested on the New York City’s CitiBike network using a full year of data. The proposed approach was compared against two alternative policies: one in which no repositioning takes place, and one in which repositioning takes place twice a day, at 3h00 and at 15h00. They showed the superiority of their dynamic replenishment system over these two policies.

We end this subsection by mentioning a system that mixes rebalancing inventives and dynamic repositioning features. Ghosh and Varakantham (2017) suggested the use of bicycle trailers for the repositioning operations. A bicycle trailer is an add-on to a bicycle that can carry from three to five bicycles at the same time. The idea is that the bicycles can be repositioned by the users themselves using this technology. In a sense this way of operating is akin to crowdsourcing witnessed in parcel delivery. The authors have developed a model that assigns crowdsourcing tasks to potential users under a budget constraint. Tests conducted on several demand scenarios derived from the Boston Hubway bicycle sharing system data showed that the proposed approach is competitive with conventional truck-based repositioning systems.

Table 1 Summary of the reviewed papers
Full size table

7 Conclusion

Table 1 summarizes the content of our survey. It provides for each problem the related references with respect to the decision level. For this table, we gathered the problems of fleet dimensioning and station inventory under a same header called “sizing”.

To conclude, we propose a number of research questions that arose while writing this survey. Our overall impression is that there already exists a wide range of methodological tools to solve most planning problems raised by shared mobility systems. However, open research questions remain. In particular, we sense that some interesting combinatorial questions remain to be investigated. For example, determining the optimal inventory level at each station is an important aspect of the rebalancing problem that has not yet received much attention and should ideally be studied within a theoretical framework. On the methodological side, the design of exact algorithms for the multi-truck repositioning problem has not yet been investigated and seems rather difficult for instances of reasonable sizes. The deterministic case is the most obvious, but this problem cast within a stochastic context is also meaningful. Finally, the study of several repositioning problems in an on-line environment is at the same time relevant and challenging.