Please wait a minute...
浙江大学学报(工学版)  2018, Vol. 52 Issue (7): 1275-1283    DOI: 10.3785/j.issn.1008-973X.2018.07.007
自动化技术     
共享自行车系统调度区域的分形树自平衡划分算法
刘冬旭1,2, 董红召1
1. 浙江工业大学 智能交通系统联合研究所, 浙江 杭州 310014;
2. 浙江广播电视大学 信息学院, 浙江 杭州 310012
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
 全文: PDF(5741 KB)   HTML
摘要:

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

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.

收稿日期: 2017-12-13 出版日期: 2018-06-26
CLC:  TP206  
基金资助:

国家自然科学基金资助项目(61773347);浙江省自然科学基金资助项目(LY17F030017).

通讯作者: 董红召,男,教授.orcid.org/0000-0001-5905-567X.     E-mail: its@zjut.edu.cn
作者简介: 刘冬旭(1976-),女,副教授,从事智能交通研究.orcid.org/0000-0002-2282-8963.E-mail:liudx@zjtvu.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  

引用本文:

刘冬旭, 董红召. 共享自行车系统调度区域的分形树自平衡划分算法[J]. 浙江大学学报(工学版), 2018, 52(7): 1275-1283.

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.

链接本文:

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

[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] 汤雪萍, 鲁天龙, 黄平捷, 侯迪波, 张光新. 行为规划和浓度梯度法联合的河道污染源追踪定位方法[J]. 浙江大学学报(工学版), 2018, 52(3): 543-551.
[2] 刘景明, 黄平捷, 侯迪波, 张光新, 张宏建. 河流突发污染的污染物浓度动态校正方法[J]. 浙江大学学报(工学版), 2017, 51(12): 2459-2465.
[3] 刘世成, 王海清, 李平. 基于秩-1矩阵摄动的递归主元分析算法[J]. J4, 2009, 43(5): 827-831.