Free-floating is the new paradigm of car-sharing. These services enable one-way trips freely within a specified area, overcoming the need of a network of stations, that characterizes station-based services. Despite the increase of level of service for the users, free-floating poses a problem for the spatial distribution of the vehicles, due to a possible unbalance between the users-demand and the availability of vehicles. In such cases, the service provider has to develop strategies to reallocate the vehicles and restore an optimal distribution of the fleet of the car-sharing service. In case of free-floating services using electric-vehicles, the problem is even more complicated, due to the need of plug-in the vehicles to charging stations when needed. The paper presents a new model for vehicle relocation problem for an electric free-floating service, where cars are moved by operators of the service provider to keep the system balanced, generating a challenging pickup and delivery problem. The proposed algorithm has been designed and calibrated using real data from the city of Milan.