Dynamic Repositioning in Free-Floating Bike Sharing Systems Using Approximate Dynamic Programming

In bike sharing systems, the spatiotemporal imbalance of bike flows leads to shortages of bikes in some areas and overages in some others, depending on the time of the day, resulting in user dissatisfaction. Repositioning needs to be performed timely to deal with the spatiotemporal imbalance and to meet customer demand in time. In this paper, we study the dynamic repositioning of bikes under stochastic demand in free-floating bike sharing systems. Considering that customers can drop off bikes almost anywhere in free-floating systems, we study the simultaneous reposition of bikes among gathering points and collection of scattered bikes. We formulate the problem as a Markov Decision Process (MDP), design a policy function approximation (PFA) algorithm, and apply the optimal computing budget allocation (OCBA) method to search for the optimal policy parameters. We perform a comprehensive numerical study, which demonstrates the outperformance of the proposed PFA policy against the benchmark policies and the practical implications on the value of repositioning and the impact of bike scatteredness.


Department of Industrial Engineering, Tsinghua University & Department of Automation, Tsinghua University. Current version: November 2020