| Artxibo OCR | Available online at www.sciencedirect.com
ELSEVIER
ScienceDirect
Procedía - Social and Behavioral Sciences 87 (2013) 203 - 210
Procedía
Social and Behavioral Sciences
SIDT Scientific Seminar 2012
A dynamic simulation based model for optimal fleet repositioning
in bike-sharing systems
Leonardo Caggiani3*, Michele Ottomanelli3
aPolitecnico di Bari, via Orabona 4, Bari, 70125 Italy
Abstract
In this paper a simulation model for dynamic bikes redistribution process is presented. The objective of the model is to
minimize the vehicles repositioning costs for bike-sharing operators, aiming at a high level users satisfaction, and assuming
that it increases with the probability to find an available bike or a free docking point in any station at any time. The proposed
model considers the dynamic variation of the demand (for both bikes and free docking slot) and micro-simulate the BSS in
space and time determining the optimal repositioning flows, distribution patterns and time intervals between relocation
operations by explicitly considering the route choice for trucks among the stations.
© 2013 The Authors. Published by Elsevier Ltd. Open access under CC BY-NC-ND license.
Selection and peer-review under responsibility of SIDT2012 Scientific Committee.
Keywords: bike-sharing; repositioning problem; decision support system; sustainable mobility.
1. Introduction
The development of Bike-Sharing Systems (BSS), in addition to the sustainability of the transport and urban
systems, is mainly due to its door-to-door feature (DeMaio, 2009). BSS allow to access areas of the city that are
forbidden for other transport means, including eco-friendly vehicles. BSS are also often employed to connect
users to public transit networks (for ex. connection between intermodal hubs and final destination). The main
components of a BSS are a bikes fleet, bike stations and a given (known) number of users. In these systems,
customers arrive to bike stations (trip origin), utilize bicycles for an amount of time, and then return the bicycle to
the same or to a different bike station (trip destination). Nevertheless, a greater diffusion and usage of the BSS is
limited by its own drawbacks (Büttner et al., 2011). BSS is used mainly for medium-short distances and for one-
way trips. Such a behaviour leads to an unbalanced distribution of the bikes over the time and space. Thus, from
* Corresponding author. Tel.: +39-080-5963380; fax: +39-080-5963329.
E-mail address', [email protected].
1877-0428 © 2013 The Authors. Published by Elsevier Ltd. Open access under CC BY-NC-ND license.
Selection and peer-review under responsibility of SIDT2012 Scientific Committee,
doi: 10.1016/j.sbspro.2013.10.604
204
Leonardo Caggiani and Michele OttomaneHi /Procedía - Social and Behavioral Sciences 87 (2013) 203 - 210
the real-time management stand point, to increase the system capacity and users satisfaction, it is necessary to
properly relocate the bikes among the stations of the BBS.
As in technical literature, redistribution scheme relevant to systems operating with shared vehicles can be
mainly divided into two standard categories: “user based” and “operator based” (Allouche et al., 1999; Barth &
Todd, 2001; Kek et al., 2006; Vogel & Mattfeld, 2010). In the former the users are stimulated to return to a non-
saturated station in order to balance the distribution of the bikes among the stations. In the latter, the relocation is
assigned to the service staff. While the indirect customer base redistribution is feasible for mid-term operations,
the direct operator based redistribution may be effective in short-term period.
The operator based reallocation problem is defined as Pickup and Delivery Problem (PDP). In literature
several methods to solve the vehicle or resources reallocation problem have been presented (Cheung & Powell,
1996; Kochel et al., 2003; Nair & Miller-Hooks, 2011). These models are generally applied to freight
transportation (Du & Hall, 1997; Crainic, 2000) or to car-sharing systems (Barth & Todd, 2001; Kek et al., 2006
and 2009; Dell’Orco et al., 2011).
Recently just a few papers have been dealing with the Bike Sharing Pickup and Delivery Problem (BS-PDP)
as a variation of classical PDP. The BSS reallocation can be carried out either during the night when the bikes
demand is negligible (static repositioning, as defined in literature), or during the day when the bikes distribution
among the stations rapidly changes due to the high demand level (dynamic repositioning). Most of the literature
presents static BS-PDP (Benchimol et al., 2011; Shu et al., 2010; Chemla et al., 2011; Forma et al., 2010). Even
less authors deal with the dynamic case. In particular Contrado et al. (2012) propose a mathematical formulation
of the dynamic problem on a space-time network. In general the dynamic BS-PDP is investigated without
focusing at redistribution patterns and time periods (Vogel & Mattfeld, 2010). Some works propose a fixed
repositioning time interval (TSTair & Miller-Hooks, 2011; Sayarshad et al., 2012), a variable repositioning time
interval (Caggiani & Ottomanelli, 2012) or assume redistribution vehicles moving at random from saturated
stations to empty ones (Fricker & Cast, 2012).
In this paper a simulation model for dynamic bikes redistribution process is presented. The objective of the
model is to minimize the vehicles repositioning costs for bike-sharing operators, aiming at a high level users
satisfaction, and assuming that it increases with the probability to find an available bike or a free docking point in
any station at any time. The proposed model considers the dynamic variation of the demand (for both bikes and
free docking slot) and micro-simulate the BSS in space and time determining the optimal repositioning flows,
distribution patterns and time intervals between relocation operations by explicitly considering the route choice
for trucks among the stations. As matter of fact the model has been specified as a micro-simulation model and
thanks to this features and variables considered it can be considered as a Decision Support System (DSS) for BSS
design and real-time management. Furthermore the obtained results have been compared to those of the
previously proposed method with variable repositioning time interval based on Fuzzy Decision Support System
(FDSS) (Caggiani & Ottomanelli, 2012).
2. The proposed model
2.1. Bike sharing system simulator
In the proposed model we have represented and modelled all the operations that characterise a BSS. We
assume that the system runs an advanced monitoring systems of the number of bicycles in each station as most of
the current BSS.
The design variables that describe a BSS are the number of stations (TSTs) and their location in the city network,
the number (Nrt) and the capacity (Crt) of the redistribution pick-up or open trailers (proper carrier vehicles used
to carry several bikes at the same time), for each station: the number of docking slots (Nd) and free ones (TSTp) and
Leonardo Caggiani and Michele OttomaneUi /Procedía - Social and Behavioral Sciences 87 (2013) 203 - 210
205
the number of available bikes (Nb). For further detail on the architecture with relevant functions of the BSS
operations simulator see the first flow-chart depicted in Caggiani and Ottomanelli (2012).
With respect to the system dynamics, we assume the operating day is divided in Z discrete time intervals. For
each time interval z and for each station j, given the pickup bikes demand (Db), the model simulate the
destination choice (Dp) in order to assess the arrival time for each users. The choice model is based on relative O-
D attractiveness and the nature of trip (one-way or round trip). Since in this first stage we have developed the
simulation for a low density stations distribution, we assume that each bike request that cannot be satisfied (empty
station) turn user away (demand decreasing); as well as each give back not satisfied demand (full station)
generate undesired waiting time for user.
At the begin of each interval z the number of bikes and the available docking points are updated by taking into
account in-out users flow (turn-over) and the relocated bikes.
The Decision Support System (Fig. 1) is activated at constant gap time. At the end of the day (end of service
time period), a static redistribution is carried out in order to restore the starting bikes distribution among the
stations.
2.2. The proposed Decision Support System
The problem is to relocate the bicycles from overcrowded station to the stations with a shortage of bikes (i.e.
balance the demand-supply system). The first essential data is the prediction of future demand among stations in
order to forecast bikes and free docking point requests. The literature proposes different forecasting methods, in
particular, for BSS, Borgnat et al. (2009) use a linear regression model; Froehlich et al. (2009) have developed a
Bayesian network.
The core of the forecasting demand method in the proposed DSS is based on Artificial Neural Networks
(ANN). A first advantage of this approach is that, using Neural Networks (NN), there is no need to assume
explicit functions for returned or picked up bikes, because a NN learns directly from observed data. Therefore,
starting from the time series of bikes requests, the NN is able to relate the hour of the day to entering or exited
vehicles number. Furthermore, the high capability and the goodness of NN with respect to forecasting methods
proposed for shared use vehicle has been proved by Kek et al. (2005) for the case of car sharing systems.
Differently from the FDSS model (Caggiani & Ottomanelli, 2012) the proposed DSS is activated at constant
Gap Time (GT) and it starts with the forecasting module that estimates entering and exiting bikes (demand). For
each station the estimation is performed on GT by two Artificial Neural Networks (NN) on the bases of given
historical time series collected by the usage monitoring systems.
The first NN is used to estimate the number of entering vehicles; the second one to forecast the exiting
vehicles. Both NNs are feed-forward back-propagation networks with a training function that updates weight and
bias values according to Levenberg-Marquardt optimization. The NNs have three layers with five neurons for the
first and the second layer and one neuron for the third. The input data of NNs are the vectors of entered and exited
bicycles in the station, for each step, during the previous months of the prediction. Actually, such a formulation
depends on the available data.
The outputs of the NNs are the entering (PDp) and exiting (PDb) number of bicycles dynamically forecasted
for each time step and station. Other NNs variables are the day of the week, the time of the day and the weather
conditions.
206
Leonardo Caggiani and Michele Ottomanelli/Procedía - Social and Behavioral Sciences 87 (2013) 203 - 210
Fig. 1. Flowchart of the DSS
In other words at this stage the outputs are the estimated number of lost users PLu (i.e. users whose service
request cannot be satisfied), the number of waiting users NWU (i.e. users that do not find free docking points at
the desired station) as well as the estimated waiting time spent to return the bike (UWT) at each bike station. On
Leonardo Caggiani and Michele OttomaneUi /Procedía - Social and Behavioral Sciences 87 (2013) 203 - 210
207
the basis of the forecasted in-out bikes within the GT interval, by solving the optimization problem given in eq. 1
we obtain the Relocations Matrix (RM), with rm,k entries, and the Relocation Path (RelP) of the redistribution
carrier vehicles that minimizes the total costs for the provider (sum of relocation costs, RelC, and lost users costs,
LuC). In the proposed model the variable RelC is time dependent and it is function of the congestion level.
The RM matrix belongs to a set of matrix M such that if a station is seller it must not be receiver. The upper
bound (UB with ubk entries) and the lower bound (LB with lb, entries) of the problem are calculated adjusting the
possible maximum number of transferable bikes or free docking points. This correction is due to find the
minimum number of relocated bikes that maximize the users’ satisfaction. Moreover if the problem is over
constrained, no relocation is feasible. For example if all station are receivers, no bikes can be delivered.
The relocation paths for carrier vehicles are obtained by solving a Travelling Salesman Problem in the same
level of the optimization problem (fixed point problem). In particular the redistribution truck must previously
pass through the seller stations. The lost users costs are calculated with the BSS simulation considering PDp and
PDb slots and bikes demands. Differently from other approaches that use bi-level formulations, the proposed
minimization problem is formulated as fixed point Non Linear Integer Optimization. The solution algorithm is
based on a Branch and Bound procedure. The outputs are the optimal relocation matrix and the optimal relocation
path and bikes distribution among the stations.
(RM', RelP’) = argmin RelC(RelP(RM)) + ^LuCj (PDb,PDp,RelP (RM))
s.t.
Ns Ns
£ Cn< i=1 ¿-=1
Ns Ns Ns
2)nH¡i <ub,,.. i=l ■. 2) rmi* - ubk •'■ ■■■ • 2) rmM - ub«*; i=l i=1
Ns Ns Ns
Yrmu>-lblt. ..., yrmit > -lb,,..., y.rmm > -lb,
k=1 k=1 k=1
RM£M„,
= ](%)«..........ns , a* G NI 3k e {l,..„ Ns} : Vi e {l,..„ Ns}
k=l,...,Ns
2)«at =0
(1)
3. Numerical application
The proposed algorithm has been applied to a portion of a BSS. This part of the entire BSS network is made
up of 5 stations that represent the typical scheme of a wider real BSS considering a larger number of central or
peripheral stations. Thanks to its modular properties, the proposed algorithm can be easily scaled to the entire
BSS. In the application we have considered three different level of demand and different days of the week.
The station 1 is located in the city centre while the other stations are located in the outskirts of the city. The
distances in meters between the stations are reported in the Table 1. The parameters used for each station of the
application reflect average values of medium-large size BSS. The method has been applied considering three
working days with 24 hours/day of operations. Each day is divided into 288 steps (Z = 288), 5 minutes each long.
The starting data are: the number of stations Ns = 5, the number of carrier vehicles (i.e. redistribution trucks) Nrt
208
Leonardo Caggiani and Michele OttomaneHi /Procedía - Social and Behavioral Sciences 87 (2013) 203 - 210
= 1 with a capacity Crt = 20 bikes, the number of docking points per station (Nd1; ... Nd5) = (40, 30, 30, 20, 20),
the number of available bikes (Nb1; ... Nb5) = (10, 10, 10, 10, 10), Gap Time = 12 steps.
Table 1. Station distances [m]
O/D 1 2 3 4 5
1 0 400 500 300 300
2 400 0 700 700 600
3 500 700 0 400 800
4 300 700 400 0 600
5 300 600 800 600 0
Since all the distances between stations (Tab. 1) are lower than one kilometer we assume that the truck travel
and operation time between two stations (also in the peak hours) is lower than five minutes that is a truck
movement takes place within one step. The total redistribution cost per kilometer is assumed to be 0.30 Euros
(considering depreciation, taxes, fuel and tires consumption and maintenance costs); the cost for each lost user is
fixed to 0.7 Euros (based on subscription and fees of the most of the major BSS). Actually, the costs for lost users
should take into account all the impacts given to the consequent use of no eco-friendly transport means. The
bicycles demand is distributed among the stations so that the central station (station 1) is mainly an arrival station
during the morning and during the early afternoon and mainly a departure station during the rest of the day. The
converse happens for the other four stations.
To evaluate the performances of the proposed model, we have tested the algorithm considering two cases and
three levels of demand. The two cases are: no relocation and relocation with variable gap time (proposed DSS).
Some results of the mentioned cases are reported in Table 2. In this table are depicted also the obtained result of
the FDSS model with variable GT. The comparison is possible because the starting data of both model
application are the same. In all considered cases, the new proposed DSS leads to a reduction of the number of
lost users. Also in the case of low demand level, positive results have been reached. Assuming higher level of
demand, due to the congestion of the system, the proposed method shows a lower reduced number of lost users.
Making a comparison between the obtained results of the proposed model and those of the FDSS, it is clear that
the model with constant relocation time intervals performs better (in terms of number of satisfied users) than the
method with variable GT for the case of low demand. With increasing congestion of the system (see demand
level 3) the FDSS involves, on the other hand, lower costs of relocation with slightly better average user
satisfaction.
Leonardo Caggiani and Michele OttomaneUi /Procedía - Social and Behavioral Sciences 87 (2013) 203 - 210
209
Table 2. Summary of obtained results
demand level 1 2 3
number of day i 2 3 1 2 3 1 2 3
pickup demand 263 302 282 477 505 494 781 720 811
Variable GT
relocated bikes 59 88 76 156 153 172 87 83 70
lost users (no rel.) 52 76 60 161 193 188 361 304 391
lost users (rel.) 29 19 22 88 109 112 324 269 341
lost users reduction (%) 44.2 75.0 63.3 45.3 43.5 40.4 10.2 11.5 12.8
relocation costs 63.9 76.5 59.4 114.6 114.9 134.1 60.9 62.4 55.5
Constant GT
relocated bikes 84 110 85 145 238 163 140 97 75
lost users (no rel.) 53 68 54 170 178 192 333 302 403
lost users (rel.) 11 12 22 110 118 104 286 286 350
lost users reduction (%) 79.0 82.0 59.0 35.0 34.0 46.0 14.0 5.0 13.0
relocation costs 84.6 91.2 71.7 114.9 110.1 140.1 94.2 84.0 58.8
4. Conclusions
In this paper a micro-simulation model for optimal relocation of bikes in bike-sharing systems has been
presented. In particular, the proposed model jointly determines the optimal carrier vehicles route and the number
of bikes to be repositioned with the relevant stations. The results show that the relocation management increases
of users satisfaction in term of probability of finding available bikes or free docking point. In particular the
proposed DSS is more suitable for non congested bike-sharing systems. The method is modular so that it can be
used for wider systems. The proposed DSS reproduce in detailed way the system, thus it can be also used for both
strategic design and/or real-time management that is to determine the optimal layout of the BSS. Additional
simulations for large-scale BSS with multiple carrier vehicles are needed and are in progress in order to check the
robustness of the method. Further research will deal with the implementation of the artificial NNs based model
for the real-time estimation of bikes demand based on real systems with consequent model validation.
210
Leonardo Caggiani and Michele Ot.toman.elli /Procedía - Social and Behavioral Sciences 87 (2013) 203-210
References
Angeloudis, P., Hu, J., & Bell, M.G.H. (2012). Strategie Repositioning Algorithm for Bicycle-Sharing Schemes, Proc, of the 91th Meeting of
the Transportation Research Board, paper 12-3210, Washington D.C., USA
Barth, M., & Todd, M. (2001). User Behaviour Evaluation of an Intelligent Shared Electric Vehicle System, Transportation Research
Record: Journal of the Transportation Research Board, 1760, 145-152.
Benchimol, M., Benchimol, P, Chappert, B., de la Taille, A., Laroche, F., Meunier, F., & Robinet, L. (2011). Balancing the stations of a self
sendee “bike hire” system. RAIRO-Operations Research, 45(1), 1-15.
Borgnat P., Abry P., Flandrin P., & Rouquier, J.-B. (2009). Studying Lyon's Velo'V: A Statistical Cyclic Model. Proceedings of the European
Conference on Complex Systems ( ECCS'09). Warwick, UK, Sept. 2009
Büttner, J., Mlasowsky, H., Birkholz, T., Groper, D., Fernandez, A. C., Emberger, & Banfi, M. (2011). Optimising Bike Sharing in European
Cities: A Handbook, Intelligent Energy Europe program (IEE). http://obisproject.com. Accessed Feb. 13, 2012.
Caggiani, L., & Ottomanelli, M. (2012). A modular soft computing based method for vehicles repositioning in bike-sharing systems,
Procedia - Social and Behavioral Sciences, 54, 675-684, DOI: 10.1016/j.sbspro.2012.09.785
Chemla, D., Meunier, F., & Wolfler Calvo, R. (2011). Balancing a bike-sharing system with multiple vehicles. 12e congrès annuel de la
ROADEF, Saint-Etienne, France, 2 au 4 Mars 2011.
Cheung, R.K. & Powell, W.B. (1996). .An algorithm for multistage dynamic networks with random arc capacities, with an application to
dynamic fleet management. Operations Research, 44, 951-963.
Contrado, C., Morenci, C., & Rousseau, L.-M. (2012). Balancing a Dynamic Public Bike-Sharing System.
https://wvw.cirrelt.ca/DocumentsTravail/CIRRELT-2012-09.pdf. Accessed Mar. 20, 2012.
Crainic, T.G. (2000). Sendee network design in freight transportation. European Journal of Operational Research, 122, 272-288.
Dell'Orco, M., Caggiani, L., & Sassanelli, D. (2011). Neuro-fuzzy Decision Support System for relocation process in car sharing systems. In:
(Crisalli U and Mussone L eds.) Transport management and land-use effects in presence of unusual demand. Selected papers. Franco Angeli
Pubbl, Milan, Italy
DeMaio, P. (2009). Bike-sharing: History, Impacts, Models of Provision, and Future. Journal of Public Transportation, 12(4).
Du, Y., & Hall, R. (1997). Fleet sizing and empty equipment redistribution for center-terminal transportation networks. Management Science,
43, 145-157.
Forma, L, Raviv, T., & Tzur, M. (2010). The Static Repositioning Problem in a Bike-Sharing System. Proc. of TRISTAN VII, seventh
Triennial Symposium on Transportation .Analysis, Tromso, Norway, June 20-25, 2010.
Fricker, C., & Gast, N. (2012). Incentives and regulations in bike-sharing systems with stations of finite capacity.
http://arxiv.org/pdf/1201.1178vl.pdf. Accessed Feb. 13,2012.
Froehlich, J. Neumann & Oliver, N. (2009) Sensing and predicting the pulse of the city through shared bicycling, Proc. of Twenty-First
International Joint Conference on .Artificial Intelligence (IJCAI-09), pp. 1420-1426
Kek, A.G.H., Cheu R. L., & Xu, J. (2005). Trip Forecasting Models for Intelligent Community Vehicle Systems, Proc. of the 84th .Annual
Meeting of the Transportation Research Board, Washington, D.C., CD-ROM.
Kek, A.G.H., Cheu, R.L., & Chor, M.L. (2006). Relocation simulation model for multiple-station shared-use vehicle systems, Transportation
Research Record: Journal of the Transportation Research Board, 1986, 81-88.
Kek, A.G.H., Cheu, R.L., Meng, Q., & Fung, C.H. (2009). A decision support system for vehicle relocation operations in carsharing systems,
Transportation Research Part E, 45(1), 149-158.
Kochel, P., Kunze, S., & Nielander, U. (2003). Optimal control of a distributed sendee system with moving resources: Application to the fleet
sizing and allocation problem. Int. J. Production Economics, 81—82, 443-459.
Nair, R., & Miller-Hooks, E. (2011). Fleet management for vehicle sharing operations. Transportation Science, 45(4), 524-540.
Sayarshad, H., Tavassoli, S., & Zhao, F. (2012). A multi-periodic optimization formulation for bike planning and bike utilization, Applied
Mathematical Modelling, Atricle in press, doi:10.1016/j.apm.2011.12.032.
Shu, J., Chou, M., Liu, Q., Teo, C.-P., & Wang, I-L. (2010). Bicycle-sharing system: deployment, utilization and the value of re-distribution,
http://wvw.bschool.nus.edu.sg/Staff/bizteocp/BS2010.pdf. Accessed Feb. 15, 2012.
Vogel, P., & Mattfeld, D.C. (2010). Modeling of repositioning activities in bike-sharing systems, Proc. of 12th WCTR, July 11-15, 2010 -
Lisbon, Portugal. | |
