Modelling Methods for Planning and Operation of Bike-Sharing Systems

Abstract

Bike-sharing systems (BSSs) are emerging as a popular type of shared vehicle platform where users can rent bicycles without having to own and maintain them. BSSs are ideal for short trips and for connecting to public transit systems. Bicycle usage is associated with several unique characteristics which make planning and operation of BSSs very different from car sharing problems and other traditional transportation modelling approaches. In this paper, we summarize existing literature on strategic planning which involves selecting stations, designing bike paths, and figuring out station capacity. Research on operational measures which include day-to-day and within-day repositioning activities are also collated. Additionally, models for understanding demand, pricing and incentives, maintenance, and other technological aspects are reviewed.

1 Introduction

Automobile usage is on the rise in many parts of the world and cities are actively promoting eco-friendly transportation solutions to reduce traffic congestion and emissions. Bike-sharing systems (BSSs) is one such alternative which can not only serve short-distance trips, but can also enhance connectivity to public transportation networks. In a BSS, customers can pick up and drop off cycles at specific locations or anywhere in the city depending on the type of bikes in the system, locking technology, and payment mechanisms. Most of the current generation BSSs are either free-floating or station-based (Fig. 1). Station-based BSSs may use both docked or geo-fenced dockless bikes. A few examples of BSSs include Capital Bikeshare (CaBi) in Washington, D.C., Citi Bike in New York, Blue Bikes in Boston, and Vélib’ in Paris.

Figure 1:

Docked BSS: Capital Bikeshare, US 1 (left) and Dockless BSS: Mobike, China2 (right).

Like any other transportation system, planning and operation of BSSs require understanding the spatio-temporal demand for cycles in a city. Demand can either be inferred from extensive surveys or past data on traveller movements.3^,4. This knowledge of demand can drive decisions on building dedicated bike lanes, setting up base stations,5 and choosing between pay-per-use and subscription-type services. Supply-side aspects can also in turn influence demand. For example, dedicated bike lanes make bike travel safer and has the potential to increase BSS usage.6,7,^–8

For station-based BSSs, it is important to determine the capacity of each station and distribute the fleet across stations, although these decisions can also be made at an operational level.9,10,^–11 Within-day stochasticity in travel patterns often leads to imbalances in the availability of bikes and parking spots. Having stations that are full or empty can affect ridership and render the system ineffective. To address these situations, cycles are often repositioned from one station to another using trucks12 or by providing price incentives to users for dropping off bikes at nearby high-demand locations.13

When bikes are repositioned using motor vehicles, one must decide how many cycles to move between stations and also determine optimal vehicle routes. Repositioning done during the day, in real-time, is classified as dynamic rebalancing,14^,15 while that carried out at the end of a day, when the system is inactive, is called static rebalancing.12^,16^,17 Periodic maintenance of bikes, vandalism, and theft are some other common problems faced by a service provider of a BSS.

The rest of this review article is structured as follows. In Sect. 2, we discuss the history of BSSs and motivate the need for developing decision support tools for studying planning and operational problems associated with BSSs. In Sect. 3, we discuss research on some of the strategic problems such as bike-lane design, station locations, and dock size selection. Section 4 details various repositioning mechanisms that can be used when operating a BSS. Technological aspects and some emerging phenomena are addressed in Sect. 5 and the conclusions of this study are presented in Sect. 6.

Figure 2:

(Source: Midgley18, Chen et al.19; Picture source:20,21,22,23,^–24).

Generations of BSSs.

2 Background and History

The first BSS started in Amsterdam in 1965 (White bicycle plan) with just fifty bicycles.18 However, a month later, all bikes were either stolen or dumped into canals. The white bicycle plan was a first-generation BSS in which bikes were free to use. Other first-generation BSS examples include Vélos Jaunes in La Rochelle, France (1974) and Green Bike Scheme in Cambridge, UK (1993). Since then, BSSs have undergone many changes. An infographic of the historical development of BSSs through the years is shown in Fig. 2. The second generation of BSS saw the advent of coin deposit stations in which rides were free, but customers had to insert coins into a slot to unlock bikes and could retrieve them once the bikes were returned. The first coin deposit bike program called Bycyklen started in Copenhagen in 1991.19 In 1995, it also became the first large-scale BSS with around 1,100 bikes. This system was still vulnerable to theft due to anonymity of users. The use of automated docked stations with registered customers marked the beginning of the third generation of BSSs. This greatly reduced vandalism and theft issues associated with the previous generations of BSSs. Such a system first appeared in Portsmouth University, England (1996) and students had to pay for membership and bikes could be rented using a magnetic card. Other examples of third generation BSSs include LE Vélo STAR

in Rennes (1998), Bicing in Barcelona (2007), Cycle Hire in London (2010), and Citi Bike in New York (2013). The fourth-generation bikes came into existence in 2005 with the Vélo’v program in France. This system was operated by an advertising firm JCDecaux and was equipped with smart bikes that could be accessed using a mobile app. The smart technology-based system provided real-time information on bike availability.19^,25 Most BSSs in the recent past belong to the fifth generation in which dockless bikes are used in a free-floating or station-based set up. These systems have lower setup costs and hence have grown rapidly in many cities.

By December 2016, about a thousand cities in the world had a bike-sharing program.26Mobike, a dockless BSS, is the world’s largest bike-sharing operator. As of 2018, Mobike operated in over 19 countries and 200 cities.27 One of the large-scale station-based BSSs is the Hangzhou Public Bicycle System in China, which comprises of 2,965 stations and approximately 69,750 bicycles,28, with plans to expand to 175,000 bicycles by 2020.29 Bike-sharing programs have grown exponentially in the last decade, particularly in Asia. For instance, thirteen of the world’s fifteen largest BSSs are in China.30

Although BSSs have been encouraged by public agencies and users around the world, service providers such as Mobike, Ofo, and Pedl had to shut down operations in many cities due to high maintenance costs, low profits, theft, and vandalism.31,32,^–33 Some of the new technologies like global positioning system (GPS), anti-theft alerts, and high-tech handlebars introduced in the fourth and fifth generation dockless bicycles have the potential to address these issues to a certain extent.34^,35

Figure 3:

(Source: Alan36).

Roadside dumping of bicycles in Xiamen, Fujian province, Chinan

Also, cycling is not perceived as a safe commute mode, especially in mixed traffic, and the lack of dedicated bike lanes in most places proves to be a major hurdle for the success of BSSs. Further, while BSSs work well in controlled environments such as office and university campuses, scaling them to a city level can be extremely challenging especially for dockless free-floating systems. Often, bikes are left at remote locations where there is no demand, and this affects the utilization rates of cycles. As bicycles are fairly inexpensive, service providers tend to add more bikes to the system as a knee-jerk reaction, but the oversupply of bikes has resulted in many abandoned and broken bicycles, especially in China (see Fig. 3). These observations strongly motivate the need for planning and operating BSSs in an efficient manner.

3 Strategic Planning

Strategic planning problems in the context of a BSS typically involve designing the bike path network and determining the number and locations of bike stations. These decisions must consider construction costs, the effect of terrain, customer service level (which can be measured by the coverage level, bicycle availability, and user out-of-pocket costs), and the impact on existing automobile traffic. For instance, station location decisions must make sure that cycles are at a convenient walking distance (roughly 300–500 m) from the actual trip origins and destinations.37 Geographical factors are crucial not only for bike lane design, but also for locating bike stations. For example, in Brisbane, it was observed that CityCycle users avoid returning bicycles to higher-elevation stations.38 Stations must also be designed such that there is enough curb-side space to account for surges in pickups and dropoffs.

A key input to these decisions is the knowledge of demand for bike sharing, which can be estimated using census data,39 stated-preference surveys, and by observing the travel patterns of commuters who might potentially shift from other modes to cycling.40 BSS planners must allocate bicycles at different stations in a manner that is consistent with the actual demand of customers. Most studies in literature focus on understanding demand patterns after a BSS system is in place. For example, statistical regression-based forecasting and time-series methods can be used to predict the spatio-temporal activity of users. These have been successfully demonstrated using data from Bicing in Barcelona41^,42 and Vélo’v in Lyon. 3^,4 Others have used a data mining approach43 to cluster BSS stations according to the rate of bike pickups and dropoffs using Citybike Wien data from Vienna. Clustering methods were also used to identify ‘similar’ stations for analysing the system before and after a policy change.44 Demand prediction for existing BSSs was also successfully done using machine learning and artificial intelligence methods by learning customer behaviour from observed data and using it for prediction.45,46,47,48,^–49^,50 However, these predictions are yet to be fully exploited in existing research on operational planning that we will discuss in Sect. 4.

Customer demand in existing BSSs is heavily influenced by supply, and literature on demand forecasting before a BSS is planned remains sparse. Traditional demand models involving trip generations and distribution were extended to bicycling by Turner51 and Landis52. A few researchers have proposed GIS-based methods that can provide macro-level bicycle demand using socio-demographic and geographical attributes.53,54,^–55 Using daily trips by different modes and stated preference surveys that provided mode shift propensities,40 forecasted the bike trips for Philadelphia, US assuming three different levels of system usage. In the absence of elaborate travel demand models or surveys, studies that understand factors influencing bike trips can be transferred to other cities for predicting demand.56 For example, Faghih-Imani et al.57 analyses the role of factors such as population density, accessibility, points of interest, and supply-side features such as the number of stations per unit area and capacity on bicylce trip generation and attractions. Data from Barcelona and Seville, Spain were used in this work to estimate model parameters using a restricted maximum likelihood approach. In another work, Singhvi et al.58 uses taxi data from New York City, US along with population information to build regression models that predict bicycle usage. Other predictors that have been found to significantly influence bike demand are weather59 and seasons60.

Bicycle trips may also be used for first- and last-mile access to transit systems. In such cases, transit ridership and accessibility must be factored in when estimating the demand for a BSS. In the next subsections, we discuss a few mathematical models that have tried to incorporate the integrated effects of various input parameters in the design of a BSS. For better readability, we have altered the notation from the original papers at several places to describe similar variables and parameters wherever possible.

3.1 Route Design

Researchers have addressed the bike network design problem in multiple ways using different objectives and assumptions. For example,61 formulated models that connect origin-destination (OD) pairs with bike paths while minimizing total cost and meeting a specified bicycling level of service. The framework considers a network $G=(R,S)$, where R is the set of intersections and S is the set of roads. Each roadway segment has an associated cost $c_{ij}$ to make it cyclable. The cost associated with improving each intersection is $d_{i}$. Decision variable $\delta _{ij}$ is 1 if roadway segment $(i,j) \in S$ is improved and is 0 otherwise. Similarly, $\gamma _{i}$ is 1 if intersection $i \in R$ is improved and is 0 otherwise. The objective can thus be mathematically expressed as follows.

$$\begin{aligned} \min \bigg (\sum \limits _{(i,j) \in S} c_{ij} \delta _{ij} + \sum \limits _{i \in R} d_{i} \gamma _{i} \bigg ) \end{aligned}$$

(1)

Their formulation included flow-balance constraints, connectivity constraints for every OD pair, a constraint that limits the path length beyond which users will not cycle, constraints that ensure a suitable level of service, and constraints that select intersections belonging to a chosen path. Extensions in which these constraints are reformulated to speed up computation were also proposed. The model was solved using a branch-and-bound method for small problem instances and the authors studied the effect of the level of service and the number of OD pairs on the total cost.

Others have formulated bi-level programs for the bike route design problem.62 At the upper level, benefits to cars and cyclists were considered, and at the lower level, an assignment model for bikes and automobile traffic was optimized. A genetic algorithm was used to solve the bi-level formulation on medium-sized examples using a special crossover and mutation technique. Another optimization framework was proposed by Mauttone et al.63 in which the roadway network could have sections with no cycling infrastructure and the total number of discontinuities in bike paths was minimized. A mixed-integer multi-commodity flow problem was proposed, and a metaheuristic was used to handle large problem instances, including a test case from the city of Montevideo, Uruguay. The optimal bike path design was also addressed in64 to separate bicyclists from motorized vehicles for an existing transportation network. The objective was to maximize the cyclists’ utilities assuming that their route choices could be modelled using a path-size logit framework. The problem was formulated as a mixed-integer linear program (MILP) and tested on the Sioux Falls and Anaheim, US networks using a global solver and a metaheuristic.

While previously mentioned studies considered a single objective function, Zhu and Zhu 65 formulated a multi-objective function that comprised of accessibility, bicycle level of service, number of intersections, and the construction cost. (Since intersections pose safety risk for bicyclists, they are assumed to prefer connected bikeway networks over fragmented ones.66^,67). Accessibility was measured by not only considering the connectivity between the points of interest, but by also considering the travel budget of commuters on the road. The problem was solved by an augmented $\epsilon$-constraint method using hypothetical data from Jurong Lake District in Singapore. A few other route design models have been summarized in Table 1.

Table 1: Summary of route design models.

3.2 Facility Location

Research on station location selection is heavily influenced by the hub location73 and maximal covering problem.74 In the basic version of the single hub location problem, it is assumed that there are n nodes which act as both origins and destinations. The objective is to find the optimal hub location such that the cost of transporting demand between nodes via the hub is minimized. That is, the hub acts as a switch for all interactions in the network. Suppose that the flow between OD pair (i, j) is denoted by $w_{ij}$ and $c_{ij}$ represents the distance between nodes i and j. The optimal location of the hub q can be obtained by solving

$$\begin{aligned} \min \limits _{q} \sum \limits _{i} \sum \limits _{j} w_{ij} \big (c_{iq} + c_{qj}\big ) \end{aligned}$$

(2)

Note that in the absence of set up costs, there is no requirement of a hub since,

$$\begin{aligned} \sum \limits _{i} \sum \limits _{j} w_{ij} c_{ij} \le \sum \limits _{i} \sum \limits _{j} w_{ij} \big (c_{iq} + c_{qj}\big ) \end{aligned}$$

(3)

is satisfied if triangle inequality is assumed. However, if K is the cost associated with setting up each inter-city route, a hub is needed if

$$\begin{aligned}&\sum \limits _{i} \sum \limits _{j} w_{ij} \big (c_{iq} + c_{qj}\big ) + K n \\&\quad < \sum \limits _{i} \sum \limits _{j} w_{ij} c_{ij}+ K \frac{n(n-1)}{2} \end{aligned}$$

(4)

The Kn term on the left-hand side of inequality (4) corresponds to the cost of connecting each of the n stations to the hub. On the other hand, if routes were to be built between each pair of stations without creating a hub, the construction cost would be $Kn(n-1)/2$, since ${n}\atopwithdelims (){2}$ arcs have to be built.

The bike station design problem is not exactly similar to this model since it involves a pick up and a drop off. Such scenarios resemble a two-hub facility location problem.73 Suppose 1 and 2 represent two hub locations and let $u_i$ be 1 if an origin or a destination i is serviced by hub 1 and be set to 0 otherwise. Likewise, let $v_i$ be 1 if an origin or a destination i is serviced by hub 2 and is 0 otherwise. Note that when a node can be served by both hubs, the one nearest to the node is assumed to serve the node and the binary variable corresponding to the other hub is set to 0. The goal is to send the OD flows passing through both hubs. The hub locations are chosen such that the overall transportation cost is minimized.

$$\begin{aligned}&\min \sum \limits _{i} \sum \limits _{j} w_{ij} \Big ( u_i v_j(c_{i1} + c_{12} + c_{j2}) \\&\quad +u_j v_i(c_{i2} + c_{21} + c_{j1})\Big ) \end{aligned}$$

(5)

The problem of locating multiple facilities is also widely addressed in the literature using a maximum covering model or a p-median problem.74,75,76,^–77 In the maximum covering model, the objective is to locate a fixed number of facilities to maximize the total demand that can be covered assuming that demand located farther than S units from a hub cannot be served. Mathematically, it can be expressed as

$$\begin{aligned} \max _J \sum \limits _{i \in I} a_i y_i \end{aligned}$$

(6)

where I and J are the set of demand nodes and facility sites respectively, $a_i$ is the demand at node i, decision variable $x_j$ is 1 if a facility is opened at $j \in J$ and is 0 otherwise, $N_i =\{j \in J\ | d_{ij} \le S\}$ is a subset of facility sites which can serve demand from i, and $y_i$ is 1 if the demand at i can be served and is 0 otherwise.

The x and y variables are connected using constraints $\sum _{j \in N_i} x_j \ge y_i \, \forall \, i \in I$ and $\sum _{j \in J} x_j = p$, where p is the total number of facilities.

The p-median problem on the contrary minimizes the total cost of serving the demand and can be expressed as

$$\begin{aligned} \min \sum _{i \in I} \sum _{j \in J} a_i c_{ij} w_{ij} \end{aligned}$$

(7)

where $c_{ij}$ represents the unit cost of serving demand at i using a facility at j and $w_{ij}$ is the fraction of the total demand $a_i$ served by the facility at j. (Hence, it must satisfy $\sum _{j \in J} w_{ij} = 1 \, \forall \, i \in I$.) As before, a binary variable $x_{j}$ is used to represent facility location decisions and $\sum _{j \in J} x_j = p$ ensures that p such locations are opened. Finally, the x and the w variables are connected using an additional constraint $w_{ij} \le x_j \, \forall \, i \in I, j \in J$.

There are a few key differences in bicycle networks that prohibit the direct use of standard facility location models. For instance, the hub location model implicitly assumes that the flow from a certain node can first be sent to hub 1 or 2 (whichever is closer) and it can be redirected to the destination. However, in a BSS, some trips may not be feasible if the stations are far from the actual origins and destinations. Second, there are more than two hubs in a bike network. On the other hand, the maximum covering and the p-median problems can be used to model unmet demand, but they are applicable to single commodity, single source/destination-type flows whereas locating bike stations involves a multi-commodity, multiple OD pair problem.

One of the first models to tackle these issues was proposed by Lin and Yang37 using multiple objectives and found the optimal bicycle locations along with the paths needed for connectivity. The formulation, explained below, balances the cost incurred and the level of service provided to customers.

Let $d_{rs}$ denote the distance between nodes r and s (which could be trip origins or destinations or bike stations). Different components of the objective are weighted by parameters to convert it to cost units. For example, $\alpha$, $\beta$, and $\gamma$ represent the unit travelling cost from the trip origin to the pickup bike station, between the pickup and the dropoff bike station, and the dropoff bike station to the trip destination respectively. Assume that the yearly mean travel demand between OD pair (i, j) is $\lambda _{ij}$ and decision variable $y_{iklj}$ is 1 if the demand between i and j passes through bike stations k and l and is 0 otherwise. Denoting the set of origins, destinations, and bike stations as I, J, and K, respectively, the transportation cost component of the objective was formulated as

$$\begin{aligned}&\alpha \sum \limits _{i \in I} \sum \limits _{k \in K} d_{ik} \sum \limits _{l \in K} \sum \limits _{j \in J} y_{iklj} \lambda _{ij} \\&\quad+ \beta \sum \limits _{k \in K} \sum \limits _{l \in K} d_{kl} \sum \limits _{i \in I} \sum \limits _{j \in J} y_{iklj} \lambda _{ij} \\&\quad + \gamma \sum \limits _{l \in K} \sum \limits _{j \in J} d_{lj} \sum \limits _{i \in I} \sum \limits _{k \in K} y_{iklj} \lambda _{ij} \end{aligned}$$

(8)

To address the issue of unmet demand, the authors introduce a penalty term

$$\begin{aligned}&\delta \Big (\sum \limits _{i \in I} \sum \limits _{k \in K} q_{ik} \sum \limits _{l \in K} \sum \limits _{j \in J} y_{iklj} \lambda _{ij} \\&\quad + \sum \limits _{j \in J} \sum \limits _{l \in K} q_{jl} \sum \limits _{k \in K} \sum \limits _{i \in I} y_{iklj} \lambda _{ij} \Big ) \end{aligned}$$

(9)

where $\delta$ is the additional unit cost of uncovered demand and $q_{rs}$ is 1 if a bike station located at s cannot cover demand starting or ending at r. In addition, setup costs

$$\begin{aligned} \sum \limits _{k \in K} f_{k}x_{k} +\sum \limits _{k \in K} \sum \limits _{l \in K} c_{kl} z_{kl} \end{aligned}$$

(10)

are introduced to model the cost of constructing stations and bike lanes. Here, the binary decision variable $x_k$ is 1 if a station is opened at k and $z_{kl}$ is set to 1 if a bike lane is needed between stations k and l. The associated costs are $f_k$ and $c_{kl}$ respectively. Finally, the authors also include a couple of extra terms in the objective that reflect the average holding costs and the cost of replenishing bicycles assuming some stochasticity in demands.

Consistency between the decision variables is achieved using constraints. For example, if bike stations are opened at two nodes, a bike lane could be built between them using

$$\begin{aligned} 2 z_{kl} \le x_k + x_l \, \forall \, k \in K, l \in K \backslash \{k\} \end{aligned}$$

(11)

Similarly, demand can be routed between two stations only if a bike lane connects them and this is modelled using

$$\begin{aligned} y_{iklj} \le z_{kl} \, \forall \, i \in I, k \in K, l \in K \backslash \{k\}, j \in J \end{aligned}$$

(12)

Finally, constraint (13) is used to route the demand between each OD pair along some path connecting the OD pair.

$$\begin{aligned} \sum \limits _{k \in K} \sum \limits _{l \in K \backslash \{k\}} y_{iklj} =1 \, \forall \, i \in I, j \in J \end{aligned}$$

(13)

Some researchers have also proposed tools to locate bike stations while simultaneously modelling the interactions with other modes. For example, Romero et al.9 capture the mode choices between cars and a BSS using a multinomial logit framework within a bi-level optimization program that determines the optimal bike station locations. Using data from Santander City, Spain, a genetic algorithm was used to demonstrate the applicability of their model. Results indicate that optimally located bikes can induce a significant mode shift from cars to cycles. In another line of related, but tangential, work on car sharing, Kumar and Bierlaire78 developed regression models that predict the demand for shared services as a function of transit ridership, personal car usage, and other land use attributes and integrated the outputs with an optimization model to select car stations. A few other facility location models have been summarized in Table 2.

Table 2: Summary of facility location models.

3.3 Capacity Allocation

After deciding the locations of the bike stations and paths, another key strategic decision that is crucial to a station-based BSS is the capacity allocation of bikes at each station. Many studies have modelled this jointly with the location decisions of bicycles.81^,83 In this section, we will discuss one model proposed by Lin et al.6 that builds on the formulation by Lin and Yang37 discussed earlier.

In addition to (8)–(10),6 introduce a term $h \sum _{k \in K} s_k$ that reflects the overall holding costs, where h is the inventory holding cost of a bicycle and $s_k$ is a non-negative decision variable representing the inventory level at station k. The yearly travel demand between OD pair (i, j) is assumed to follow a Poisson distribution with rate $\lambda _{ij}$ and hence the daily demand at station k was computed using

$$\begin{aligned} \Lambda _k = \frac{1}{T} \sum \limits _{i \in I} \sum \limits _{l \in K \backslash \{k \} } \sum \limits _{j \in J} y_{iklj} \lambda _{ij} \, \forall \, k \in K \end{aligned}$$

(14)

where T is the number of days in a year. Assuming that the lead time for replenishing bikes at a station k is $\tau _k$, and a desired level of service is set by the probability of running out of stock $(1-\gamma _k)$, the inventory level required $s_k$ can be expressed as

$$\begin{aligned}\begin{aligned} s_k&= \min \Bigg \{s : \sum \limits _{q=0}^{s-1} \frac{\mathrm{{e}}^{-\Lambda _k \tau _k} (\Lambda _k \tau _k)^q}{q!} \ge \gamma _k \Bigg \} \\ &\quad \forall k \in K \end{aligned}\end{aligned}$$

(15)

Constraints (14) and (15) are both non-linear and make the problem highly intractable. The authors proposed an iterative greedy heuristic in which for a given set of bike stations, lanes and inventory levels are chosen one at a time to reduce the overall costs. Their method was demonstrated on a hypothetical test network and sensitivity of optimum inventory levels with respect to the frequency of replenishment and network design was studied.

Some researchers have proposed MILPs to address the capacity allocation problem. For instance, Sayarshad et al.84 formulated a multi-period optimization model in which the demand was known, and the objective function included revenue from trips, relocation costs, capital and maintenance costs, and a penalty for unmet demand. A similar multi-period MILP was suggested by Martinez et al.5 and it also included relocation decisions. Heuristics that decompose the problem by time periods were proposed and tested on a network from Lisbon, Portugal. A few other capacity allocation models have been summarized in Table 3.

Table 3: Summary of capacity allocation models.

Figure 4:

(Source: Citybike Wien System Map90, Capital Bikeshare System Map91).

Station inventory levels of Citybike Wien (left) and CaBi (right).

4 Operational Planning

As discussed in Sect. 3, strategic planning can be used to locate stations and allocate an optimum number of bicycles at those locations. However, at an operational level, uncertainty in demands and maintenance requirements create supply imbalances rendering re-optimization necessary. For station-based systems, these types of stochastic events might make some stations go empty, preventing customers to rent a bicycle. It may also happen that some stations become full and force customers to wait or return their cycles at another station. Supply imbalances in free-floating systems do not affect dropoffs but demand fluctuations can make it difficult to find a bike in the first place. Such departures from strategic plans can lead to loss of customers and affect the overall performance of a BSS. Figure 4 shows a snapshot of the inventory levels for a portion of Citybike Wien in Vienna, Austria and CaBi, Washington D.C., US and one can notice bicycle stations which are nearly full or empty.

To address these situations, day-to-day and within-day operational measures such as relocating bicycles from one place to another is a must. These repositioning tasks are usually carried out using trucks or bike-trailers (see Fig. 5). In addition, one can provide incentives that might nudge customers to pick up (or drop off) their bicycles at nearby stations that are close to capacity (or short of bicycles). Repositioning strategies are mainly classified as static and dynamic depending on the timing of repositioning. Some authors also classify it as online and offline methods and the subtle distinction in the nomenclature will be discussed in Sect. 4.3.

Figure 5:

(Source: Panhard92).

Rebalancing using a trailer.

4.1 Static Repositioning

In static repositioning, bicycles are rebalanced during the night when customer movements are minimal. Past data may be used to forecast demand for bikes at different stations and guide the repositioning operation. The repositioning and forecasting periods do not overlap as shown in Fig. 6 and hence real-time demand variations are not addressed. Nevertheless, moving bicycles during the night is convenient from the operator’s perspective since there are no parking and congestion issues. Modelling within-day demand fluctuations requires a more dynamic approach and will be discussed in Sect. 4.2.

Figure 6:

(Source: Zhang et al.15).

Static bicycle repositioning.

Most research on static repositioning is geared towards addressing the following key questions. First, how many cycles should be moved between different pairs of stations. (This problem is also referred to as the inventory balancing problem.) Second, what is the most efficient way to route vehicles which move these bicycles (which constitutes the routing problem). These two problems are often jointly solved using optimization models with integer decision variables.

A commonly used target stock level in the inventory balancing problem is the number determined from the capacity allocation problem. Alternately, researchers have also proposed models in which the inventory level at the end of the rebalancing procedure falls within an ideal pre-determined interval.93 The limits of such intervals can be obtained from Markovian queuing models with different objectives by forecasting the operations on the subsequent day.

For example, Schuijbroek et al.17 suppose that C is the capacity of a station and the state transitions for the number of bicycles at the station occur according to a non-stationary $M_t/M_t/1/C$ (in Kendall notation) process. That is, the inter-arrival times for returns and pickups at time t are distributed exponentially with rates $\lambda (t)$ and $\mu (t)$ respectively (see Fig. 7). These transition rates are estimated using maximum likelihood methods. Additional assumptions are often needed when developing a demand forecasting tool since lost demand due to empty or full stations is censored and is not a part of the observed data.

Assuming that a station starts with s cycles after static repositioning, let $p(s,s',t)$ be the probability of finding $s'$ bikes at time t on the next day. These transition rates satisfy Chapman-Kolmogorov equations. To calculate the expected fraction of successful pickups and dropoffs, the authors define

$$\begin{aligned} g(s,0,T) = \frac{\int _0^T \mu (t)(1-p(s,0,t)) \mathrm{{d}}t}{\int _0^T \mu (t) \mathrm{{d}}t} \end{aligned}$$

(16)

$$\begin{aligned} g(s,C,T) = \frac{\int _0^T \lambda (t)(1-p(s,C,t)) \mathrm{{d}}t}{\int _0^T \lambda (t) \mathrm{{d}}t} \end{aligned}$$

(17)

where T is the time limit for the next day’s operations. The bounds for the desired inventory level at the end of the static rebalancing procedure is defined as

$$\begin{aligned} s^{\min }&= \min \, \big \{s : g(s,0,T) \ge \beta ^{-} \big \} \end{aligned}$$

(18)

$$\begin{aligned} s^{\max }&= \max \big \{s : g(s,C,T) \ge \beta ^{+} \big \} \end{aligned}$$

(19)

where $\beta ^{-}$ and $\beta ^{+}$ are desired service levels for the next day.

Figure 7:

(Source: Schuijbroek et al.17).

Markov chain for station inventory.

Many studies also allow deviations from the desired inventory levels but penalize them in objective functions.94^,95 The penalty could just be an absolute value of the difference between the desired and achievable inventory level or could factor in the next day’s operations. For instance, Raviv et al.95 assume a penalty for out-of-stock pickup and dropoff events as $\phi$ and $\psi$ respectively and define a function to describe the expected shortage using

$$\begin{aligned} F(s) = \int _0^T \Big ( p(s,0,t) \phi + p(s,C,t) \psi \Big ) \mathrm{{d}}t \end{aligned}$$

(20)

An approximation of this function was used as a penalty term in the objective function of an MILP. The authors used data from Tel-O-Fun in Tel Aviv, Israel to estimate the model parameters.

Inventory levels after rebalancing have also been set using a chance constraint approach96. In this method, the number of pickups ($\xi _i^{+})$ and dropoffs ($\xi _i^{-}$) at a station $i \in N$ are assumed random and one of the constraints in the model ensures that the probability of successful pickups and dropoffs are greater than a pre-specified parameter p. Specifically, let $r_i$ and $C_i$ denote the current inventory level and capacity of station i respectively. If $u_{ij}$ indicates the number of bicycles moved from station i to station j, then the number of available bikes at a station i is $r_i + \xi _i^{-} + \sum _{j} ( u_{ji} - u_{ij})$. Likewise, the number of available spaces at station i is $C_i - r_i + \xi _i^{+} + \sum _j (u_{ij} - u_{ji})$. The chance constraint can thus be written as

$$\begin{aligned}&{\mathbb {P}} \left( r_i + \xi _i^{-} + \sum _{j} \big ( u_{ji} - u_{ij}\big ) \ge \xi _i^{+},\right. \\&\left. \quad C_i - r_i + \xi _i^{+} + \sum _j \big (u_{ij} - u_{ji}\big ) \right.\\&\quad\left.\ge \xi _{i}^{-} \, \forall \, i \in N \vphantom{\sum _{j}}\right) \ge p \end{aligned}$$

(21)

After deciding the target inventory levels or their intervals, the routing problem needs to be solved to figure out how a single or multiple vehicles can redistribute cycles in an optimal manner. The single vehicle routing problem can be formulated as a one-commodity pickup and delivery travelling salesman problem (1-PDTSP).97 To mathematically model this problem, consider a complete graph (without self-loops) $G = (N,A)$ where $N=\{0, 1,\ldots , n\}$ represents the set of bike stations and A is the set of arcs. The assumption that the graph is complete is not necessary but is made only to simplify the notation. Suppose node 0 represents the depot where the vehicle (with capacity Q) that is used to move bicycles begins its trip and suppose nodes $1, \ldots , n$ denote the other stations in the network. Let $c_{ij}$ be the travel costs between i and j and binary decision variable $x_{ij}$ be 1 if the vehicle takes arc (i, j) and is 0 otherwise. Each station i is assumed to have a demand/supply $q_i = r_i - s_i$ which is the deficit or excess when compared to the desired inventory $s_i$. If $q_i >0$, station i is a pickup node and if $q_i < 0$, it is a dropoff node. A second decision variable $y_{ij}$ represents the total number of cycles that are carried by the vehicle on arc (i, j). Supposing that the total deficit equals the total excess (this can be easily relaxed assuming that the depot has extra inventory or space for extra cycles), the 1-PDTSP can be formulated as follows.

$$\begin{aligned} \min&\, \, \sum _{(i,j) \in A} c_{ij} x_{ij}&\end{aligned}$$

(22)

$$\begin{aligned} \text {s.t.}&\, \, \, \sum _{j \in N} x_{ij} = \sum _{h \in N} x_{hi} = 1 \quad&\forall \, i \in N \end{aligned}$$

(23)

$$\begin{aligned}&\, \, \sum _{i \in S} \sum _{j \notin S} x_{ij} \ge 1 \quad&\forall \, S \subset N , S \ne \emptyset \end{aligned}$$

(24)

$$\begin{aligned}&\, \, \sum _{j \in N} y_{ij} - \sum _{h \in N} y_{hi} = q_i \quad&\forall \, i \in N \end{aligned}$$

(25)

$$\begin{aligned}&\, \, \, 0 \le y_{ij} \le Q x_{ij} \quad&\forall \, (i,j) \in A \end{aligned}$$

(26)

$$\begin{aligned}&\, \, \, x_{ij} \in \{0,1\} \quad&\forall \, (i,j) \in A \end{aligned}$$

(27)

Constraint (23) ensures that each station is visited exactly once and (24) eliminates subtours. Flow conservation of the cycles is guaranteed using (25) and inequality (26) forces the flow variables to be zero on links that are not traversed by the vehicle. This formulation was extended by Raviv et al.95 to the multiple vehicle scenario using a three-index formulation with less restrictive assumptions. Suppose that previous notation is modified such that $x_{ijv}$ is a decision variable which is 1 if vehicle $v \in V$ traverses arc (i, j) and is 0 otherwise. Similar to (23), flow conservation of vehicles can be expressed as

$$\begin{aligned}&\, \, \, \sum _{j \in N} x_{ijv} = \sum _{h \in N} x_{hiv} = 1 \quad&\forall \, i \in N, v \in V \end{aligned}$$

(28)

$$\begin{aligned}&\, \, \sum _{j \in N} x_{ijv} \le 1 \quad&\forall \, i \subset N \backslash \{0\} , v \in V \end{aligned}$$

(29)

Note that (29) makes sure that each vehicle can visit a station at most once. It is also possible that a station is visited by more than one vehicle. Just like the 1-PDTSP, Raviv et al.95 define another variable $y_{ijv}$ which indicates the number of cycles carried by vehicle v while traversing arc (i, j). These are linked to the $x_{ijv}$ variables in a manner similar to (26) as shown below

$$\begin{aligned} 0 \le y_{ijv} \le Q_v x_{ijv} \quad \forall \, (i,j) \in A, v \in V \end{aligned}$$

(30)

where $Q_v$ is the capacity of vehicle v. Two new decision variables $z_{iv}^{+}$ and $z_{iv}^{-}$ are introduced which represent the number of bikes added and removed by vehicle v at station i respectively. Hence, we may write $q_i = r_i - s_i = \sum _{v \in V} (z_{iv}^{-} - z_{iv}^{+})$ and flow conservation of bicycles (25) can be recast as

$$\begin{aligned} \sum _{j \in N} y_{ijv} - \sum _{h \in N} y_{hiv} = z_{iv}^{-} - z_{iv}^{+} \quad \forall \, i \in N, v \in V \end{aligned}$$

(31)

Assuming that we need not meet the desired inventory level exactly (i.e., we need not clear the excess or deficits), the following sets of constraints on the z variables follow naturally.

$$\begin{aligned}&\, \, \, \sum _{v \in V} z_{iv}^{-} \le r_i \quad&\forall \, i \in N \end{aligned}$$

(32)

$$\begin{aligned}&\, \, \, \sum _{v \in V} z_{iv}^{+} \le C_i - r_i \quad&\forall \, i \in N \end{aligned}$$

(33)

$$\begin{aligned}&\, \, \, \sum _{i \in N} \Big ( z_{iv}^{+} - z_{iv}^{-} \Big ) = 0 \quad&\forall \, v \in V \end{aligned}$$

(34)

Subtour elimination constraints for each vehicle were described in the form proposed by Miller et al.98 as shown in (35) using an additional continuous decision variable $w_{iv}$ and a sufficient large number M.

$$\begin{aligned} &w_{jv} - w_{iv} + M(1-x_{ijv}) \ge 1 \\&\quad \forall \, i \in N, j \in N \backslash \{0\}, v \in V \end{aligned}$$

(35)

The complete formulation is shown below.

$$\begin{aligned} \min&\, \, \sum _{i \in N} f(s_i) + \alpha \sum _{(i,j) \in A} c_{ij} \sum _{v \in V} x_{ijv} \end{aligned}$$

(36)

$$\begin{aligned} \text {s.t.}&\, \, (28) - (35) \\&\, \, \, x_{ijv} \in \{0,1\}, y_{ijv} \ge 0 \quad&\forall \, (i,j) \in A, v \in V \end{aligned}$$

(37)

$$\begin{aligned}&\, \, \, z_{iv}^{-}, z_{iv}^{+} \in {\mathbb {Z}}_+ \quad&\forall \, i \in N, v \in V \end{aligned}$$

(38)

$$\begin{aligned}&\, \, \, w_{iv} \ge 0 \quad&\forall i \in N, v \in V \end{aligned}$$

(39)

where $f(s_i)$ is a penalty function for reaching an inventory level $s_i$ at station i. In addition, the authors also impose a constraint on the maximum duration of operations assuming a fixed loading and unloading time per bike. Note that the formulation assumes that bikes can be picked up at stations with excess and dropped off at places where there is a deficit, but stations cannot be used as buffers. This assumption is also referred to as the monotonicity condition for fill levels99. The time-indexed and sequence-indexed formulations in95 further relaxed some of these model assumptions by dividing the time available into smaller intervals and allowed vehicles to revisit stations. Models in literature also allow exchanging bikes between vehicles.

The optimization program by Raviv et al.95 has been a starting point for many MILP formulations in static repositioning research. For instance, instead of penalty functions, Erdoğan et al.93 use pre-determined inventory levels and Schuijbroek et al.17 use the bounds obtained from equations (18) and (19) as extra constraints. Others have included service times and unloading and loading costs as part of the objective.93^,94 Most MILP models, however, tend to be computationally intractable for large problem instances. To address these issues, solution methods such as branch-and-cut;93^,100 heuristics such as cluster-first-route-second which solves the multiple vehicle problem using single vehicle problems;17^,101 and metaheuristics such as tabu search102 have been proposed. A summary of the papers that address static rebalancing is presented in Table 4. Almost all of them use integer programming methods and hence integrality constraints have not been explicitly mentioned in the table.

4.2 Dynamic Repositioning

While static repositioning helps reset a BSS to a state with ideal inventory levels, it can perform poorly when the spatio-temporal demand patterns exhibit high variance. It also cannot handle non-recurring forms of demand fluctuations such as those due to weather, special events, etc. In such situations, a BSS operator must reposition bicycles during the day and in real-time to match supply and demand. Hence, this operation is more challenging to carry out than its static counterpart. Unlike in Fig. 6, repositioning and forecasting periods of dynamic repositioning procedures overlap.

Two approaches are popular in literature on dynamic repositioning. The first divides the operating period into a finite number of time steps and assumes perfect knowledge of time-varying demand. This allows us to extend the static repositioning formulations to determine the number of cycles to be moved between stations and the vehicle routes at each time step. For example, Ghosh et al.103 formulated a dynamic repositioning model in which the goal was to reduce the lost customer demand. To understand their formulation, assume that N, A, and T are the set of nodes, arcs, and time steps respectively and let $x_{ijv}^t$ be a binary variable which is 1 if a vehicle v starts to move between stations i and j at time step t. Define another binary variable $\chi _{iv}^t$ which captures initial conditions by taking a value 1 if vehicle v is at station i at time $t = 0$ and is 0 for all other times. That is, vehicles are not required to be present at the depot at the start of the rebalancing procedure. Additionally, it is assumed that vehicles can travel between a pair of stations within one-time step. This assumption is reasonable if the duration of each time step is large. If not, the underlying graph can be modified by creating dummy nodes and arcs. Just like the static case, flow conservation constraints (28) and (29) can equivalently be written as

$$\begin{aligned}&\sum _{j \in N} x_{ijv}^t - \sum _{h \in N} x_{hiv}^{t-1} = \chi _{iv}^t \,&\forall \, i \in N, v \in V, t \in T \end{aligned}$$

(40)

$$\begin{aligned}&\sum _{j \in N} \sum _{v \in V} x_{ijv}^t \le 1 \,&\forall \, i \in N, t \in T \end{aligned}$$

(41)

Constraint (40) equates the number of vehicles coming into station i to the number going out of i. Inequality (41) restricts the number of vehicles that can be present at a station to avoid overcrowding.

Extending other notation in a similar manner, let $r_i^t$ be the inventory level of bikes at station i at time t and let $z_{iv}^{+t}$ and $z_{iv}^{-t}$ be the number of bicycles added and removed by a vehicle v at station i at time t respectively. Denote using $u_{ij}^{tt'}$, the number of bicycles trips made by customers from station i at time step t to station j at time $t + t'$. (Customers take different times to travel between stations, but vehicles are assumed to take one time step.) Flow conservation of bicycles can thus be expressed as

$$\begin{aligned}&r_i^t + \sum _{t^{\prime} < t} \sum _{h \in N} u_{hi}^{t-t^{\prime},t^{\prime}} - \sum _{t^{\prime} > t} \sum _{j \in N} u_{ij}^{tt^{\prime}} \\&\quad+ \sum _{v} \Big (z_{iv}^{+t} - z_{iv}^{-t} \Big ) \\&\quad = r_i^{t+1} \, \forall \, i \in N, t \in T \end{aligned}$$

(42)

If $y_{v}^{t}$ is the number of bicycles present in vehicle v at time step t, the flow balance of bicycles from and into each vehicle is ensured by imposing constraint (43).

$$\begin{aligned} y_v^{t + 1} = y_{v}^t + \sum _{i \in N} \Big ( z_{iv}^{-t} - z_{iv}^{+t} \Big ) \, \forall \, t \in T, v \in V \end{aligned}$$

(43)

Let the demand at time t for travelling between station i and station j in $t'$ time steps be $d_{ij}^{tt'}$. The actual number of customer trips starting from a station at each time step should not exceed the number of bicycles present in the station at that time. When the demand at a station is greater than its supply, bounds on rentals to destinations are assumed to be proportional to the demand to those stations.

Table 4: Summary of static rebalancing models.

Mathematically, this is modelled using (44).

$$\begin{aligned} u_{ij}^{tt'} \le r_{i}^t \frac{d_{ij}^{tt'}}{\sum \limits _{k \in N} d_{ik}^{tt'}} \, \forall \, i \in N, j \in N, t \in T, t' \in T \end{aligned}$$

(44)

The actual flow of bicycles between the stations must also be less than or equal to the demand. Further, for each station i, the inventory level must not exceed the station capacity $C_i$. These conditions are implied in constraints (45) and (46).

$$\begin{aligned} 0 \le u_{ij}^{tt'} \le d_{ij}^{tt'}&\quad \, \forall \, i \in N, j \in N, t \in T, t' \in T \end{aligned}$$

(45)

$$\begin{aligned} 0 \le r_i^t \le C_i&\quad \, \forall i \in N, t \in T \end{aligned}$$

(46)

As before, let $Q_v$ denote the capacity of vehicle v. A vehicle can be loaded or unloaded at a station only when present at that station. These observations are ensured using (47) and (48).

$$\begin{aligned} z_{iv}^{+t} + z_{iv}^{-t} \le Q_v \sum _{j \in N} x_{ijv}^t&\quad \forall \, i \in N, t \in T, v \in V \end{aligned}$$

(47)

$$\begin{aligned} 0 \le z_{iv}^{+t}, z_{iv}^{-t}, y_v^t \le Q_v&\quad \forall \, i \in N, t \in T, v \in V \end{aligned}$$

(48)

Let $b_{ij}^{tt'}$ be the revenue generated from one bicycle trip that departs from station i at t and reaches station j at time $t+t'$ and $c_{ij}$ be the vehicle cost of traversing (i, j). With these constraints, objective (49) is maximized to improve the overall profit which includes the revenue generated from all bicycle trips and the total routing cost of repositioning vehicles.

$$\begin{aligned} \max \sum _{(i,j) \in A} \sum _{t \in T} \sum _{t' > t} b_{ij}^{tt'} u_{ij}^{tt'} - \sum _{(i,j) \in A} c_{ij} \sum _{v \in V} \sum _{t \in T} x_{ijv}^t \end{aligned}$$

(49)

The MILP model is NP-hard and hence does not scale well with the problem size. To tackle this issue, Ghosh et al.103 proposed a Lagrangian Dual Decomposition (LDD) approach in which the original problem is decomposed into a master problem and two slaves (one for repositioning and the other for routing).

Since the repositioning variables z and the routing variables x in constraint (47) are coupled, it is relaxed by introducing dual variables $\alpha _{iv}^t$. The Lagrangian function ${\mathcal {L}}(\alpha )$ can thus be written as

$$\begin{aligned}&\min \limits _{z} \Bigg \{\sum _{i \in N} \sum _{v \in V} \sum _{t \in T} \alpha _{iv}^t \big (z_{iv}^{+t} + z_{iv}^{-t} \big )\\&\quad - \sum _{(i,j) \in A} \sum _{t \in T} \sum _{t^{\prime} > t} b_{ij}^{tt^{\prime}} u_{ij}^{tt^{\prime}} \Bigg \} \\&\quad +\min \limits _{x} \Bigg \{ \sum _{(i,j) \in A} \sum _{v \in V} \sum _{t \in T} (c_{ij} - Q_v \alpha _{iv}^t) x_{ijv}^t \Bigg \} \end{aligned}$$

(50)

The first component of (50) only involves repositioning and the second component is related to vehicle routing. For a given $\alpha$, these slaves are separately solved and the $\alpha$ vector is updated using a sub-gradient descent method for the master problem $\max _{\alpha \ge 0} {\mathcal {L}}(\alpha )$. To speed up computation, an additional clustering approach was used to create abstract stations and the proposed method was tested on CaBi and Hubway data sets. Comparison with other benchmark solutions showed a reduction in lost demand.

The formulation discussed so far was extended to stochastic demand settings using a robust optimization approach.121 In this framework, the BSS operator and the users/environment were viewed as players in a two-player game. At each iteration, the environment generates a demand scenario which maximizes the lost demand considering the repositioning strategy of the operator. The operator reacts by proposing a new repositioning strategy that minimizes the lost demand considering the worst demand scenario presented by the environment and the process is continued until both objectives converge.

The second popular approach for dynamic repositioning is to use rolling horizon models in which the overall problem is broken down into multiple dynamic rebalancing problems. The observed demand in each time interval is used to update forecasts for the next interval and rebalancing decisions are recomputed.15^,122 For example, in the set up shown in Fig. 8, using forecasts of demand between 10:00 and 13:00, a repositioning strategy is first constructed for the roll period which, for time period 1, begins at 10:00 and ends at 12:00. At 12:00, a new repositioning strategy is obtained from updated demand forecasts for the interval 12:00 to 15:00 and the process continues till the end of the time horizon. This method has a greater practical applicability since it can react to current conditions by adjusting the initial conditions for each roll period.

Figure 8:

(Source: Zhang et al.15).

Rolling horizon method for dynamic bicycle repositioning.

A few other models which addresses the dynamic rebalancing problem are summarized in Table 5.

4.3 Offline and Online Repositioning

Some authors have also classified repositioning activities as offline and online methods. Offline algorithms assume perfect knowledge of input data and do not react to changing system states. Hence, they can be both static and dynamic. When applied in a dynamic setting (see 123,124,^–125^,103 for example), one can view offline methods as open-loop control measures. They are suitable in situations with stable demand patterns. However, if the demand exhibits high variance or if there is supply-side uncertainty due to traffic, weather, broken bikes, etc., the recommended solutions may be infeasible since re-optimization is not done in such methods. It can, however, be used to compute value-of-information benchmarks by determining how well the system could be operated in retrospect, using data on the events that occurred. In that way, dynamic offline algorithms are still useful compared to static repositioning methods.

Table 5: Summary of dynamic rebalancing models.

Online methods on the other hand can react to the current inventory level and potentially other external factors such as the day of the week, temperature, and precipitation.132 Most online methods in the literature are posed using a rolling horizon14^,122 or a Markov decision process (MDP) and reinforcement learning (RL) framework.133^,134 MDPs prescribe the sequence of actions to be taken at different system states by considering the rewards/costs incurred for various state-action pairs and the stochastic nature of transitions between states after an action is taken. In the context of bike repositioning, states typically comprise of inventory levels and locations of repositioning vehicles and their contents. State transitions may occur when customers pick up or drop off bicycles or when vehicles remove or add cycles to stations.

Transition probabilities depend on the arrival processes of customers and the time it takes for vehicles and cycles to move between stations. Owing to large state and action spaces, the optimal policies to these problems are solved using RL, particularly off-policy RL methods. In these methods, the optimal policy is learnt using a simulator which generates demand data after training it on a real-world dataset. This procedure is done offline (not to be confused with the earlier description of offline repositioning methods) and a near-optimal policy is generated in the form of a look-up table that prescribes the action to take in each state. Using this policy, one could implement the suggested actions, in the field, in an online manner.

An MDP model proposed by Legros135 attempted to minimize the long-run rate of unmet demand. Suppose that $T_{it}^1$ and $T_{it}^2$ represent the expected arrival rate of customers who are not able to rent and return a bike at station i up to time t respectively. Also let $c_i^1$ and $c_i^2$ be the unit costs incurred by the operator due to the non-availability of bikes and docks at station i respectively. Then, the objective was written as

$$\begin{aligned} \min \left\{ \lim \limits _{t \rightarrow \infty } \sum \limits _{i \in N} \big (c_i^1 T_{it}^1 + c_i^2 T_{it}^2\big ) \right\} \end{aligned}$$

(51)

The time-varying nature of arrival processes was modelled by dividing the time horizon into intervals within which the parameters of the random processes could be assumed constant. Next, a rebalancing problem for a single station was cast as an average cost MDP and was extended to the multi-station case using approximate relative value functions and policy improvement steps.

A spatio-temporal RL approach was used in133 for online repositioning of bikes in a BSS with an objective to minimize lost demand. To reduce the problem complexity, a clustering algorithm was used to group stations and multiple trikes (repositioning tricycles which typically carry 3–4 bikes) were used within each cluster. A deep neural network was used to learn the optimal value functions and the model was tested on real-world Citi Bike data. Another MDP model was proposed in134 to solve the dynamic repositioning problem with a similar objective. A coordinated lookahead policy heuristic was used to address the curse of dimensionality. The resulting policy was tested on data sets from BSSs in Minneapolis and San Francisco, US and was shown to perform better than benchmark policies in reducing lost demand.

Online problems have also been formulated as multi-stage stochastic programs.136 This model extends103 by considering demand scenarios drawn from known distributions that are constructed from data. They proposed a sample average approximation which was solved using a LDD method and a greedy online anticipatory heuristic on CaBi and Hubway problem instances.

4.4 Incentivizing Users

Apart from using vehicles and bike-trailers to rebalance a BSS, operators can provide incentives to customers and influence them to pick up or drop off bikes at desired stations to avoid stations from becoming empty or full. Incentive design may be ideal if it is cheaper than deploying repositioning vehicles but is relatively difficult since user behaviour can be unpredictable. Researchers have presented different models to address this problem.

A deep RL framework was proposed in137 to rebalance dockless BSSs. The problem was modelled as an MDP in which the actions at each time step are the prices for renting bikes in different regions of the network. A policy gradient approach was used to develop a novel hierarchical reinforcement pricing (HRP) algorithm, the objective of which was to maximize the total number of satisfied customers with a limited rebalancing budget. Experiments for HRP were conducted based on datasets from Mobike.

A two-choice model and a mean-field approximation was proposed in138 for incentivizing users to rebalance a homogeneous BSS in which unmet pickup demands are assumed lost. Users are requested to provide two nearest destination stations and they are incentivized to return their bicycles to the station with lower inventory. It was found that this incentivizing scheme improved the redistribution rate significantly, even when a small fraction of users complied.

Another approach was developed by Pfrommer et al.14 to rebalance a BSS using vehicle-based redistribution and user-based price incentives. Their model predictive control algorithm computed dynamic rewards depending on the current and predicted future system states to optimize the operating costs while ensuring a desired service quality. A Monte Carlo model was formulated using historical data from the London Cycle Hiring and results showed that on weekends, the incentive scheme alone could improve the service level. On weekdays, however, price incentives were found to be insufficient for achieving the desired service level, especially during rush-hours.

A bilevel optimization formulation was presented in139 where link-level incentives/prices are decided at the upper level to minimize the number of imbalanced stations. The lower level assigns users to routes and destinations assuming that they take the minimum cost paths. The proposed method attempted to create hubs in the system through which most of the demand is routed and ensured that only a small number of vehicles are deployed for further repositioning. A heuristic approach named iterative price adjustment scheme was used to solve the problem.

A different kind of incentive mechanism design problem was proposed in140 where repositioning activity was crowd sourced. Their model first determines all repositioning tasks and interested customers could bid for carrying out these tasks using bike trailers. Instead of bids,13 proposed a dynamic incentive scheme in which the system offers its users incentives to change their pickup or dropoff location using a finite set of possible prices (subject to an overall budget constraint) and observes binary acceptance/rejection decisions. An online learning mechanism varies these prices across time and customers and using their acceptance/rejection decisions, a cost curve F(p) representing the probability of accepting an alternate station when offered a price incentive p is discovered. The proposed mechanism was deployed for one month on a real-world BSS, MVGmeinRad, in Europe. Rental requests were made on a smart phone app with information on intended pickup and dropoff stations. About 60 percent of the offered incentives were accepted by users during the pilot implementation.

5 Technological Aspects

BSSs are going through a transformative phase in which technological advancements to improve existing systems are constantly being tested and deployed. For instance, a study by Woodcock et al.141 uses secondary data sources to estimate the disabled-life adjusted years (DALY) of BSS users in London by considering levels of air pollution and traffic injuries. With modern day technology, it is possible to track bicycle activity of registered members and the health impacts can be more accurately captured and relayed to users via their apps in real-time. In this section, we examine potential future improvements to BSSs and discuss related research issues.

5.1 Electric Bikes

Electric bicycles that use rechargeable batteries and a motor to assist pedalling have the potential to replace traditional bikes of a BSS. These offer greater ease of cycling especially in cities with uneven terrains and can support long-distance trips. In January 2018, Limebike (currently known as Lime) unveiled a pedal-assisted electric bicycle142 which was made operational in cities like Seattle, Miami, and San Francisco in the US. Currently, E-bikes of Lime and JumpBike are operational in many cities across the globe.

Use of E-bikes in a BSS brings with it a new set of problems. First, the demand for E-bikes may be very different from that of traditional BSSs since factors such as age, gender, trip purposes, and destinations influence the adoption of these systems. When compared with regular bikes, E-bikes may also attract a significant portion of travellers using other motorized forms of transport. Demand forecasts for E-bikes can be obtained using stated preference surveys143 and other methods as explained in Sect. 3. For instance,144 use a multinomial logit model on data collected from a survey in Beijing to analyse the impact of socio-demographic factors, environmental conditions, and transit supply on E-bike usage.

Second, E-bike batteries need to be recharged which, depending on the vehicle design, can be done at the stations or using solar energy.145 Hence, there are other dimensions to station location such as connection with the grid and the amount of daylight received. Stochastic demand results in fluctuations in charging patterns and this needs to be considered when designing a low voltage grid network of bike stations with recharging capabilities.146 E-bikes can also be recharged by swapping batteries.147 The movement of charged batteries and the swapping activities can also be modelled as a logistical optimization problem. For instance,148 generated different demand scenarios using Poisson distributions and determined the number of E-bikes and batteries to be placed at different stations using Monte Carlo simulations. A pilot experiment was also run at the University of Tennessee, Knoxville campus, where E-bikes powered by Li-ion batteries were deployed.

5.2 Locking Mechanisms

Cycles in a BSS are prone to theft which necessitates the use of foolproof locking mechanisms. Most BSS operators provide keyless locks on their bicycles. For example, Ofo used a number lock system in the early stages and later adopted a bar/QR code. Mobike also uses a smart lock mechanism which can be unlocked using a mobile app.149 Even though GPRS-based smart locks are in use, network connectivity issues are not uncommon. To address this problem, a narrow band Internet of Things (NBIoT)-based smart bike locks are being developed.150 Other options include bluetooth low energy (BLE) powered smart locks151 and electromechanical locking system for E-bikes (which can also verify if the bicycle was returned to a dock).145

5.3 Impact of Pricing Schemes

One of the major challenges of BSS operators is to draw more customers to use their services. User satisfaction is not only dependent on the spatial location of stations and the availability of bikes or empty docks, but also on the pricing scheme. Low rental fares can increase ridership but also reduces revenue. Revenue also decreases when the cost of rentals is high since the demand for bike-sharing will drop in such situations. In this context, some studies have focused on understanding the optimal pricing policy and the sensitivity of users to BSS pricing.

In June 2016, CaBi introduced a single-trip fare (STF) scheme to allow customers to take a trip up to 30 min for $2. The timing of this scheme coincided with a SafeTrack metro rail maintenance program because of which an increase in bike rentals was anticipated and the number of docks was increased by about 23%. Before STF, CaBi also had a 24-h pass and a 3-day pass, priced at $8 and $17 respectively, for unlimited trips less than 30 min. It also had monthly and annual subscription passes that cost $28 and $85. The presence of different options allowed152 to study the impact of the price differences on the ridership across price classes. They found that rentals by casual users rose to about 79% per dock but there was not much change in the ridership of those with monthly and annual passes. It was also found that there was a decrease in the revenue generated from users having a 24-h pass and a 3-day pass, indicating that some of them started to shift to the STF scheme.

The price sensitivities were further analysed in153 where STF was decreased from $2 to $1.50 and annual membership changed from $85 to $73. This new pricing scheme improved both revenue and ridership. Further analysis was made using an ordered logit regression model which suggested that low-income groups were relatively more sensitive to price changes and women were about 30% more price sensitive than men in the case of the STF pricing scheme.

Although changes to pricing structure in BSSs are usually infrequent, such opportunities can be put to good use to infer the effect of prices on revenue and ridership.

5.4 Periodic Bike Maintenance

Another crucial problem in the operation of a BSS is to identify broken or faulty bicycles that need repair.154 Bicycles typically face issues with tyre punctures, broken chains, and braking systems.155 In addition, GPS devices, locks, and dock slots at stations could also malfunction. These problems warrant periodic maintenance of bicycles and the BSS infrastructure. Operators often allow users to report issues with their rented bicycles using mobile apps. This information can be used to deploy maintenance vehicles and crew to repair faulty cycles at bike stations or to take broken bikes to dedicated repair stations. Decisions support tools for locating repair stations and routing of maintenance crew can be built using optimization models and these operations can be combined with repositioning.156 BSS operators must, from time to time, perform a cost benefit analysis to decide if bicycles must be discarded or repaired and reintroduced into the fleet.155 Some of the latest bicycles are equipped with tyreless tubes, disk brakes, and chainless drive shaft all of which can drastically reduce the frequency and extent of maintenance required for the upkeep of a BSS.

6 Conclusions

The growth of bike sharing systems has spurred considerable research, especially in the last decade, on problems related to its planning and operations. BSSs have the potential to transform into a competitive transportation mode in many cities around the world. It has a positive effect on the environment and the health of individuals and can also serve as a cost-effective intermediate public transportation mode to address last- and first-mile issues that plague most transit systems. In this paper, we reviewed the history of BSSs and literature on various mathematical models that can help planners and operators design, improve, and optimize new or existing BSSs. We also briefly examined the effects of pricing schemes, technological aspects such as E-bikes, and the maintenance challenges posed by the broken bicycles.

Specifically, we examined literature on strategic and operational planning models. Strategic planning involves forecasting the demand for BSSs, designing stations and bike paths, and determining dock capacity. Potential directions for future research on route design must consider the effects of elastic demand induced by supply-side changes, automobile congestion on route choices of travellers, multi-modal trip making behaviour and transit connectivity, and socio-economic characteristics of demand between different zones.

When designing station locations and capacities, most studies assume knowledge of demand which lacks spatio-temporal complexity. Diurnal patterns of travel are known to cause a reversal of origins and destinations between the morning and evening peak periods. While these effects have been widely studied in the context of rebalancing, they do play a major role in station location and capacity allocation as well. Stylized versions of spatio-temporal variation in demand, time to travel between stations, and relocation strategies must be used to make these decisions at a strategic level.

Our synthesis of literature on operational aspects of BSSs predominantly included static and dynamic repositioning. Static repositioning models assume that bikes are redistributed at night when bike usage is negligible. Dynamic repositioning operations on the other hand are carried out during the day when the system is in use. Models for rebalancing consider single or multiple vehicles/bike-trailers which can make single or multiple visits to stations and can also feature user incentives. Many of these formulations were tested on real-world data sets and were found to improve the operational efficiency when compared to a do-nothing policy. However, supply-demand interactions are modelled only to a limited extent in existing literature. Although, econometric and machine learning models have been found to uncover influential factors and have good predictive power for short- and long-term demand, embedding them within optimization frameworks for managing supply is an uphill task. A right balance between predictive demand models and supply optimization is much needed for data-driven tools that can practically be used for BSSs.