Relating Electric Vehicle Charging to Speed Scaling with Job-Specific Speed Limits

• 成果类型: Article; Early Access
• 署名作者: Winschermann, Leoni; Antoniadis, Antonios; Gerards, Marco E. T.; Hoogsteen, Gerwin; Hurink, Johann
• 署名单位: University of Twente
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1044
• 发表日期: 2025

摘要

Because of the ongoing electrification of transport in combination with limited power grid capacities, efficient ways to schedule the charging of electric vehicles (EVs) are needed for the operation of, for example, large parking lots. Common approaches such as model predictive control repeatedly solve a corresponding offline problem. In this work, we first present and analyze the flow-based offline charging scheduler (FOCS), an offline algorithm to derive an optimal EV charging schedule for a fleet of EVs that minimizes an increasing and strictly convex function of the corresponding aggregated power profile. To this end, we relate EV charging to processor speed scaling models with job-specific speed limits. Experiments based on real-world EV charging data show that FOCS takes only 2.5 seconds to schedule 400 EVs in 15-minute granularity. Furthermore, we analyze the online algorithms Average Rate and Optimal Available and show that they are, respectively, 2 alpha-1 alpha alpha and alpha alpha competitive, where alpha is typically two in energy applications. Further numerical experiments show that, for the real-world EV charging use case, both algorithms achieve approximation ratios of less than 1.3. Furthermore, they significantly improve on the uncontrolled default often applied in practice.