P.: Balancing bicycle sharing systems: Improving a VNS by efficiently determining optimal loading operations

Abstract. Public bike sharing systems are important alternatives to motorized individual traffic and are gaining popularity in larger cities worldwide. In order to maintain user satisfaction, operators need to ac-tively rebalance the systems so that there are enough bikes available for rental as well as sufficient free slots for returning them at each station. This is done by a vehicle fleet that moves bikes among the stations. In a previous work we presented a variable neighborhood search metaheuris-tic for finding effective vehicle routes and three different auxiliary proce-dures to calculate loading operations for each candidate solution. For the most flexible auxiliary procedure based on LP, the current work provides a new, practically more efficient method for calculating proven optimal loading operations based on two maximum flow computations. The dif-ferent strategies for determining loading operations are further applied in combination controlled by an additional neighborhood structure. Exper-imental results indicate that this combined approach yields significantly better results than the original variable neighborhood search.