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.