Optimal Repositioning in Bike Sharing Systems

This thesis examines the static bicycle repositioning problem (SBRP) and the dynamic bicycle repositioning problem (DBRP) which deal with optimal re-balancing of bike sharing systems (BSSs) during the night and during the day, respectively. The DBRP is an extension of the SBRP where demand throughout the planning period is taken into account. Our analyses show that the demand depends on the location of the stations, the day of week, the time of day, and the weather. Articles and proceedings discussing the two problems are reviewed in an exhaustive literature survey. To our knowledge, a survey of this scope on the operational level literature has not previously been conducted. We present new and improved mathematical models for the two problems. These models make fewer simplifications than many existing models, e.g. they allow a heterogeneous fleet, multiple visits to each station, and non-perfect re-balancing. The DBRP-model stands out by giving complete routes and specific loading instructions, and by considering the timing of events. It does not however consider the stochasticity in demand. The models are thoroughly tested on a number of instances that are generated based on the BSS in Oslo, Norway. Testing of the SBRP-model shows that a strengthened MTZ-formulation yields the best results for eliminating subtours, that the symmetry breaking constraints handling visit sequence are effective, and that variable reduction is powerful as it removes symmetry around the depot. For the DBRP-model, the main results from the SBRP-model are applicable. Additionally, we show that the length of the planning horizon influences the routing decision and the value given to key input parameters. The models may serve as decision support together with cost-benefit analyses, for instance when deciding the number of service vehicles and their capacity. Increasing the fleet size and the vehicle capacity improve the objective value for both models. For the SBRP-model, more available time would further improve the solution. The computational effort needed to find the optimal solution is however shown to peak at a problem specific time limit for re-balancing. The computational effort depends on the number of stations considered and the maximum number of possible visits to each station. While the SBRP-model is solved to optimality within reasonable time for 15 stations, the DBRP-model is only solvable with up to eight stations, indicating that alternative solution methods should be considered. Six rules of thumb (ROTs) for the DBRP are developed, evaluated, and compared with the DBRP-model through simulations. For small instances, the DBRP-model proves effective, while a simple ROT considering the number of times a station fails in meeting customer demand and the driving time seems preferable for larger instances