Enhanced Energy Delivery in Electric Vehicle Charging Scheduling via Metaheuristic Approaches

Electric vehicle (EV) adoption is rapidly increasing, intensifying pressure on existing charging infrastructures and making the allocation of limited station capacity a critical scheduling problem. In the EV charging scheduling problem, heuristic and hybrid metaheuristic approaches aim to minimize non-delivered energy using discrete-time formulations where each vehicle-charger pair occupies an integer number of time slots. This modeling choice imposes an unavoidable lower bound on non-delivered energy when requested energies are misaligned with single time slot energy delivery, regardless of available infrastructure capacity. Consequently, physically feasible schedules satisfying all energy requests may exist for practically relevant instances, yet state-of-the-art methods using this formulation cannot construct such optimal schedules, distorting the assessment of smart-charging strategies. To remove this artifact, the paper introduces a refined mixed-integer linear programming (MILP) formulation that permits fractional use of the final charging slot for each vehicle-charger pair, eliminating discretization-induced energy losses while preserving a standard time-indexed structure. Given the NP-hardness of the underlying problem, three customized metaheuristics—Genetic Algorithm (GA), Grey Wolf Optimizer (GWO), and Cuckoo Search Algorithm (CSA)—are developed using a dedicated schedule encoding, a stochastic insertion heuristic for constructing and repairing feasible schedules, and perturbation and generalized crossover operators that maintain feasibility throughout the search. Extensive computational experiments on large-scale instances derived from the ACN-Data dataset and benchmark sets from the literature show that CSA consistently achieves the highest delivered-energy ratios, statistically outperforms GA and GWO, and improves average delivered energy by up to 89.45% over recent state-of-the-art methods without significant additional computational overhead.