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

I. Zaidi, A. Oulamara, L. Idoumghar and M. Basset

European Journal of Operational Research, 2024, vol. 312, issue 1, 22-37

Abstract: 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.

Keywords: Scheduling; Electric vehicle charging; Preemption; Complexity; Iterated local search (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723004241
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:312:y:2024:i:1:p:22-37

DOI: 10.1016/j.ejor.2023.05.039

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().