Adapting the ng-path relaxation for bike balancing problems

This paper deals with a static bike relocation problem that deploys a fleet of vehicles to redistribute shared bicycles. To solve the problem to optimality, we present a branch-price-and-cut algorithm. In particular, a new path relaxation for the pricing problem is introduced that relaxes the constraints on the maximum number of bikes to move at each station in a similar fashion as elementary can be relaxed in vehicle routing problems. Computational results show that our algorithm outperforms the former state-of-the-art.