Dynamic repositioning strategy in a bike-sharing system; how to prioritize and how to rebalance a bike station

Bike-sharing systems are becoming increasingly popular in large cities. The natural imbalance and the stochasticity of bike's arrivals and departures lead operators to develop redistribution strategies in order to ensure a sufficiently high quality of service for users. Using a Markov decision process approach, we develop an implementable decision-support tool which may help the operator to decide at any point of time (i) which station should be prioritized, and (ii) which number of bikes should be added or removed at each station. Our objective is to minimize the rate of arrival of unsatisfied users who find their station empty or full. The existence of an optimal inventory level at each station is proven. It may vary over time but does not depend on the capacity of the truck which operates the repositioning. Next, we compute the relative value function of the system, together with the average cost and the optimal state. These results are used to derive a policy for station's prioritization using a one-step policy improvement method. We evaluate our policy in comparison with the optimal one and with other intuitive ones in an extended version of our model. From our numerical experiments, we show that only a little intervention of the operator can significantly enhance the quality of service, and that the rule of thumb for bike repositioning is to prioritize the closer, the more active, the closer to be full or empty, and the more imbalanced stations if no reversing in the imbalance is anticipated.