A time-space network flow approach to dynamic repositioning in bicycle sharing systems. (September 2017)

• Record Type: Journal Article
• Authors: Zhang, Dong; Yu, Chuhang; Desai, Jitamitra; Lau, H.Y.K.; Srivathsan, Sandeep
• Is Part Of: Transportation research. Volume 103(2017)
• Page Start: 188
• Page End: 207
• Publication Date: 2017-09
• Subjects: Bicycle sharing systems -- Time-space network flow model -- Dynamic repositioning -- Demand forecasting -- Convexification and linearization -- Heuristic algorithm; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2016.12.006
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: 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. Abstract: 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.