Lowering overhead costs and environmental impact in bike-sharing requires the efficient realization and optimization of a vehicle-based rebalancing strategy. The goal is to solve the total problem for a large city within one minute. For that, carefully chosen metaheuristics together with efficient numerical implementations have been developed. Initial solutions, stochastically produced by a Greedy method, are improved by an advanced Variable Neighborhood Search (VNS) algorithm together with a Large Neighborhood Search (LNS) metaheuristic. VNS is the efficient local search strategy, LNS better explores global solution space but is slower. For VNS, different neighborhood operators and operator change strategies are experimentally analyzed for real and large data sets of cities like Munich. Loading instructions obtained from exact maximum flow computations are derived for every set of intermediate candidate routes and are used as feasibility checks. Our two approaches (VNS+LNS and Parallel Variable Neighborhood Search (pVNS)) are benchmarked against (exact) Branch-and-Cut (B&C) methods and provide near-optimal solutions while vastly outperforming the exact method in terms of computational time, especially for large cities. Extensions to hybrid systems and a new windowing strategy modeling behavior of human experts are presented. They significantly improve real-world applicability and ease the work of bike-sharing systems (BS) operators.