Exactly solving the Split Pickup and Split Delivery Vehicle Routing Problem on a bike-sharing system

We propose an exact methodology to solve the Split Pickup and Split Delivery Vehicle Routing Problem arising in bike-sharing systems: a bike-sharing system is a public service in which bicycles are stored in rack stations and made available for shared use to individuals on a short term basis. However, during peak hours, flows along particular direction are registered, leading to high risk of empty racks in departure stations, and full racks at destination. One of the solutions chosen by many operators is to iteratively rebalance the system by means of a fleet of dedicated trucks: transportation demand is forecast, and bikes are picked up from stations where congestion is expected, and delivered to those expected to become empty. Due to the high costs of running trucks in a urban environment, efficient rebalancing operations are a key factor for the success of the whole system. We propose a branch-and-price based exact algorithm that exploits the decomposition of vehicles routes into substructures in order to reduce the complexity of the pricing problem. We prove that our methodology can solve small instances of the problem faster than competitors