The vehicle relocation problem for the one-way electric vehicle sharing
This addresses operational efficiency for electric car-sharing operators by managing vehicle distribution and charging constraints, though it is incremental as it builds on existing relocation problems with new electric-specific features.
The paper tackles the vehicle relocation problem in one-way electric car-sharing systems, where personnel must move cars to balance vehicle and charging station availability, and presents a Mixed Integer Linear Programming formulation with valid inequalities that speeds up solution times using CPLEX on simulated Milan network instances.
Traditional car-sharing services are based on the two-way scheme, where the user picks up and returns the vehicle at the same parking station. Some services permits also one-way trips, which allows the user to return the vehicle in another station. The one-way scheme is quite more attractive for the users, but may pose a problem for the distribution of the vehicles, due to a possible unbalancing between the user demand and the availability of vehicles or free slots at the stations. Such a problem is more complicated in the case of electrical car sharing, where the travel range depends on the level of charge of the vehicles. The paper presents a new approach for the Electric Vehicle Relocation Problem, where cars are moved by personnel of the service operator to keep the system balanced. Such a problem generates a challenging pickup and delivery problem with new features that to the best of our knowledge never have been considered in the literature. We yield a Mixed Integer Linear Programming formulation and some valid inequalities to speed up its solution through a state-of-the art solver (CPLEX). We test our approach on verisimilar instances built on the Milan road network.