Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)  2018, Vol. 52 Issue (7): 1275-1283    DOI: 10.3785/j.issn.1008-973X.2018.07.007
Automatic Technology     
Fractal tree based self-balanced partitioning algorithms for bike sharing system
LIU Dong-xu1,2, DONG Hong-zhao1
1. ITS Joint Research Institute, Zhejiang University of Technology, Hangzhou 310014, China;
2. College of Information Engineering, Zhejiang Radio and Television University, Hangzhou 310012, China
Download:   PDF(5741KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A fractal tree based self-balanced partitioning model for bike sharing system (BSS) redistribution was proposed to solve the problem of lacking scheduling partitioning method for BSS redistribution in order to quickly respond to the bicycle demand of stations and reduce the redistributing service cost of large bike sharing system (BSS). The model was organized by self-similar multi-level redistributing regions including leaf-level, branch-level and root-level. The mutual-balance intensity formulation was built to estimate the complementary feature of bicycle import/export demands between two adjoining regions at same level. The fractal tree based self-balanced partitioning algorithm (FSPA) was designed to realize the proposed model according to the self-similarity of fractal tree. FSPA was combined by the range estimating algorithm of redistribution regions at leaf-level and branch-level considering BSS response speed, the corresponding dynamic clustering algorithm for region partition and the cluster ensemble algorithm using bicycle turnover rate. An empirical study was conducted on Xiasha district of Hangzhou BSS with docks to construct a hierarchical scheduling model with three level self-balanced regions. Results show that the model can effectively decrease cross-region redistributing times and shorten driving distance of vehicle. Then the service costs can be reduced and redistributing efficiency of BSS can be improved.

Received: 13 December 2017      Published: 26 June 2018
CLC:  TP206  
  U121  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

LIU Dong-xu, DONG Hong-zhao. Fractal tree based self-balanced partitioning algorithms for bike sharing system. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1275-1283.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2018.07.007     OR     http://www.zjujournals.com/eng/Y2018/V52/I7/1275


共享自行车系统调度区域的分形树自平衡划分算法

为了满足大型共享自行车系统（BSS）快速响应调度的需求并降低调度成本，针对目前缺少调度区域合理划分研究的问题，提出 BSS调度基于分形树的自平衡区域划分模型.该模型由具有自相似性结构的叶子级、枝节级和根级调度区域组成，给出衡量同级邻近区域租/还需求互补性的互平衡强度计算方法.根据分形树的自相似性特征，设计分形树自平衡区域划分算法（FSPA），包括考虑快速服务响应的分形树叶子级与枝节级调度区域范围计算方法和基于同级区域互平衡强度的自平衡区域划分动态聚类算法，将BSS周转率杠杆引入共协矩阵来实现自平衡区域聚类融合.以杭州市下沙地区锁桩式BSS运营历史数据为例，对构建模型方法进行实验验证，划分了具有分形树特征的三级自平衡调度区域.结果表明，采用自平衡区域划分方法，有助于实现区域内的自平衡，减少跨区调度次数和调度车行驶路程，可以有效地降低调度成本和提升BSS工作效率.

[1] 董红召,赵敬洋,郭海锋.公共慢行系统的动态调度建模与滚动时域调度算法研究的调度[J].公路工程,2009,34(6):68-75. DONG Hong-zhao,ZHAO Jing-yang,GUO Hai-feng. Research on the dynamic model and rolling horizon scheduling algorithm for public-use bicycle vehicle scheduling problem[J]. Highway Engineering, 2009,34(6):68-75.
[2] 董红召,吴满金,刘冬旭,等. 城市公共自行车系统自然租赁需求的估算方法[J].浙江大学学报:工学版,2016,50(2):265-270. DONG Hong-zhao, WU Man-jin, LIU Dong-xu, et al. Estimation method of natural demand of urban public bicycle system[J]. Journal of Zhejiang University:Engineering Science,2016,50(2):265-270.
[3] SALAKEN S M, HOSEN M A, KHOSRAVI A, et al. Forecasting bike sharing demand using fuzzy inference mechanism[J]. Neural Information Processing, 2015, 9491:567-574.
[4] 解小平,邱建东,汤旻安. 基于Elman神经网络的公共自行车单站点需求预测[J]. 计算机工程与应用, 2017, 53(16):221-224. XIE Xiao-ping, QIU Jian-dong, TANG Min-an. Demand prediction of public bicycle rental station based on Elman neural network[J]. Computer Engineering and Applications, 2017, 53(16):221-224.
[5] 林燕平,窦万峰.基于网络模型的城市公共自行车需求量预测研究[J].计算机应用研究,2017,34(9):2692-2695. LIN Yan-ping,DOU Wan-feng. Research on demand prediction of urban bicycle sharing based on network model[J]. Application Research of Computers,2017,34(9):2692-2695.
[6] ADHAM M T, BENTLEY P J. An ecosystem algorithm for the dynamic redistribution of bicycles in London[J]. Information Processing in Cells and Tissues, 2015, 9303:39-51.
[7] 杨继伟,周竹萍,蔡逸飞.基于改进蚁群算法的城市公共自行车动态调度模型[J].北京理工大学学报,2016,36(增2):121-124. YANG Ji-wei, ZHOU Zhu-ping, CAI Yi-fei. Public bicycle dynamic scheduling model based on improved ant colony algorithm[J]. Transactions of Beijing Institute of Technology,2016,36(supple.2):121-124.
[8] SCHUIJBROEK J, HAMPSHIRE R C, VAN HOEVE W J. Inventory rebalancing and vehicle routing in bike sharing systems[J]. European Journal of Operational Research, 2017, 257(3):992-1004.
[9] COME E, OUKHELLOU L. Model-based count series clustering for bike sharing system usage mining:a case study with the Velib' system of Paris[J]. ACM Transactions on Intelligent Systems and Technology, 2014,5(3):39.
[10] 陈昕昀,蒋永康,李牧原,等.基于多目标优化模型的城市公共自行车调度研究[J].现代交通技术,2017,14(1):61-68. CHEN Xin-yun, JIANG Yong-kang, LI Mu-yuan, et al. Research on urban public bicycle scheduling based on multi objective optimization model[J]. Modern Transportation Technology, 2017,14(1):61-68.
[11] 董红召,史彩霞,陈宁,等.基于关联规则的公共自行车调度区域聚类划分[J].科技通报,2013,29(9):209-216. DONG Hong-zhao,SHI Cai-xia,CHEN Ning,et al. Clustering division of public bicycle scheduling regional based on association rules[J]. Bulletin of Science and Technology,2013,29(9):209-216.
[12] 徐建闽,秦筱然,马莹莹.公共自行车多层次分区调度方法研究[J].交通运输系统工程与信息, 2017,17(1):212-219. XU Jian-min, QIN Xiao-ran, MA Ying-ying. Public bicycle multilevel partition scheduling method[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(1):212-219.
[13] 董红召,刘冬旭,陈鹰,等.基于分形理论的企业网络联盟的研究[J].浙江大学学报:工学版,2004,38(1):11-16. DONG Hong-zhao, LIU Dong-xu, CHEN Ying, et al. Research on fractal-based extended enterprise[J]. Journal of Zhejiang University:Engineering Science,2004,38(1):11-16.
[14] 冯中慧,何亮,王栋.基于新的成员选择方法的聚类融合算法[J]. 微电子学与计算机, 2016, 33(11):25-29. FENG Zhong-hui, HE Liang, WANG Dong, Clustering ensemble algorithm based on new members selection method[J]. Microelectronics and Computer, 2016, 33(11):25-29.
[1] TANG Xue-ping, LU Tian-long, HUANG Ping-jie, HOU Di-bo, ZHANG Guang-xin. Tracking and locating channel pollution source combining behavior-based planning and concentration gradient method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(3): 543-551.
[2] LIU Jing-ming, HUANG Ping-jie, HOU Di-bo, ZHANG Guang-xin, ZHANG Hong-jian. Dynamic pollutant concentration correction method for river sudden pollution[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(12): 2459-2465.
[3] LIU Shi-Cheng, WANG Hai-Qing, LI Beng. Recursive PCA algorithm based on rank-one matrix perturbation[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2009, 43(5): 827-831.