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

为了满足大型共享自行车系统（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.