Research And Implementation Of A Shared Bicycle Dynamic Redistribution Algorithm Based On Monte Carlo Tree Search

Bike-sharing systems(BSS)are now popular in more and more countries.People usually rent a Shared bike at a station near the starting point and return it at a station near the destination.However,the demand for bikes varies dramatically at different times and in different regions.Therefore,it is easy to make some stations have no bikes to rent and some stations have no space for bikes to store.As a result,the whole BSS is in an unbalanced state,which seriously affects the user experience and leads to the loss of users.BSS managers usually use trucks to move bikes from station to station.However,most of the traditional bike redistribution methods are based on experience,and the number of transferred bikes is also randomly assigned.BSS utilization and user experience remain low.How to choose the next best unbalanced station has always puzzled managers.In order to reduce the loss of users effectively and develop a balanced strategy for managers reasonably,we propose a method based on Monte Carlo tree search for Dynamic bike Repositioning(MCDR).This method can help BSS managers make decisions at any time :(1)which stations should be balanced first;(2)How many bikes should be taken or dropped at the unbalanced station to keep the station available for the coming period of time.In this paper,we first use the density clustering algorithm based on distance-demand similarity to cluster a large number of stations.The stations with short distance and similar demand for bikes are divided into the same cluster.This allows trucks to dynamically reposition bikes within a single cluster,thus reducing the complexity of the problem.Then,a KNN method based on time and weather similarity is used to predict the demand of bike rental and return at the station.Based on the predicted results,we simulate the dynamic flow of bikes.In order to keep the balance state of the station,the concept of service level of the station is proposed in the process of the simulations.According to the service level,we can get the number of bikes need to transferred at the unbalanced stations.Finally,a dynamic bike reposition method based on MCTS is proposed after considering several factors that have an impact on managers' decisions,such as distance,the number of transferred bikes,the urgency of unbalanced station,and the impact of subsequent unbalanced stations.This method can simulate station selection several times under the current real-time state of BSS.Based on the previous simulation results,training and iteratively updating bike repositioning strategy,it can finally provide the manager with the best next unbalanced station selection.In order to make our model take more reasonable decisions in different demand situations,we adjusted the parameters to ensure that the MCTS model can make trucks travel less distance in the case of low demand for bikes and reduce a large number of lost users in the case of high demand for bikes.In this paper,the validity of the proposed model is evaluated through experiments with a real data set of Citi Bikes in New York.The experimental results show that our method is more effective in reducing the number of lost users and practical compared to other existing methods.