Hybrid Heuristic for Multi-Depot Static Bike Rebalancing And Collection Problem

The bike rebalancing problem is one of the major operational challenges in the urban bike-sharing system which involves the redistribution of bikes to prevent stations from being empty or overloaded. This paper investigates a new bike rebalancing problem, which considers the collection of broken bikes in the multi-depot bike sharing system. An integer programming model is formulated to find the optimal vehicle assignment and visiting sequences with the minimum total working time and fixed cost of vehicles. A hybrid heuristic algorithm integrating Variable Neighbourhood Search and Dynamic Programming is proposed to solve the problem. The computational results show that the proposed method can find 26 best solutions out of 36 instances, while the CPLEX obtains 16 best solutions. Impact of broken bikes collection and distribution of depots is examined. Comparison of different practical strategies indicates that the number of vehicles required can be significantly reduced by allowing multiple visits to depots. Allowing vehicles to return to different depots can help reduce the total working time