Efficient heuristic algorithm for the Robust Bike Sharing Rebalancing Problem

Bike sharing systems are becoming increasingly common as a mobility option in urban centers. However, over time such systems are subject to unbalanced bike distributions in its stations. Furthermore, the demand of a station (that is, the number of bikes in surplus or shortage) might be uncertain, adding further complexity to the planning of pickup and delivery operations. In this work we address the Robust Bike Sharing Rebalancing Problem (RBRP), which uses Robust Optimization techniques to model uncertain demands in the planning of such rebalancing operations. Due to the complexity of the problem, we propose an efficient heuristic algorithm based on Slack Induction by String Removals (SISRs), using auxiliary structures to reduce the time complexity of the algorithms.