Difficulties in maintaining adequate numbers of bicycles and free docking spaces are a known issue in the operation of bicycle-sharing schemes. Empty and full stations in such systems are equally undesirable, since the former turn away potential users while the latter could not be used to terminate bicycle journeys. Repositioning practices have been used in the past to address this situation with partial success. This paper introduces a new approach for the optimization of such activities, addressing both routing and assignment aspects of bicycle repositioning using a fleet of carrier vehicles. A case study on bicycle usage patterns from a large bicycle-sharing scheme is carried out; examples are also provided that demonstrate the behavior of the algorithm. Implementation concerns and means to improve computational performance are also discussed.