Metaheuristics for solving a real-world electric vehicle charging scheduling problem

In this paper we consider a problem motivated by a real-world environment: scheduling the charging periods for a large set of electric vehicles, subject to a set of hard constraints, with the objective of minimizing the total tardiness. The set of constraints imposed by the charging station makes it difficult to obtain schedules that are both feasible and efficient. We consider both the static variant of the problem, where arrival time, charging time and due date of vehicles are known in advance, and also the dynamic variant. As the problem is NP-hard, metaheuristics are probably the best option to solve it. In fact, the state-of-the-art methods are a simple genetic algorithm (GA) and a method based on priority rules (EVS). In this paper we propose to design hybrid metaheuristics, motivated by the success of these hybridizations in solving a large number of scheduling problems. In particular we define a GRASP-like method and a memetic algorithm that use the Variable Neighborhood Search framework, both specifically designed for the problem at hand. Experimental results illustrate the potential of the proposed methods, reaching in some test-beds improvements larger than 12% with respect to EVS and GA. (c) 2018 Elsevier B.V. All rights reserved.