Monte carlo tree search for dynamic bike repositioning in bike-sharing systems

With the popularity of green travel and the aggravation of traffic congestion, Bike Sharing System (BSS) is adopted increasingly in many countries nowadays. However, the BSS is prone to be unbalanced because of the unequal supply and demand in each station, which leads to the loss in customer requirements. To address this issue, we develop a Monte Carlo tree search based Dynamic Repositioning (MCDR) method, which can help operators to decide at any time: (i) which station should be balanced firstly, and (ii) how many bikes should be picked or dropped at an unbalanced station. In this paper, we first employed a Density-based Station Clustering algorithm to reduce the problem complexity. Then the concept of service level is introduced to calculate the number of bikes that need to be transferred at each station. Finally, considering multiple factors, we propose a dynamic bike repositioning approach named MCDR, which can provide an optimal repositioning strategy for operators. Experimental results on a real-world dataset demonstrate that our method can reduce customer loss more effectively than the state-of-the-art methods.