Minimizing grid capacity in preemptive electric vehicle charging orchestration: Complexity, exact and heuristic approaches

Unlike refueling an internal combustion engine vehicle, charging electric vehicles is time-consuming and results in higher energy consumption. Hence, charging stations will face several challenges in providing high-quality charging services when the adoption of electric vehicles increases. These charging infrastructures must satisfy charging demands without overloading the power grid. In this work, we investigate the problem of scheduling the charging of electric vehicles to reduce the maximum peak power while satisfying all charging demands. We consider a charging station where the installed chargers deliver a preemptive constant charging power. These chargers can either be identical or non-identical. For both cases, we address two optimization problems. First, we study the problem of finding the minimum number of chargers needed to plug a set of electric vehicles giving different arrival and departure times and required energies. We prove that this problem belongs to the complexity class P, and we provide polynomial-time algorithms. Then, we study the problem of minimizing the power grid capacity. For identical chargers, we prove that the problem is polynomial, whereas it is NP-hard in the case of non-identical chargers. We formulate these problems as a mixed-integer linear programming model for both cases. To obtain near-optimal solutions for the NP-hard problem, we propose a heuristic and an iterated local search metaheuristic. Through computational results, we demonstrate the effectiveness of the proposed approaches in terms of reducing the grid capacity.