What if rebalancing fleets could adapt? A two-stage stochastic model for dynamic bike redistribution

Bike-sharing systems are an important mode of transportation, enabling individuals to rent bikes for short trips and return them to any station throughout the city. However, the dynamic nature of user arrivals at each station leads to imbalances between bike supply and demand, resulting in unsatisfied users. An essential challenge lies in efficiently deploying and scheduling rebalancing vehicles for bike redistribution, as these decisions have a considerable effect on the efficiency of the system. To tackle this challenge, we propose a dynamic rebalancing model that integrates tactical and operational decisions within a single optimization framework. Unlike approaches that treat these decisions separately, our model captures the interaction between the two: in the first stage, it determines how many vehicles should be deployed over the planning horizon (tactical decision), and in the second stage, it assigns stations to dynamic rebalancing groups and allocates vehicles to these groups in response to demand realizations (operational decisions). To address the computational challenge, we propose two approaches: an Improved Integer L-shaped decomposition algorithm and a heuristic that combines machine learning with an early stopping criterion to estimate the second-stage cost function. Moreover, we generate forecasts of rental and return demand and incorporate them into the optimization model to enhance decision-making under demand uncertainty. Our numerical results show that the proposed heuristic is highly effective in minimizing the unsatisfied demand while reducing the computational costs efficiently.