基于时空聚类预测的共享单车调度优化研究

Optimization of shared bicycle scheduling based on spatio-temporal clustering prediction

无桩共享单车网络中存在着供需时空失衡现象,造成了共享资源的浪费及运营商管理成本的增加。为此,针对共享单车需求时间空间的分布特点,本文提出通过聚类分析的方法将具有相似时空属性的单位区域聚合为调度集群,使单车调度问题转化为有时间窗与载重量限制的车辆路径问题,并提出加入衡量集群划分是否合理的惩罚成本,构建共享单车调度路径优化模型。最后,本文改进了贪心算法、遗传算法对模型进行求解,并对算法的调度效果进行比较,为共享单车调度问题提出了从网络分析到调度优化的完整框架和改进算法,具有一定借鉴意义。

Bike-sharing service refers to the mode of bike rental service provided by bike rental companies in public service areas, so as to provide a more sustainable and environmentally-friendly carbon-free transport for urban users. In the face of increasing crowded traffic status and serious environmental problems, bike sharing caters to a greener and healthier option for people′s short trips with the powerful resource integration power, which has been a pivotal component of urban transportation.According to the data provided by iMedia Research, the number of bike-sharing users in China reached 235 million in 2018. There is no doubt that sharing bicycles improves people′s travel convenience and urban traffic condition, while they have also brought some new problems. Due to the unreasonable allocation of bicycle resources, the company always encounters the unexpected situation that in some areas there is not bicycle available, while the bikes in other areas are piled up in a disorderly manner. In such a case, there is an imbalance between the supply and demand in the bike sharing network, which not only causes the waste of resources, but also increases the management cost of operators. For the unreasonable resource allocation in the sharing network, this paper divides the random distribution network of bicycles into multiple clusters with similar saptio-temporal attributes through cluster analysis. The article transforms the bicycle scheduling problem into a vehicle routing problem with time windows and load limitations, and then proposes a scheduling path optimization model and designs algorithms to solve it. The research contents and conclusions of this paper are as follows.In the first part, the paper expounds the practical background and significance of the research topic. It introduces the development of China′s bike-sharing market, compares the advantages and disadvantages of several mainstream operating modes, and lists the significance of the study for operators, consumers and society. Secondly, we introduce the theoretical basis of relevant problems, including the scheduling scheme of shared bikes, the VRP problem and relevant scheduling algorithms.The second part is literature review. It is a rough sorting of the literature on the scheduling optimization researches for bike sharing scheduling, including the research on station-based bike sharing(SBBS) and the research on free-floating bike sharing(FFBS). This part also illustrates the research results of some domestic and foreign scholars who innovatively combined the clustering algorithm with the VPR problem.In the third part, we design and construct the scheduling optimization model and algorithm.(1) As free-floating shared bicycles can be parked anywhere, how to accurately describe and classify the distribution of bicycles in the network has become the key to demand forecast and schedule. Moreover, the demand for shared bikes has obvious spatial temporal attributes, which are reflected in the imbalance of demand distribution in time and space. Hence, the paper would aggregate the cell regions with similar time-space attributes into clusters similar to “virtual base stations” through k-means cluster analysis, and it is deemed as the access objectives of dispatchers.(2) We build the scheduling model with the target of minimum cost. The scheduling cost in the objective function includes the fixed cost, the transportation cost, the loading cost, and the unloading cost. Moreover, we add penalty cost to measure whether the cluster division is feasible. In addition, this paper also considers the constraints on the driving distance and the load of the dispatching vehicle to make the model more realistic.(3) To solve the feasible approximate solution of the corresponding VPR(NP-hard) problem, this paper designs the greedy algorithm and the genetic algorithm to solve the model. In particular, the performances of the algorithms are compared in the follow-up.The fourth part is simulation. According to certain rules, we generate the data of the demand for shared bikes and the distribution of the bike-sharing network in the designated period. Through data simulation, the role of the frame and model in the actual scheduling is studied. The conclusion shows that the number of clusters will greatly affect the scheduling cost;secondly, the overall optimization of the genetic algorithm is better than that of the greedy algorithm, but the greedy algorithm could take less time.The fifth part is the summary and future work. This section points out that more attention should be paid to user-based scheduling in the future, such as studying the role of pricing and rules in guiding the bike-sharing consumers to actively assist operators in resource scheduling.In summary, this paper uses the cluster analysis method to analyze the spatio-temporal attributes of demand in bicycle-sharing network. Moreover, on the base of the spatio-temporal attributes, demand forecasting and scheduling path optimization are carried out. The framework suggested by this paper provides feasible idea for scheduling activities and academic study, which has certain reference significance. The management implications of the conclusions reached in this article are as follows.(1) Enterprise managers need to get more acquainted with the user′s stickiness and satisfaction with the company′s bike-sharing services and determine the appropriate number of dispatching clusters to achieve competitive advantage by reducing dispatching costs.(2) The heuristic algorithm has shown excellent ability when optimizing the scheduling path. Compared with genetic algorithm, although greedy algorithm has a great advantage in solving time, the overall optimization effect is slightly inferior. Hence, operators should make a trade-off between time and accuracy when choosing an algorithm.