The presence of enough bicycles and free docking points to satisfy user demands in stations is a known operational issue in bicycle-sharing schemes. Empty and full stations in such systems are equally undesirable and disruptive for the operation of the network, 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 planning approach for 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 behaviour of the algorithm. Implementation concerns and means to improve computational performance are also discussed.