Column-generation-based heuristics for integrating static rebalancing and faulty bike collection in bike-sharing systems

This paper studies the static rebalancing problem in bike-sharing systems with faulty bike collection and multiple depots. The decisions of this problem involve the routes to be executed by rebalancing vehicles, the number of usable bikes to load and unload across stations, and the number of faulty bikes to collect from each station. The goal is to minimize rebalancing costs and penalty costs due to users’ dissatisfaction. We propose the first cycle formulation for this problem to model decisions regarding the execution of vehicle routes explicitly. To solve this problem, we implement a column-generation-based heuristic and a matheuristic that relies on a neighborhood-search scheme. We also propose a restrictive optimization model that can be solved after executing the matheuristic to further improve the quality of the solution. Our computational results on a set of small instances show that our matheuristic returns solutions equal to the optimal ones. Our solution methods can also solve bigger instances based on a variety of real-world bike-sharing systems. For these instances, the results provide evidence of the effectiveness of our solution methods, and they considerably improve the service level offered to the users of bike-sharing systems. Finally, we assess the effect of the availability of multiple vehicles and depots on the quality of the solutions. Both of them are beneficial, but the advantage of having multiple depots is bigger than the advantage of having multiple vehicles.