Joint Scheduling and Optimal Charging of Electric Vehicles Problem

In this paper, we consider the joint scheduling and optimal charging of electric vehicles problem. This problem can be defined as follows: Given a fleet of Electric Vehicles - EV and Combustion Engine Vehicles - CV, a set of tours to be processed by vehicles and a charging infrastructure, the problem aims to optimize the assignment of vehicles to tours and to minimize the charging cost of EVs while considering several operational constraints mainly related to chargers, electricity grid, and EVs driving range. We prove the NP-hardness in the ordinary sense of this problem. We provide a mixed-integer linear programming formulation to model the joint Scheduling and Optimal Charging of EVs problem (EVSCP) and we use CPLEX to solve small and medium instances. A two-phase sequential heuristic, based on the Maximum Weight Clique Problem (MWCP) and the Minimum Cost Flow Problem (MCFP), is developed to solve large instances of the EVSCP. Computational results on a large set of real and randomly generated test instances show the efficiency and the effectiveness of the proposed approaches.