Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches

Abstract

This paper deals with the Electric Vehicle (EV) Scheduling and Optimal Charging Problem. More precisely, given a fleet of EVs and Combustion Engine Vehicles (CVs), a set of tours to be processed by vehicles and a charging infrastructure, the problem aims to optimise the assignment of vehicles to tours and minimise the charging cost of EVs while considering several operational constraints mainly related to chargers, electricity grid and EVs driving range. We prove that the Electric Vehicle Scheduling and Charging Problem (EVSCP) is NP-hard in the ordinary sense. We provide a mixed-integer linear programming formulation to model the EVSCP and use CPLEX to solve small and medium instances. To solve large instances, we propose two heuristics: a Sequential Heuristic (SH) and a Global Heuristic (GH). The SH considers the EVs sequentially. To each EV, it assigns a set of tours and guarantees the feasibility of a charging schedule. Then, it generates an optimal charging schedule for this EV. However, the GH computes, in the first step, a feasible assignment of tours to all EVs. In the second step, it applies a global Min-Cost-Flow-based charging algorithm to minimise the charging cost of the EVs fleet. To evaluate the efficiency of our solving approaches, computational results on a large set of real and randomly generated test instances are reported and compared.