Dynamic scheduling strategy for bicycle-sharing in cities

XIE Qing-cheng; MAO Jia-li; LIU Ting

doi:10.3969/j.issn.1000-5641.2019.06.009

Issue 6

Dec. 2019

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2019 > (6): 88-102

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

Citation:

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

Citation:

PDF( 1225 KB)

Dynamic scheduling strategy for bicycle-sharing in cities

doi: 10.3969/j.issn.1000-5641.2019.06.009

XIE Qing-cheng^1
,,
MAO Jia-li^{1,2
,
,},
LIU Ting¹

1.
School of Computing, China West Normal University, Nanchong Sichuan 637000, China
2.
School of Data Science and Engineering, East China Normal University, Shanghai 200062, China

Received Date: 2018-09-03
Publish Date: 2019-11-25

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.
- dynamic scheduling strategy,
- city shared bike,
- pick-up region,
- drop-off region,
- real-time road conditions

FullText(HTML)

References(18)

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. doi: 10.1504/IJBIDM.2010.030296
[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. http://d.old.wanfangdata.com.cn/Periodical/zggdxxxswz-jsjkx201201009
[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. doi: 10.1007/s11704-016-5550-2
[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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=9b015e7c3d8974d18e08b7d023892292
[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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5a7bc0394d83c1171935047514e7fb07
[15]	DIJSTRA E D. A note on two problem in connexion with graphs[J]. Numerische Mathematik, 1959(1):269-271. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=10.1177/001872676702000107
[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. doi: 10.1016/j.cie.2008.10.014