Dynamic Intra-Cell 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 at some locations and overages at 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 user demand in time. In this paper, we study the dynamic intra-cell repositioning of bikes by a single mover in free-floating bike-sharing systems. Considering that users can drop off bikes almost anywhere in free-floating systems, we study the simultaneous reposition of bikes among gathering points and collection of bikes scattered along the paths between gathering points under stochastic demands at both the gathering points and along the paths. We formulate the problem as a Markov decision process (MDP), design a policy function approximation (PFA) algorithm, and apply the optimal computing budget allocation method (OCBA) to search for the optimal policy parameters. We perform a comprehensive numerical study using test instances constructed based on the real data set of a major free-floating bike-sharing company in China, 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.