A column generation heuristic for the dynamic bicycle rebalancing problem
针对公共自行车共享系统中防止站点空满的动态再平衡问题，提出一种列生成启发式算法，能在实时滚动时域内快速求解，基于奥斯陆真实数据测试表明计算时间适合实际运营，且显著优于当前规划方法。
Public bicycle sharing systems are becoming an essential part of the future urban mobility system. Real-time monitoring of the system state through sensors on bicycles and/or stations gives possibilities for advanced coordination of the system. In this paper, we consider the dynamic bicycle rebalancing problem, where bicycles are re-positioned by service vehicles to prevent stations from becoming completely full or empty, and so satisfying the demand for bicycles or locks. We solve the problem in a rolling horizon fashion with dynamic deterministic bicycle rebalancing subproblems (DDBRS) at the decision epochs. To solve the DDBRS within a few seconds in real-time, we propose a novel column generation heuristic (CGH). The CGH is tested within a simulation framework based on real data from the bicycle sharing system in Oslo. We show that the CGH is able to solve large real-life instances with computational times that are suitable for actual operation and that it provides significantly improved solutions compared with current planning practice. We also perform a number of tests to analyze the effect of changing the number of bicycles and locks in the system, as well as adding extra service vehicles. The case company is now making preparations to implement an optimization-based decision support system based on the CGH proposed in this paper.