Dynamic scheduling strategy for bicycle-sharing in cities

doi:10.3969/j.issn.1000-5641.2019.06.009

Abstract

Abstract: To meet the soaring demand of share bike using and improve the service efficiency of bicycle-sharing, this paper proposes a two-stage shared bicycle real-time delivery and scheduling framework based on road condition information. At the offline modeling phase, clustering is implemented on the historical short-distance taxi trajectory data using RET(Regional Extraction Technique) algorithm, to obtain the popular regions of pick-up (or drop-off), and the frequencies of the pick-up (or drop-off) at different time periods. At the online scheduling phase, a dynamic scheduling optimization model (called ROM (Real-time Optimization Model)) for bicycle-sharing is designed to obtain the popular pick-up regions in the next time period. Specifically, searching for the k-nearest neighbor bicycle drop-off regions within the current time period, and combining them with the real-time road conditions to recommend the top-k roads with convenient vehicular access for the bike dispatching car. Experiments on the taxi trajectory dataset show that the proposed method is more effective than the traditional bicycle scheduling strategies.

Key words: dynamic scheduling strategy, city shared bike, pick-up region, drop-off region, real-time road conditions

CLC Number:

TP311

XIE Qing-cheng, MAO Jia-li, LIU Ting. Dynamic scheduling strategy for bicycle-sharing in cities[J]. Journal of East China Normal University(Natural Sc, 2019, 2019(6): 88-102.

References

[1] CHANG H W, TAI Y C, HSU Y J. Context-aware taxi demand hotspots prediction[J]. International Jounal of Business Intelligence and Data Mining, 2010, 5(1):3-18.
[2] LI X L, PAN G, WU Z H, et al. Prediction of urban human mobility using large-scale taxi traces and its application[J]. Frontiers of Computer Science, 2012, 6(1):111-121.
[3] LIU H P, JIN C Q, ZHOU A Y. Popular route planing with travel cost estimation[C]//International Conference on Database Systems for Advanced Applications(DASFAA), 2016, 2016:403-418.
[4] CHEN C, CHEN X, WANG Z, et al. Scenicplanner:Planning scenic travel routes leveraging heterogeneous user-generated digital footprints[J]. Frontiers of Computer Science, 2017, 11(1):61-74.
[5] EOIN O M, DAVID B S. Data analysis and optimization for (citi)bike sharing[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence. AAAI, 2015:687-694.
[6] DIMITRIOS T, IOANNIS B, VANA K. Lessons learnt from the analysis of a bike sharing system[C]//PETRA'17 Proceedings of the 10th International Conference on PErvasive Technologies Related to Assistive Environments. 2017:261-264.
[7] CHENG F, JANE H, DANIEL R. Moment-based probabilistic prediction of bike availability for bike-sharing systems[C]//International Conference on Quantitative Evaluation of Systems, QEST 2016:Quantitative Evaluation of Systems. 2016:139-155.
[8] CHEN L B, ZHANG D Q, PAN G, et al. Bike sharing station placement leveraging heterogeneous Urban open data[C]//Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. ACM, 2015:571-575.
[9] DIVYA S, SOMYA S, PETER I F, et al. Predicting bike usage for New York City.s Bike sharing system[C]//Association for the Advancement of Artificial Intelligence. 2015:110-114.
[10] LIU J M, SUN L L, CHEN W W, et al. Rebalancing bike sharing systems:A multi-source data smart optimization[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016:1005-1014.
[11] FÁBIO C, ANAND S, BRUNO P.B, et al. A heuristic algorithm for a single vehicle static bike sharing rebalancing problem[J]. Computers & Operations Research, 2017, 79:19-33.
[12] ALVAREZ-VALDES R, BELENGUER J M, BENAVENT E, et al. Optimizing the level of service quality of a bike-sharing system[J]. Omega, 2015, 62:163-175.
[13] LI Y X, ZHENG Y, ZHANG H C, et al. Traffic prediction in a bike-sharing system[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM SIGSPATIAL, 2015:Article No 33.
[14] CHRISTIAN K, GUNTHER R R. Full-load route planning for balancing bike sharing systems by logic-based benders decomposition[J]. Wiley Periodicals, 2017, 69(3):270-289.
[15] DIJSTRA E D. A note on two problem in connexion with graphs[J]. Numerische Mathematik, 1959(1):269-271.
[16] MAO J L, SONG Q G, JIN C Q, et al. TSCluWin:Trajectory stream clustering over sliding window[C]//DASFAA 2016:Databases Systems for Advanced Applications. 2016:133-148.
[17] JOSHI S, KAUR S. Nearest neighbor insertion algorithm for solving capacitated vehicle routing problem[C]//International Conference on Computing for Sustainable Global Development. 2015:86-88.
[18] ZHAO F G, LI S J, SUN J S, et al. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computers and Industrial Engineering(COMPUT IND ENG), 2009, 56(4):1642-1648.