The relocation problem for the one-way electric vehicle sharing

Traditional car sharing services have been based on the two-way scheme, where the user picks up and returns the vehicle at the same parking station. Some innovative services permit also one-way trips, that is, the user is allowed to return the vehicle in another station. The one-way scheme is more attractive for the users, but may lead to an unbalance between the user demand, and the availability of vehicles or free lots at the stations. In such cases, the service provider could reallocate the fleet and restore a better distribution of the vehicles among the stations. In the case of electric car sharing, such a problem is more complex because the travel range depends on the level of the battery charge. This article presents a new approach for the relocation of electric vehicles (EVs), carried out by the staff of the service provider to keep the system balanced. Such an approach generates a challenging Paired Pickup and Delivery Problem with Time Windows with new features that to the best of our knowledge have never been considered in the literature. We call such a problem the EV relocation problem (EVRP). We yield a mixed integer linear programming (MILP) formulation of the EVRP and some techniques to speedup its solution through a state-of-the-art solver (CPLEX). Moreover, we develop a simple but effective heuristic based on such a formulation and four upper bound generation methods. We test the performances of both the MILP formulation and the heuristic on instances built on the Milan road network.