Optimization of Electric Vehicle Charge Scheduling in Multiple Parking Lots: A Method Based on Metaheuristics and High Performance Computing

Abstract

The increase in global energy demand has led to the expansion, modernization, and digitization of power systems to incorporate new technologies like Electric Vehicles (EVs), which has created the potential for optimization of different aspects of the grid. The growing number of EVs requires system operators to balance the grid power supply against the electrical demand while reducing costs, which can be done through optimizing the charging schedule of EVs to manage their charging load. The EV charge scheduling optimization problem is complex and nondeterministic polynomial time-hard, generally involving a large amount of uncertainty in the variables and constraints. Because conventional mathematical and heuristic optimization techniques are not always appropriate for use with this problem, it may be considered a good candidate for use with metaheuristic optimization methods. Metaheuristics are a type of non-deterministic optimization algorithm, which have become a popular approach in EV optimization problems because they have been shown to provide improved performance with complex problems with many possible solutions and local optima, to escape local optima convergence, and to handle discrete variables. However, they require significant computational resources to compute the optimization for large problem sizes, and may not be calculated in an acceptable amount of time. Used in combination with a centralized optimization framework, they may produce more optimized results than decentralized models, but become unscalable with large power networks or number of EVs. The aim of this thesis is to develop a solution for the problem of centralized EV charge scheduling with multiple parking lots using metaheuristics, to prove that it will find a more optimized solution to the charge scheduling problem, compared to decentralized optimization. High Performance Computing (HPC) techniques are used to combat the high resource requirements and long simulation time associated with the problem size, to increase the scalability of the solution, and to complete the optimization in an acceptable real-time interval. A parallelized centralized optimization model using two-level particle swarm optimization is designed and validated against its sequential version and a decentralized model on a HPC cluster, where it provides more optimal solutions than the decentralized model, computes solutions for scenarios with up to 27 parking lots in less than 15 minutes, and provides average computation speedups of up to 139 times faster. This research contributes to the development of centralized optimization solutions to EV charge scheduling optimization problems for multiple parking lots, which may have previously been considered intractable.

L'augmentation de la demande mondiale d'énergie a conduit à l'expansion, à la modernisation et à la numérisation des systèmes électriques pour intégrer de nouvelles technologies telles que les véhicules électriques (VE), ce qui a permis d'optimiser les différents aspects du réseau. Le nombre croissant de VE oblige les opérateurs de système à équilibrer l’alimentation électrique du réseau par rapport à la demande électrique tout en réduisant les coûts, ce qui peut être fait en optimisant l'horaire de recharge des VE pour gérer leur taux de recharge. Le problème d’optimisation de la planification des charges des VE est complexe et non déterministe en temps polynomial, impliquant généralement une grande quantité d’incertitude dans les variables et les contraintes. Les techniques d'optimisation mathématiques et heuristiques conventionnelles ne sont pas toujours appropriées pour une utilisation avec ce problème, ce qui en fait un bon candidat pour une utilisation avec les méthodes d'optimisation métaheuristiques. Les métaheuristiques sont un type d'algorithme d'optimisation non déterministe, qui sont devenues des approches populaires dans les problèmes d'optimisation des VE, car il a été démontré qu'elles offrent des performances améliorées pour des problèmes complexes avec de nombreuses solutions possibles et optima locaux, permettant d'échapper à la convergence vers des optima locaux et permettant aussi de manipuler des variables discrètes. Cependant, elles nécessitent des ressources de calcul importantes pour l'optimisation de problèmes de grande taille et peuvent ne pas être calculées dans un délai acceptable. Utilisées en combinaison avec un cadre d'optimisation centralisé, elles peuvent produire des résultats plus optimisés que les modèles décentralisés, mais deviennent non évolutives avec de grands réseaux électriques ou un grand nombre de VE. L'objectif de cette thèse est de développer une solution au problème de planification centralisée de la recharge des VE avec plusieurs parcs de stationnement en utilisant des métaheuristiques, pour prouver que la méthode centralisée trouvera une solution plus optimisée au problème de planification de la recharge, par rapport à l'optimisation décentralisée. Les techniques de calcul haute performance (CHP) sont utilisées pour lutter contre les besoins élevés en ressources et le long temps de simulation associés à la taille du problème, pour augmenter l'évolutivité de la solution et pour terminer l'optimisation dans un intervalle en temps réel acceptable. Un modèle d'optimisation centralisé parallélisé utilisant l'optimisation par essaim de particules à deux niveaux est conçu et validé par rapport à sa version séquentielle et à un modèle décentralisé sur un cluster CHP. Ce modèle centralisé fournit des solutions plus optimales que le modèle décentralisé, calcule des solutions pour des scénarios avec jusqu'à 27 parcs de stationnement en moins de 15 minutes et offre des accélérations de calcul moyennes jusqu'à 139 fois plus rapides. Cette recherche contribue au développement de solutions d'optimisation centralisées pour résoudre les problèmes d'optimisation de la planification de la recharge des véhicules électriques pour plusieurs parcs de stationnement qui pouvaient auparavant être considérés comme insolubles.