A time-space network flow approach to dynamic repositioning in bicycle sharing systems

•An integrated model is proposed to simultaneously consider the user dissatisfaction forecasting, bicycle repositioning and vehicle routing.•An efficient linearization method is proposed to transfer the non-linear model into an equivalent linear model.•A math-heuristic algorithm is proposed.

Faced with increasing population density, rising traffic congestion, and the resulting upsurge in carbon emissions, several urban metropolitan areas have instituted public bicycle sharing system as a viable alternative mode of transportation to complement existing long-distance bus- and metro- transit systems. A pressing issue that needs to be addressed in bike sharing systems is the accrued imbalance of bicycles between commuter demands and inventory levels at stations. To overcome this issue, a commonly employed strategy is to reposition bicycles during off-peak periods (typically at night) when no new user arrivals are expected. However, when such an imbalance occurs during day-time peak hours, such a passive strategy would result in lower resource utilization rates. To overcome this drawback, in this study, we propose a dynamic bicycle repositioning methodology that considers inventory level forecasting, user arrivals forecasting, bicycle repositioning, and vehicle routing in a unified manner. A multi-commodity time-space network flow model is presented, which results in an underlying complex nonlinear optimization problem. This problem is then reformulated into an equivalent mixed-integer problem using a model transformation approach and a novel heuristic algorithm is proposed to efficiently solve this model. Specifically, the first stage involves solving the linear relaxation of the MIP model, and a set covering problem is subsequently solved in the second stage to assign routes to the repositioning vehicles. The proposed methodology is evaluated using standard test-bed instances from the literature, and our numerical results reveal that the heuristic algorithm can achieve a significant reduction in rejected user requests when compared to existing methods, while yet expending only minimal computational effort.