A 3-step math heuristic for the static repositioning problem in bike-sharing systems

Over the last few years, bike-sharing systems have emerged as a new mode of transportation in a large number of big cities worldwide. This new type of mobility mode is still developing, and many challenges associated with its operation are not well addressed yet. One such major challenge of bike-sharing systems is the need to respond to fluctuating demands for bicycles and for vacant lockers at each station, which directly influences the service level provided to its users. This is done using dedicated repositioning vehicles (light trucks) that are routed through the stations, loading and unloading bicycles to/from them. Performing this operation during the night when the demand in the system is negligible is referred to as the static repositioning problem. In this paper, we propose a 3-step mathematical programming based heuristic for the static repositioning problem. In the first step, stations are clustered according to geographic as well as inventory (of bicycles) considerations. In the second step the repositioning vehicles are routed through the clusters while tentative inventory decisions are made for each individual station. Finally, the original repositioning problem is solved with the restriction that traversal of the repositioning vehicles is allowed only between stations that belong to consecutive clusters according to the routes determined in the previous step, or between stations of the same cluster. In the first step the clusters are formed using a specialized saving heuristic. The last two steps are formulated as Mixed Integer Linear Programs and solved by a commercial solver. The method was tested on instances of up to 200 stations and three repositioning vehicles, and was shown to outperform a previous method suggested in the literature for the same problem.