Bi-Objective Electric Vehicle Charging Scheduling with Stochastic Vehicle Arrivals

Electric vehicles present a sustainable alternative to conventional transportation due to their reduced environmental impact and enhanced energy efficiency. However, their prolonged charging times create significant operational hurdles, motivating the development of intelligent scheduling systems that optimize charging resources and improve operational efficiency. In this paper, we address the constrained multi-objective stochastic scheduling problem for EV charging operations, where vehicle arrivals are uncertain; specifically, clients may cancel their requests with a given probability. The objective is to minimize both the expected mean relative tardiness and the expected peak load, thereby addressing charging station stability and client satisfaction simultaneously. This approach offers a more realistic framework compared to existing state-of-the-art methods for this problem. We demonstrate that computing the expected peak load for a given schedule requires an exponential number of operations with respect to the problem size. Given this computational complexity, we adopt a Monte Carlo approximation approach and employ metaheuristic algorithms to approximate the optimal Pareto front using problem-specific operators designed to explore the solution space effectively. Specifically, we implement both versions of the Non-Dominated Sorting Genetic Algorithm (NSGA-II and NSGA-III) along with the Multi-Objective Cuckoo Search (MOCS) algorithm. We conduct numerical experiments comparing these metaheuristics in terms of hypervolume and execution time, demonstrating that the MOCS algorithm yields the best performance. Furthermore, we demonstrate that our stochastic model substantially outperforms its deterministic counterpart by explicitly accounting for demand uncertainty, resulting in more robust and operationally efficient EV charging schedules that better reflect real-world variability and establish the practical superiority of this work.