Multi-objective electric vehicle charging scheduling under stochastic duration uncertainty

The ongoing electrification of the transport sector, driven by the numerous advantages of electric vehicles (EVs), introduces new challenges related to charging logistics, particularly due to long charging durations and uncertain conditions, posing significant negative impacts on grid stability and user satisfaction. While existing literature on EV charging scheduling often assumes deterministic charging durations, real-world conditions introduce randomness due to uncontrollable factors such as battery state-of-charge (SoC), fluctuating grid demand, and ambient temperature. In this paper, we address the Electric Vehicle Charging Scheduling Problem (EVCSP) under uncertain charging durations. First, we introduce a novel, flexible multi-objective scheduling model operating on a continuous time horizon, considering stochastic charging durations and incorporating controlled preemptions during charging, where the non-preemptive mode is a particular case. Then, we prove that finding a feasible assignment of EVs to chargers is strongly NP-hard under this uncertainty, even assuming identical chargers. Our model accounts for realistic constraints, including heterogeneous charger power levels and vehicle-charger compatibility, aiming to minimize the conditional expected values of grid overload and total tardiness, while also minimizing the undelivered energy to users. Given the problem’s computational complexity, we adapt four evolutionary algorithms (EAs), namely, extensions of the Non-Dominated Sorting Genetic Algorithm (NSGA), namely NSGA-II and NSGA-III, alongside other state-of-the-art multi-objective metaheuristics, including the Multi-Objective Cuckoo Search (MOCS) algorithm, and the Multi-Objective Grey Wolf Optimizer (MOGWO) by defining problem-specific operators to explore the search space and efficiently approximate the optimal Pareto front. Assuming lognormally distributed charging durations, we conducted a comparative experimental analysis on real-world data to evaluate the four methods and revealed that MOCS algorithm outperforms the other competitors. • Introduce the first multi-objective EV charging scheduling model under stochastic charging durations. • Prove that EV-to-charger assignment under uncertain charging durations is strongly NP-hard. • Derive explicit formulas for conditional expected total tardiness under multiple probability distributions. • Adapt four evolutionary algorithms with problem-specific operators for Pareto front approximation. • Demonstrate Multi-Objective Cuckoo Search (MOCS) algorithm superiority through comprehensive experiments on real-world ACN dataset.