This study examines the on-line proactive planning of relocations in a one-way station-based electric car-sharing system that implements a complete parking reservation policy. A Markovian model that utilizes reservation information is formulated in order to estimate the expected near-future shortages of vehicles and parking spots at each station. The outcome of the model is used in algorithms for staff-based and user-based relocations. The proposed algorithms are tested in a simulation environment using data derived from a real-world car-sharing system. In addition, in collaboration with a car-sharing operator, the algorithms are test in the field.