Pareto truck fleet sizing for bike relocation with stochastic demand: Risk-averse multi-stage approximate stochastic programming

Bike-sharing systems play an important role in the multimodal transit system. This study investigates the truck fleet sizing problem for bike relocation that integrates strategic and tactical decisions taking into account the stochastic nature of demand. We develop a multi-period bike relocation model at the tactical level and derive the bike shortage formulation coupling relocation decisions with midterm demand. Based on this thorough analysis, the objective of spatial fairness of bike shortage is explicitly measured. The problem is formulated as a multi-stage stochastic programming model to capture the demand uncertainty, in which bike relocation decisions relating to station inventory are integrated with decisions that determine the truck fleet size. We develop a data-driven multi-stage scenario tree generation approach that can incorporate midterm demand spatial and temporal dependence. To prevent the loss of information and mitigate the “curse of dimensionality”, we propose a novel “multi-stage approximate stochastic programming” by integrating the traditional multi-stage stochastic programming and Response Surface Methodology. A conditional value-at-risk criterion (CVaR) is introduced into each decision node to capture the service provider’s risk aversion and make more informed decisions (and thus the risk-hedging ability of the solution). To work with this nonconvex model, we develop a fast and effective hybrid metaheuristic algorithm. The modeling approach and algorithm are tested on a large-scale case in New York. Results show that there is a trade-off between total cost minimization and bike shortage equilibration. We also conduct extensive experiments to evaluate our stochastic model and discuss practical implications relative to the deterministic model.