A crowdsourced dynamic repositioning strategy for public bike sharing systems

I-Lin Wang; Chen-Tai Hou

doi:10.3934/naco.2021049

Article Contents

2022, Volume 12, Issue 1: 31-46. Doi: 10.3934/naco.2021049

This issue Previous Article Variable fixing method by weighted average for the continuous quadratic knapsack problem Next Article Levenberg-Marquardt method for absolute value equation associated with second-order cone

A crowdsourced dynamic repositioning strategy for public bike sharing systems

I-Lin Wang^, and
Chen-Tai Hou

Department of Industrial and Information Management, National Cheng Kung University, Tainan 704, Taiwan

^* Corresponding author: ilinwang@mail.ncku.edu.tw
^* Corresponding author: ilinwang@mail.ncku.edu.tw

Received: July 2020

Revised: January 2021

Early access: November 2021

Published: March 2022

The first author is supported by MOST grant 110-2221-E-006-191-MY3

Abstract / Introduction Full Text(HTML) Figure(5) Related Papers Cited by

Abstract

Public bike sharing systems have become the most popular shared economy application in transportation. The convenience of this system depends on the availability of bikes and empty racks. One of the major challenges in operating a bike sharing system is the repositioning of bikes between rental sites to maintain sufficient bike inventory in each station at all times. Most systems hire trucks to conduct dynamic repositioning of bikes among rental sites. We have analyzed a commonly used repositioning scheme and have demonstrated its ineffectiveness. To realize a higher quality of service, we proposed a crowdsourced dynamic repositioning strategy: first, we analyzed the historical rental data via the random forest algorithm and identified important factors for demand forecasting. Second, considering 30-minute periods, we calculated the optimal bike inventory via integer programming for each rental site in each time period with a sufficient crowd for repositioning bikes. Then, we proposed a minimum cost network flow model in a time-space network for calculating the optimal voluntary rider flows for each period based on the current bike inventory, which is adjusted according to the forecasted demands. The results of computational experiments on real-world data demonstrate that our crowdsourced repositioning strategy may reduce unmet rental demands by more than 30% during rush hours compared to conventional trucks.

Keywords:

Mathematics Subject Classification: Primary: 90B06, 90B10; Secondary: 90C10.

Citation:

FullText(HTML)

Figure 1. Illustrative VRFM example

Download: Full-size image PowerPoint slide

Figure 2. Comparison of the prediction performances for crowdsourced repositioning

Download: Full-size image PowerPoint slide

Figure 3. Comparison of the repositioning performances of crowdsourcing versus various numbers of trucks

Download: Full-size image PowerPoint slide

Figure 4. Comparison of repositioning strategies in 100 simulated daily rentals

Download: Full-size image PowerPoint slide

Figure 5. Comparison of the repositioning performances of crowdsourcing and trucks

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	H. I. Ashqar, M. Elhenawy, M. H. Almannaa, A. Ghanem, H. A. Rakha and L. House, Modeling bike availability in a bike-sharing system using machine learning, in 2017 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), IEEE, 2017. doi: 10.1109/mtits.2017.8005700.
[2]	A. Bargar, A. Gupta, S. Gupta and D. Ma, Interactive visual analytics for multi-city bikeshare data analysis, in The 3rd International Workshop on Urban Computing (UrbComp 2014), New York, USA, 2014.
[3]	M. Benchimol, P. Benchimol, B. Chappert, A. de la Taille, F. Laroche, F. Meunier and L. Robinet, Balancing the stations of a self service "bike hire" system, RAIRO - Operations Research, 45 (2011), 37-61. doi: 10.1051/ro/2011102.
[4]	L. Breiman, Random forests, Machine Learning, 45 (2001), 5-32. doi: 10.1023/A:1010933404324.
[5]	L. Cagliero, T. Cerquitelli, S. Chiusano, P. Garza and X. Xiao, Predicting critical conditions in bicycle sharing systems, Computing, 99 (2016), 39-57. doi: 10.1007/s00607-016-0505-x.
[6]	J. X. Cao, C. C. Xue, M. Y. Jian and X. R. Yao, Research on the station location problem for public bicycle systems under dynamic demand, Computers & Industrial Engineering, 127 (2019), 971-980. doi: 10.1016/j.cie.2018.11.028.
[7]	L.-C. Chang, Design and Management of Urban Bike Sharing Systems, Master's thesis, Department of Industrial and Information Management, National Cheng Kung University, Tainan 701, Taiwan, 2010.
[8]	D. Chemla, F. Meunier and R. W. Calvo, Bike sharing systems: Solving the static rebalancing problem, Discrete Optimization, 10 (2013), 120-146. doi: 10.1016/j.disopt.2012.11.005.
[9]	H. Chung, D. Freund and D. Shmoys, Bike angels: An analysis of citi bike incentive program, In Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies, article 5.
[10]	C. Contardo, C. Morency and L. Roux, Balancing a dynamic public bike-sharing system, Centre Interuniversitaire de Recherche sur les Rseaux d'Entreprise, la Logistique et le Transport, 4.
[11]	J. Froehlich, J. Neumann and S. Oliver, Sensing and predicting the pulse of the city through shared bicycling, International Joint Conference on Artificial Intelligence, 9 (2009), 1420-1426.
[12]	X. Gao and G. M. Lee, Moment-based rental prediction for bicycle-sharing transportation systems using a hybrid genetic algorithm and machine learning, Computers & Industrial Engineering, 128 (2019), 60-69. doi: 10.1016/j.cie.2018.12.023.
[13]	K. Gebhart and R. B. Noland, The impact of weather conditions on bikeshare trips in washington, DC, Transportation, 41 (2014), 1205-1225. doi: 10.1007/s11116-014-9540-7.
[14]	C.-P. Hung, Optimal Station Allocation and Dynamic Bike Repositioning Strategies for Public Bike Sharing Systems, Master's thesis, Department of Industrial and Information Management, National Cheng Kung University, Tainan 701, Taiwan, 2011.
[15]	A. A. Kadri, I. Kacem and K. Labadi, A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems, Computers & Industrial Engineering, 95 (2016), 41-52. doi: 10.1016/j.cie.2016.02.002.
[16]	A. Kaltenbrunner, R. Meza, J. Grivolla, J. Codina and R. Banchs, Urban cycles and mobility patterns: Exploring and predicting trends in a bicycle-based public transport system, Pervasive and Mobile Computing, 6 (2010), 455-466. doi: 10.1016/j.pmcj.2010.07.002.
[17]	M. Kaspi, T. Raviv, M. Tzur and H. Galili, Regulating vehicle sharing systems through parking reservation policies: Analysis and performance bounds, European Journal of Operational Research, 251 (2016), 969-987. doi: 10.1016/j.ejor.2015.12.015.
[18]	M.-T. Liao, A Strategic Study on Managing Public Bike Sharing Systems by Demand Profile and Temporary Manpower Allocation, Master's thesis, Department of Industrial and Information Management, National Cheng Kung University, Tainan 701, Taiwan, 2012.
[19]	W.-Y. Loh, Classification and regression trees, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 1 (2011), 14-23. doi: 10.1002/9781118660146.ch1.
[20]	R. Meddin and D. DeMaio, The meddin bike-sharing world map, Available from: http://bikesharingworldmap.com.
[21]	R. Montoliu, Discovering mobility patterns on bicycle-based public transportation system by using probabilistic topic models, in Ambient Intelligence - Software and Applications, Springer Berlin Heidelberg, (2012), 145–153. doi: 10.1007/978-3-642-28783-1_18.
[22]	O. O'Brien, J. Cheshire and M. Batty, Mining bicycle sharing data for generating insights into sustainable transport systems, Journal of Transport Geography, 34 (2014), 262-273. doi: 10.1016/j.jtrangeo.2013.06.007.
[23]	T. Raviv and O. Kolka, Optimal inventory management of a bike-sharing station, IIE Transactions, 45 (2013), 1077-1093. doi: 10.1080/0740817x.2013.770186.
[24]	T. Raviv, M. Tzur and I. A. Forma, Static repositioning in a bike-sharing system: models and solution approaches, EURO Journal on Transportation and Logistics, 2 (2013), 187-229. doi: 10.1007/s13676-012-0017-6.
[25]	R. A. Rixey, Station-level forecasting of bikesharing ridership, Transportation Research Record: Journal of the Transportation Research Board, 2387 (2013), 46-55. doi: 10.3141/2387-06.
[26]	A. Sarkar, N. Lathia and C. Mascolo, Comparing cities' cycling patterns using online shared bicycle maps, Transportation, 42 (2015), 541-559. doi: 10.1007/s11116-015-9599-9.
[27]	J. Schuijbroek, R. Hampshire and W.-J. van Hoeve, Inventory rebalancing and vehicle routing in bike sharing systems, European Journal of Operational Research, 257 (2017), 992-1004. doi: 10.1016/j.ejor.2016.08.029.
[28]	J. Shu, M. C. Chou, Q. Liu, C.-P. Teo and I.-L. Wang, Models for effective deployment and redistribution of bicycles within public bicycle-sharing systems, Operations Research, 61 (2013), 1346-1359. doi: 10.1287/opre.2013.1215.
[29]	P. Vogel, T. Greiser and D. C. Mattfeld, Understanding bike-sharing systems using data mining: Exploring activity patterns, Procedia - Social and Behavioral Sciences, 20 (2011), 514-523. doi: 10.1016/j.sbspro.2011.08.058.
[30]	P. Vogel and D. C. Mattfeld, Strategic and operational planning of bike-sharing systems by data mining – a case study, in Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2011,127–141. doi: 10.1007/978-3-642-24264-9_10.
[31]	P. Vogel, B. A. N. Saavedra and D. C. Mattfeld, A hybrid metaheuristic to solve the resource allocation problem in bike sharing systems in Hybrid Metaheuristics, Springer International Publishing, (2014), 16–29. doi: 10.1007/978-3-319-07644-7_2.
[32]	I.-L. Wang and T.-L. Wu, A simulation study on the value and impact of exploiting rental information to the metropolitan bike sharing systems, Technical report.
[33]	S. Yan, J.-R. Lin, Y.-C. Chen and F.-R. Xie, Rental bike location and allocation under stochastic demands, Computers & Industrial Engineering, 107 (2017), 1-11. doi: 10.1016/j.cie.2017.02.018.
[34]	Z. Yang, J. Hu, Y. Shu, P. Cheng, J. Chen and T. Moscibroda, Mobility modeling and prediction in bike-sharing systems, in Proceedings of the 14th Annual International Conference on Mobile Systems, Applications, and Services, ACM, 2016
[35]	J. W. Yoon, F. Pinelli and F. Calabrese, Cityride: A predictive bike sharing journey advisor, in 2012 IEEE 13th International Conference on Mobile Data Management, 2012. doi: 10.1109/mdm.2012.16.