We propose a service network design formulation to address the redistribution problem in station-based bike sharing systems. Due to spatial and temporal characteristics of user demand, e.g., commuting, such systems require bike redistribution among stations to ensure both bikes and free racks when and where required. Our formulation, which takes the form of a MILP, aims to produce a cost-efficient redistribution plan, which is defined in terms of services. A service is described by a vehicle movement between two stations, the number of transported bikes, and time interval. Such services are scheduled into master tours, which are regularly operated by load vehicles. For an adequate representation of redistribution decisions, a master tour does not only indicate a chronologically ordered sequence to visit stations, but also the necessary handling time to pick-up or deliver bikes at such stations.

In order to produce good-quality solutions for large instances, we propose an iterative solution method which combines hierarchical decomposition, metaheuristics, and exact optimization techniques. Each iteration of our decomposition scheme consists of 1) a dynamic transportation problem determining services to be operated, and 2) a single-commodity pick-up and delivery problem determining the schedule of such services into tours. The tours are stored in a pool, which is finally used to provide guidelines for efficiently exploring the search space of the original service network design problem. We demonstrate the efficacy of our solution methods with an extensive computational study on a new set of challenging instances.