A disaggregated integer L-shaped method for the bike sharing rebalancing problem with stochastic demands
针对共享单车系统在随机需求下的再平衡问题，提出了一种离散整数L形方法，包括新公式、有效不等式和下限，实验表明该方法优于现有文献。
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. • We propose a new method for a bike sharing rebalancing problem. • The demand of bicycle at stations is considered stochastic. • We propose a new dynamic programming formulation to compute the recourse. • New valid inequalities and lower bounds are introduced. • Results show that our new approach is superior when compared with the literature.