A disaggregated integer L-shaped method for the bike sharing rebalancing problem with stochastic demands

This work deals with the bike sharing rebalancing problem with stochastic demands by proposing new formulations, an exact solution method, new valid inequalities, and new lower bounds. The problem is NP-hard, and it arises in the context of bicycle-sharing systems that need to ensure quality of service. The latter is understood as the availability of bicycles and docks to park them in a network of stations. In this problem, each station presents a random request for the pickup or delivery of bicycles, which is disclosed immediately before the departure of the repositioning vehicles from the depot. The problem is framed as a variant of the stochastic vehicle routing problem, and we propose an implementation of the disaggregated integer L-shaped method to address it. To speed up the resolution, we create customized lower-bounding functionals based on a complexity result we developed for the recourse problem. The results of computational experiments show that our implementation is superior to those in the literature, which leads us to generate and propose a new, challenging benchmark set of instances.