Inventory rebalancing in bike-sharing systems

We address an optimization problem arising in rebalancing operations of inventory levels in bike-sharing systems. Such systems are public services where bikes are available for shared use on a short term basis. To ensure the availability of bikes in each station and avoid disservices, the bike inventory level of each station must met a forecast value. This is achieved through the use of a fleet of vehicles moving bikes between stations. Our problem can be classified as a Split Pickup and Split Delivery Vehicle Routing Problem. We propose a formulation in which routes are decomposed in smaller structures and we exploit properties on the structure of the optimal solutions, to design an exact algorithm based on branch-and-price.