Dynamic Rebalancing Problems for Bike-Sharing Systems: Mixed-Integer Programming and Reinforcement Learning Approach

Bike-sharing systems (BSSs) offer a sustainable and efficient transportation solution in urban areas, yet face challenges due to fluctuating demand and peak-hour imbalances, often resulting in bike or dock shortages. To tackle these dynamic rebalancing challenges, we utilize both Mixed-Integer Programming (MIP) and Reinforcement Learning (RL) to minimize lost demand across stations. We first introduce a comprehensive MIP framework for multi-period rebalancing problems, which allows for a detailed analysis of various modeling assumptions, including time discretization, trip distribution, variable domains, and event sequences. Through extensive experiments on both synthetic data and real-world data, the effectiveness of different modeling assumptions and techniques is identified. Building on this foundation, we then leverage RL-based approaches to enable real-time rebalancing, especially addressing the limitations of time discretization in MIP. Our Markov Decision Process (MDP) model is designed with state and action spaces crafted in a continuous-time framework, facilitating seamless cooperation among multiple rebalancing vehicles. Two learning methods are explored, where the routing and inventory decisions are made simultaneously or separately. This RL approach further enhances both the realism and efficiency of rebalancing, reducing lost demand and improving system performance.