1 Introduction

Sustainable transportation has become one of the major challenges that decision-makers are aiming to address in multiple levels such as the policy level, where cycling is promoted as one of the sustainable modes (European Commission 2011), and at the business and passenger levels, where new mobility schemes are being constantly encompassed in cities around the world.

Examples of these schemes involve the ever increasing use of electric vehicles, ride-sharing systems (for example either car or bicycle), micro-transportation systems (electric and non-electric scooters) and more recently, dockless schemes, in which passengers can find a vehicle near them, rent it and leave it anywhere near their destination, without being limited by a docking station (Lazarus et al. 2019).

The emergence of such schemes, and especially the ones that use means like bicycles or scooters (active mobility), is not surprising since it relates to multiple benefits both on an individual and social level, as: (1) it can be a form of exercise, thus beneficial for health (Oja et al. 2011; Mulley et al. 2013) and well-being (Friman et al. 2017; Singleton 2018; Vaitsis et al. 2019), (2) reduce kilometers driven by car (Woods and Masthoff 2017), thus benefiting the environment; and (3) lead to new business models, thus benefiting the economy (Blondiau et al. 2016).

The recognition that these new mobility schemes can alter the image of cities and urban transportation has also led to a promotion of vehicle-sharing systems, which are being exponentially implemented in cities around the world (Shaheen et al. 2010). These systems fall in the wider context of shared mobility schemes that enable users to have short-term access to transportation modes on an on-demand basis.

In their basic model, a user is registered to the system for a price and is free to take any vehicle from a corresponding station, move around and return it to the origin station or in any other of the system of stations that cover a wide area of the city (Fernández et al. 2018). Lately, dockless schemes have also made their appearance in various cities around the world. Under that scheme, the users are able to leave their bicycles at any suitable location for them after the completion of their trip. Such systems are not limited to bicycles but include other modes of micro-transportation as well, such as electrical and non- scooters, electric-assisted bicycles etc.

Regardless of the model, any vehicle-sharing system is limited by its resources and the basic management issue is focused on how to maximize the vehicles’ availability to the users i.e. how to ensure that every potential user will find at least one vehicle at a close distance to use. The need to address this limitation applies both on dockless systems and those that require the return of the vehicle in a station. However, in the latter case there is also the need for at least an empty slot in every docking station so that the users can return their vehicles.

As a result, the research followed two directions in general (Fernández et al. 2018): (1) trying to identify methods to predict future demand on every docking station (or zone in the case of dockless systems); and (2) to optimize the routes that a truck that carries the company’s bicycles should follow in order to ensure that all stations have the necessary bicycles. The re-distribution/re-balancing problem (both terms will be used in the remainder of the paper as synonyms) is very important, since micro-transportation and vehicle-sharing systems are increasing their market share in urban transportation, and ensuring that the re-balancing is performed with the minimum possible cost and thus, further make the difference between a profitable and an unsuccessful business.

In the first avenue of research, one can find the work of Froehlich et al. (2009), who attempt to predict the bicycles that will be necessary in each station, by taking into account historical data like the historical average, trends etc., along with the works of Kaltenbrunner et al. (2010) and Vogel and Mattfield (2011) who use time series analysis to predict the necessary stock of bicycles in hourly intervals.

In the second research area of vehicle-sharing schemes management, one can find the works of Paul and Zhang (2017) and Reiss and Bogenberger (2016) that use optimization techniques for optimizing the routes that trucks should adopt in order to transfer the bicycles from one station to another.

Nonetheless, these efforts seem to be restricted by numerous limitations. Firstly, they use techniques that rely on historical data, which means that they view a state of the city under normal circumstances; the methods are not robust enough to ensure that the system will not work sub-optimally when the state of the city is considered abnormal. Secondly, the works do not address the problem holistically; as each research effort clearly falls in one of the two areas of research, either predict the future demand, or optimize the routes of the trucks that move the vehicles.

As a result, the purpose of this paper is to propose an approach for the re-balancing problem of a bike-sharing scheme. The contributions of the paper are summarized as follows:

  • We develop and employ a holistic approach for the management of a vehicle sharing system, as the developed model dynamically receives forecasted demand data;

  • We develop and employ a generalized modelling methodology that can be applied to all vehicle-sharing schemes regardless if they have docking stations/zones or are dock less.

Section 2, provides a review of the existing literature while Sect. 3, the description of the system under study. Section 4 provides a detailed analysis of the model employed, while Sect. 5, the application of the model to the real case of Thessaloniki’s bike-sharing system. Section 6 provides the numerical results, while finally Sect. 7, the paper’s conclusions and future research directions.

2 Literature review

The literature review was classified based on the two distinct sub-problems examined. With respect to demand estimation, the identification of its dynamic characteristics has been gaining significant attention in the literature the last years (Si et al. 2019). Researchers are concerned not only with the factors that may affect future demand, but also with the identification of the best method to perform future demand predictions.

In 2012, the Department of Transportation of United States of America published a report that listed the most influential factors for determining the demand for bicycles at docking stations. These factors were: population density, employment density, proximity to universities, commercial activity, available infrastructure, proximity to tourism infrastructure, available public transportation means, and topography (United States Department of Transportation 2012).

Zhao et al. (2015) extended the research to identify the most important of these factors and found that demand for trips is higher for residential areas, and when stations are closer to railway stations. Noland et al. (2016) further refined the research by using Bayesian regression models and identified that proximity to subway stations in particular and the density of the bike-sharing infrastructure in general, can generate bike-sharing trips. The importance of the density of bike-sharing stations was also identified by Hyland et al. (2018), while Faghih-Imani et al. (2017) illustrate that the topography of the city and especially its elevation levels greatly affect the future demand.

The factors identified above can be considered macroscopic, thus, research efforts focused also on how demand can change within smaller time intervals (day, or even hourly intervals). Corcoran et al. (2014) showed that weather conditions greatly affect demand variability from day to day, while Kim (2018) highlighted that demand does not differ between workdays and weekends, however it is reduced on public holidays and days with high temperatures.

Regardless of the factors, several methods were deployed to predict future demand. The latest trend is to use Machine Learning techniques to predict dynamic demand at a station level. Examples includes the works of Hulot et al. (2018), Wang and Kim (2018), Lozano et al. (2018) and Lin et al. (2018), who use random forests, gradient boosting and recurrence and graph convolutional neural networks.

These efforts however, focus on large scale bike-sharing systems and do not consider small or medium size ones. Furthermore, each approach deploys one method to predict future demand, thus affected by its inherent methodological limitations.

For the second sub-problem, associated to the optimization of the routes traversed by a truck (that transfers bicycles from one docking station to another), the research (to the best of our knowledge) is limited. This can be attributed to the fact that research has focused more on other systems, such as car-sharing schemes, and assume that the solution can be also easily adopted for bike-sharing schemes. Examples include the work by Fernández et al. (2018) who focus on how to utilize the users themselves in order to achieve an effective re-balancing of the network, and Paul and Zhang (2017) as also Reiss and Bogenberger (2016) who use mathematical programming to solve a static, complete re-balancing problem of a bike sharing system. Similarly, Chemla et al. (2013) solve the static rebalancing problem with tabu search, while Erdoğan et al. (2014) use a time extended network formulation. Finally, Alvarez-Valdez et al. (2016) propose a heuristic method without however, providing a mathematical formulation of their solution.

While the majority of research efforts provide novel quantitative methodologies for addressing the rebalancing problem examined, research gaps emerge that seem to be inadequately addressed by the existing literature as these are depicted below:

  • There seems to be a lack of research efforts that provide a holistic evaluation of machine learning algorithms for predicting demand, as these focus mainly on employing one method. Thus, the derived demand forecasts may not lead to minimized forecasting errors.

  • The problems of demand prediction and resource-allocation in vehicle-sharing schemes are mainly addressed independently.

  • There is a small number of research efforts that employ their developed methodologies in real-world cases.

The current research effort addresses the above research gaps through

  • The evaluation of a number of critical machine learning algorithms for providing forecasts, and the selection of the methodology that minimizes forecasting errors.

  • The employment of the top-down approach that combines the sub-problems of demand prediction and resource allocation in the same process.

  • The evaluation of the methodology’s applicability in the real-case of the bicycle-sharing system of the city of Thessaloniki, Greece.

3 System description

The system under study consists of a number of docking stations where customers can rent bicycles and return rented bicycles at random times. Each docking station has a capacity of bicycles that can accommodate, and the maximum number of rentals that can occur (i.e. limited by the maximum number of bicycles that are docked at that specific time).

To avoid situations where a customer wishes to rent a bicycle from a station but there is none, the management company has a dedicated truck that every three (3) hours, moves bicycles from the stations that have a surplus to those stations that are in need. Which stations have a surplus and which do not, is determined by the previous rents of each station, and the knowledge of the truck driver.

The route that the truck follows is a circular route: the truck starts at the first station and visits the others consecutively. At stations with low rental demand in the previous hours, the driver picks bicycles leaving the station with a capacity slightly lower than its maximum capacity. As the truck moves across the route, the driver leaves bicycles to those stations that are expected to present high rental demand. This demand is dynamically determined through a set of appropriate machine learning algorithms.

The model decides on whether: (1) the rebalancing truck will be employed or not; (2) the sequence of the stations that the truck will follow; and (3) whether a bicycle is picked or dropped off on a specific station, under transportation cost minimization criterions.

4 Model development

We examine a distribution network that consists of a number of docking stations \(i \in I\) which supply bicycles to stations \(j \in J\) where bicycle demand occurs. The station’s network is modelled as a graph with a set of nodes and edges \(G = \left( {N, E} \right)\), where N is the number of nodes/stations and E involves the edges that connect these stations (I, J \(\in N\)). Since the route of the truck is cyclical, the distance from a station i to a station j is estimated through the use of OpenStreetMap.

The flow of the developed methodology follows a series of steps and it is depicted in Fig. 1

Fig. 1
figure 1

Flowchart of the proposed method

Full size image

4.1 Step 1: Docking station demand Estimation

In the first step, the demand of individual docking stations is estimated through an appropriate machine learning algorithm, in order to further determine the stations that exhibit bicycle surpluses and thus, supply those that exhibit bicycle deficits.

To address the limitations of choosing an individual predicting method, the designed system deploys several machine learning algorithms for the same set of data and only the results from the best fitting algorithm are considered. Thus, it is ensured that not only the “normal” (historical) state of the city is considered, but at least one of the algorithms will consider ab-normal states.

To evaluate the performance of each model, the tenfold cross validation method is used, with the evaluation indicators being: (1) the Mean Squared Error (MSE); (2) the Rooted MSE of the log-transformed predicted and target values (Root Mean Squared Logarithmic Error- RMSLE), and (3) the Mean Absolute Error (MAE) and the coefficient of determination (R2) as an indicator of the percentage of variability in the dependent variable that each model could explain.

The forecasting results are then used as inputs in a linear programming model that will optimize the sequence of bicycle pickups and drop-offs, under maximum truck capacity constraints and ensuring that no station is left without bicycles at the end of each route.

The mathematical programing model that is used to determine this sequence, follows a series of steps that are described below.

4.2 Step 2: Sequence optimization of bicycle pick-ups and drop-offs

In the second step, the purpose is to determine the stations that have an excess of bicycles and which will further supply the stations that are in need of bicycles. To do so, the predicted demand from the machine learning algorithm, and the n × n (where n is the number of stations/nodes of the network) distance matrix of the docking stations is used as an input in the following assignment (optimization) algorithm.

The mathematical formulation of the assignment problem is:

$$Minimize \mathop \sum \limits_{i = 1}^{N} \mathop \sum \limits_{j = 1 }^{N} c_{ij} \cdot x_{ij}$$
(1)
$$subject\,to:$$
$$\mathop \sum \limits_{i = 1}^{N} x_{i} \le Station_{Supply\,i} , \quad \forall i \in N$$
(2)
$$\mathop \sum \limits_{j = 1}^{N} x_{j} \ge Station_{Demand\,j} ,\quad \forall j \in N$$
(3)
$$x_{ij\, \ge\, 0}$$
(4)

The nomenclature of the model variables and parameters is illustrated in Table 1:

Table 1 Nomenclature of model variables and parameters
Full size table

The assignment problem will optimize the number of bicycles that will be transported from the stations that have an excess to those that are in need. However, the derived result provides no indication of the route that the transportation truck should follow. This type of (re-balancing) problem is difficult to formulate mathematically because the number of visits to each station is not known a priori. As a result, it requires a different approach to its formulation, which will be further addressed through Step 3 which is based on the work of Pal and Zhang (2017).

4.3 Step 3: Optimization of truck rebalancing

The assignment problem that was solved in the second step, results in a subset of the original network, containing only those stations/nodes that can supply or demand bicycles, since not all stations participate in the exchange. The new network is denoted by G′ = (N′, E′), where N′ the new number of stations/nodes that can supply bicycles and E′ the number of edges/distances that connects the new nodes.

This new network consists of stations/nodes that have the following attribute: they either have a positive imbalance (they can supply bicycles), a negative imbalance (they demand bicycles) and finally, we consider a depot node with imbalance equal to zero. An example of such a network G′ is provided in Fig. 2. In the particular network, station k with a positive imbalance of + 5 will provide 5 bicycles to stations m and p, with imbalance − 2 and − 3 respectively.

Fig. 2
figure 2

Network of docking stations after the assignment optimization

Full size image

Further assumptions of this mathematical formulation of the problem are that there are no stations/nodes that bicycles can be stored and the objective is to minimize the total distance traversed by the re-balancing truck. Finally, the assignment optimization of the previous step ensures that the total imbalance of the network is equal to zero.

The nodes of the new network G′ (except of the depot) are subsequently decomposed into nodes with a unit imbalance. Following on the previous example, in Fig. 3 each supply station (positive imbalance) is decomposed in a number of nodes equal to the imbalance of Fig. 3.

Fig. 3
figure 3

Decomposed network of docking stations

Full size image

For example, in the decomposed network, station k from the network G′ is decomposed into the five nodes (stations K_1, K_2, K_3, K_4, K_5) with the same geographical coordinates as station k of the network G. The same is valid for the stations/nodes with a negative imbalance.

The reason for this decomposition is that in such a type of network, the mathematical formulation becomes more feasible to formulate, since the number of visits to each station/node must equal one. Hence, with one re-balancing truck, the problem becomes the 1-Commodity Pickup and Delivery Capacitated Traveling Salesman Problem (Hernández-Pérez and Salazar-González 2004). The mathematical formulation of the problem was adapted by the work of Mattern (2017) and is summarized below.

The model’s decision variables are summarized in the following Table 2.

Table 2 Decision variables
Full size table
$$Minimize \mathop \sum \limits_{{i \in N^{\prime } }} \mathop \sum \limits_{{j \in N^{\prime } }} c_{ij} \cdot x_{ij}$$
(5)
$$Subject\,to:$$
$$\mathop \sum \limits_{{j \in N^{\prime } }} x_{ij} = 1,\quad \forall i \in N^{\prime }$$
(6)
$$\mathop \sum \limits_{{i \in N^{\prime } }} x_{ij} = 1,\quad \forall j \in N^{\prime }$$
(7)
$$y_{ki} \le y_{kj} + \left( {1 - x_{ij} } \right), \quad \forall \left( {i,j} \right) \in \frac{{E^{\prime } }}{k} \in N^{\prime } \left\{ i \right\}$$
(8)
$$y_{kj} \le y_{ki} + \left( {1 - x_{ij} } \right), \quad \forall \left( {i,j} \right) \in \frac{{E^{\prime } }}{k} \in N^{\prime } \left\{ i \right\}$$
(9)
$$x_{ij} \le y_{ij} , \quad \forall \left( {i,j} \right) \in E^{\prime }$$
(10)
$$y_{n + i,i} = 0,\quad \forall i \in N^{\prime }$$
(11)
$$y_{i,n + i} = 1,\quad \forall i \in N^{\prime }$$
(12)
$$\mathop \sum \limits_{i = 1}^{{2N^{\prime } }} \left\{ {y_{ij} *R_{i} } \right\} \le Q - R_{j} , \;where \,Q\, the\, truck^{\prime}\,capacity$$
(13)
$$\mathop \sum \limits_{i} x_{ii} = 0,\quad \forall i \in N^{\prime }$$
(14)
$$\mathop \sum \limits_{i} y_{ii} = 0, \quad \forall i \in N^{\prime }$$
(15)
$$y_{2n + 1, i} = 1,\quad \forall j \in N^{\prime }$$
(16)
$$y_{ i,2n + 1} = 1,\quad \forall j \in N^{\prime }$$
(17)
$$x_{ij} \in \left\{ {0,1} \right\}$$
(18)

Constraints (6), (7) ensure that all stations are visited exactly once. Constraints (8), (9) ensure that station i is always before station j. Constraint (10) shows that if an edge is not travelled then \(b_{ij} = 0\). Constraints (11), (12) ensure that a bicycle drop off never occurs before the pickup, and a pickup is always before a drop off respectively. Constraint (13) is focused on the truck’s capacity, while constraints (14), (15) prohibits the creation of self-loops. Constraint (16) ensures that the first pickup will not be made from a drop off station and similarly, constraint (17) ensures that the last move (returning to depot) will not be from a pickup station. Finally, constraint (18) shows that this is an Integer Linear Program.

5 The case study of Thessaloniki’s bike-sharing system

The proposed approach was tested in the city of Thessaloniki for a bike-sharing schema that contains eight (8) docking stations and a re-balancing truck with a capacity of eight (8) bicycles. The time interval for the machine learning algorithms was decided to be three (3) hours because for the case study, the rental frequency is considered low.

Three datasets are used for the prediction of the future demand in the machine learning algorithms. The first two datasets are about the bike-sharing scheme. The data include information about the rental and return timestamps and the station of each rental, the user ID along with the bicycle ID. An initial analysis of the dataset illustrated that almost 3% of the rentals has a duration of up to 5 min. Such trips were considered invalid and were excluded from the analysis. Historic data from the years 2015–2018 (October) were used to train the machine learning algorithms.

The third set includes weather data, taken from Thessaloniki’s local airport weather station. It contains information about the average wind speed and temperature for the previous 30 min, sky clearance report for the last 3 h and precipitation levels for the last 6–24 h. These values were normalized hourly, to enable correct resampling in the 3-h intervals.

All the algorithms were implemented in the Python programming language and utilizes the established libraries Pandas (McKinney 2010) and Scikit-learn (Pedregosa et al. 2011) for data processing, transformations, analysis and machine learning. The neural networks are realized with Keras (Chollet 2015) running on top of Tensorflow (Abadi et al. 2015). The optimization processes were modelled in Pulp (Mitchell et al. 2011).

The proposed tool was tested with data from the bike-sharing system of the city of Thessaloniki, Greece. The bike-sharing system is called Thessbike and has 16,000 members. In the current situation, the system operates with almost 200 bicycles in 8 docking stations. The analysis of the pre-processed data (Fig. 4a) illustrated that demand is distributed in a similar way for all the operational months of the system. The peaks in rents appear in May and September, when the weather conditions are ideal for cycling. In Fig. 4b, it can be noticed that the hourly demand differs during the day, with a sharp increase observed usually in the afternoon hours.

Fig. 4
figure 4

a Distribution of rentals per month for each year of operation, b distribution of rentals per hour based on the season

Full size image

A further analysis of the data illustrated what is the most important station and provided insights into the Origin and Destination of the rentals (Fig. 5). The Sankey diagram shows that the most important station (in term of rentals and returns) is the one located at the Opera House of Thessaloniki. The diagram provides also the possibility to the operator to check which and how many of those trips are cyclical (origin and destination is the same).

Fig. 5
figure 5

Sankey diagram of the origin and destination of rentals

Full size image

6 Numerical results

The initial results derive through the cross-validation on four machine learning algorithms, namely, Gradient Boosting, XGBoost, Random Forest and Neural Networks. The results indicate that the XGBoost provided a slightly better data fit with an R2 = 76% compared to 74% for Gradient Boosting and Random Forest, and 63% for Neural Networks.

Regarding the re-balancing process, the network of stations that have non-zero imbalance (calculated in the assignment optimization process) is displayed in Table 3 below

Table 3 Example of re-balancing problem
Full size table

By applying the process where the network is decomposed and the 1 Commodity Pickup and Delivery Capacitated Traveling Salesman Problem (truck capacity = 8 bicycles) is employed, the order that the re-balancing truck must follow is displayed on Table 4 and Fig. 6.

Table 4 Re-balancing route
Full size table
Fig. 6
figure 6

Visualization of the re-balancing travel in a graph

Full size image

7 Conclusions

The purpose of this paper was to propose a holistic approach to managing bike-sharing systems. It includes the challenges of predicting what the future demand may be and how to address the re-balancing of the system with a capacitated vehicle by minimizing the overall distance that it will traverse.

As a result, a process was designed and developed that includes two different solutions to the two separate problems: For demand prediction, four (4) machine learning algorithms were developed and the results from the best-fitting one were used as an input to the re-balancing problem. Consequently, that problem is further divided into two sub-processes: One where it is solved as an assignment optimization problem (which of the station can supply and which demands bicycles), the results of which are used in an 1-Commodity Pickup and Dropoff Capacitated Traveling Salesman Problem.

The algorithms are embedded into a Graphical User Interface that can be used by operators of the bike-sharing system, giving them the possibility to customize many of the results and options. The tool is currently being tested in a bike-sharing system in the city of Thessaloniki, Greece.

Future directions of the research include the input of real-time weather data, the refinement of the mechanism that records rentals and returns of bicycles to the docking stations, and the further development of the optimization processes so that they can be used for large-scale systems as well. Moreover, and as the future of vehicle-sharing schemes may be headed towards dock less systems, where the vehicles (i.e. cars, bicycles or scooters) can be picked-up and left-off anywhere within the urban environment, the proposed approach would need to become multi-dimensional. Thus, predictions would have to additionally consider not only the level of demand for vehicles, but also where that demand may occur, as the vehicles can be left-off anywhere.