Real-time vehicle relocation and charging optimization for one-way electric carsharing systems

• Real-time vehicle relocation and charging strategy for carsharing services. • Demand dynamics and practical nonlinear charging profile are considered. • Column-generation-based solution method in a rolling time horizon is developed. • Existing columns are reused and column generation process is reactive. • Case study of a one-way carsharing company EVCARD. This study investigates a real-time vehicle relocation and charging strategy (RT-VR&CS) problem for the one-way electric carsharing services considering demand dynamics and practical nonlinear charging profile. The RT-VR&CS problem aims to develop a fast and robust algorithm to determine the real-time relocation and charging strategies for electric vehicles (EVs) with the goal of maximizing the profit of carsharing operators. A dynamic algorithmic framework based on a rolling time horizon is first established. Specifically, the entire planning horizon is divided into a series of sub-horizons, and a static vehicle relocation and charging strategy (S-VR&CS) problem is subsequently addressed over each sub-horizon in regard to the latest rental information known up to the beginning of the sub-horizon. For each static problem, we employ a set-packing-type formulation and a column-generation-based solution method. In particular, a multi-label method is developed to generate activity trajectories (i.e., columns) incorporating vehicle relocation and charging strategy for the first static problem, whereas the activity trajectories for the subsequent static problems are efficiently generated in an online environment by leveraging the existing activity trajectories generated for the previous static problem and employing a reactive column generation process. Numerical experiments on randomly generated instances and a case study based on a one-way carsharing company in China, i.e., EVCARD, are conducted to demonstrate the efficiency of the proposed solution method. The impacts of algorithm-related parameters, the demand dynamism, the service charge, and the relocation cost on the performance of one-way electric carsharing systems are also analyzed.