Since the turn of the millennium, an explosion of Bicycle Sharing Systems (BSSs) has been observed in cities throughout the world (see Figure 1). These initiatives allow individuals to rent a bike from an automated rental station, use it for a short period of time, and return it to any other rental station in the city. For customers, bike sharing covers a niche by providing in the need for short low-cost trips, which are considered too far to walk (1–5 km) (Midgley ). In that sense, bike sharing can be considered more as a supplement to the modal mix of urban public transportation, rather than as a competitor to bike rental.
Figure 1: Global growth of bicycle sharing, measured by number of bikes (ITDP )
Though there are many advantages when deploying a BSS such as improving public health, reducing carbon emissions and reducing congestion, to name a few, there are also many challenges. One of the critical success factors of BSSs is the reliability for customers to find bicycles and empty locks. However, demand and supply at specific rental stations are rarely balanced, and fluctuations in supply and demand in the long or the short term might cause stations to fill up or deplete, preventing users from collecting or returning bikes. Visualizing imbalances for San Francisco’s BSS stations, for example, shows that balanced stations are rare, even when averaging over longer periods (see figure below).
Figure 2: Deviations of average user departures (thin line) and average user arrivals (thick line) from the balanced 50 % – 50 % situation at San Francisco’s bikeshare stations show that balanced stations are rare
This effect is a paradoxal property of a BSS, i.e. that by using BSSs, less bike sharing can occur. To solve the paradox means to tackle the problem of imbalanced stations. To do this, operators of BSSs therefore typically deploy a fleet of light vehicles to transfer bikes between stations, attempting to rebalance the system and, therefore, to avoid that demand of new customers is lost. These vehicles are in constant contact with the dispatching station, where the current inventory of each station is monitored, and from where the repositioning activities are directed.
Solving the paradox: bicycle repositioning
So we know bicycle repositioning is organized to allow users to better fulfill their demand for trips, i.e. demand for both bikes and empty locks at different stations and that vehicles will relocate a single commodity, i.e. the bicycle. How to decide where the vehicles need to drive at any given moment, and what they should do? What are the important aspects of the problem? They are timing, capacity constraints and prioritization.
Timing is of major importance when repositioning is done during the day, because user demand is time dependent (see Figure 3).Many stations receive more bikes from users than they serve at some time of the day while serving more bikes than they receive at other times, especially during peak hours due to commuter activity. Not taking this effect into account would yield unrealistic models for repositioning during the day.
Figure 3: Average hourly station inventory levels during one month show that time of day plays a major role when planning to relocate bicycles at a station.
2) Capacity constraints
Since a vehicle stops to either perform a drop off or pick up of bicycles, the transferred bicycles should be available at the source (station or vehicle). Likewise, the capacity to store them (vehicle or station) should be available on the other end of the transaction. Therefore, sequences of stations and corresponding instructions are infeasible when they violate station or vehicle capacities.
In general, there are more imbalanced stations than vehicles. So prioritization of stations, or, more accurately, of vehicle actions is important when timing is important since choices will need to be made. Choosing to serve a station at a certain time will lead to another station not being served when needed. Some stations of a BSS are more popular than others (See Figure 4). Prioritizing popular stations over less popular stations is therefore a good approach, since their urgency is typically higher.
Figure 4: Relative popularity of stations in the bay area bike sharing system show that some stations are more important than others.
Solving the paradox by decomposition
An elegant way to tackle the repositioning problem is to decompose it into two simpler problems:
- Forecasting repositioning instructions at the stations over time
- Planning the generated instructions for each vehicle
In the first problem, a “wish list” of instructions is computed that leads to a balanced system when executed by the vehicles. Therefore, we will call them requests. The information a vehicle needs to know in order to execute a request is presented below (Table 1). These instructions need to be computed using forecasting models that take into account a myriad of features such as weather, infrastructural state and time.
Table 1: Request attributes
|Id||ID||Unique identifier of a request within the instance|
|Station id||SID||Unique identifier of a station within the instance|
|Quantity||Q||Number of bikes to (un)load (<0 when unloading)|
|Early arrival time||EAT||Earliest allowed time to start serving a request|
|Late arrival time||LAT||Latest allowed time to start serving a request|
|Drop time||DT||Vehicle time consumption of serving a request|
|Priority||P||Relative importance of the request, larger is better|
Given the list of instructions, a solution to the planning problem can now be represented as a list of requests per vehicle, which implies a list of stations. While generating the list of requests, i.e. the wish list, in the first problem, no vehicle information is available. So possibly, it will not be feasible to execute all of the requests. The second problem, the planning of such requests, will therefore need to make a good selection of requests, where priority needs to play a role. A straightforward way to do this is to minimize the sum of priorities of requests that are not served by the vehicles. The optimization model for this problem is called the Bicycle Request Scheduling Problem (BRSP), and more information can be found in Sörensen and Vergeylen  and Vergeylen et al. . An example solution for the model applied to Antwerp’s BSS, Velo, is presented in Figure 5.
Figure 5: A computed request sequence specifying the instructions for a vehicle.
To get a feeling of how complex real-life situations can get, observe a weekday in Paris at 17h in Figure 6.
Figure 6: Full (red) and empty (blue) stations (circled when completely full/empty) in Paris need to be rebalanced, which is not an easy problem. (Source: bikes.oobrien.com)
For many stations, more than one request per day can be assumed. The Paris BSS, having more than 1200 stations, therefore can be expected to generate a few thousand requests on a daily basis. Think about how many solutions this situation allows: permuting every possible subset of requests, and partitioning each permutation to a subset of available vehicles will lead to a solution. It should not come as a surprise, therefore, that optimal solutions for realistic instances are nearly impossible to prove, since the BRSP is NP hard. Bicycle repositioning generally leads to difficult combinatorial problems –the BRSP being one of them– that benefit from heuristics in practice.
ITDP. The bike-share planning guide. Report, Institute for Transportation & Development Policy, 2014.
P. Midgley. Bicycle sharing schemes: enhancing sustainable mobility in urban areas. Background Paper CSD19/2011/BP 8, United Nations Department of Economic and Social Affairs, Commission on Sustainable Development, 2011.
K. Sörensen and N. Vergeylen. Computer Aided Systems Theory – EUROCAST 2015: 15th International Conference, Las Palmas de Gran Canaria, Spain, February 8-13, 2015, Revised Selected Papers, chapter The Bike Request Scheduling Problem, pages 294–301. Springer International Publishing, Cham, 2015.
N. Vergeylen, K. Sörensen, and D. Palhazi Cuervo. An analysis of the bike request scheduling problem search space. Technical report, University of Antwerp, 2016.