Integrating Aggregated Electric Vehicle Flexibilities in Unit Commitment Models using Submodular Optimization
Hélène Arvis, Olivier Beaude, Nicolas Gast, Stéphane Gaubert, Bruno Gaujal · 2025
Read Integrating Aggregated Electric Vehicle Flexibilities in Unit Commitment Models using Submodular Optimization by Hélène Arvis, Olivier Beaude, Nicolas Gast, Stéphane Gaubert, Bruno Gaujal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-11191.txt.
Introduction
Hélène Arvis, Olivier Beaude, and their colleagues integrate electric vehicle flexibility into unit commitment, the scheduling problem that decides which power plants run to meet demand at lowest cost. Fleets of vehicles can shift charging to help the grid, but they are usually lumped together for tractability. That lumping can hide the true range of flexibility on offer.
Their method uses the structured shape of the lumped flexibility, a generalized polymatroid, to build an exact algorithm that mixes cutting planes with submodular optimization. Solving time grows near-linearly with the number of vehicle users under convex plant limits. A real long-term case joins European grid data with a French fleet survey.
Catalog record
| CREATOR | Hélène Arvis, Olivier Beaude, Nicolas Gast, Stéphane Gaubert, Bruno Gaujal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-11191
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Integrating Aggregated Electric Vehicle Flexibilities in Unit Commitment Models using Submodular Optimization Hélène Arvis, Olivier Beaude, Nicolas Gast, Stéphane Gaubert, Bruno Gaujal Abstract The UC ( UC ) problem consists in controlling a large fleet of heterogeneous electricity production units in order to minimize the total production cost while satisfying consumer demand. EV are used as a source of flexibility and are often aggregated for problem tractability. We develop a new approach to integrate EV flexibilities in the UC problem and exploit the generalized polymatroid structure of aggregated flexibilities of a large population of users to develop an exact optimization algorithm, combining a cutting-plane approach and submodular optimization. We show in particular that the UC can be solved exactly in a time which scales linearly, up to a logarithmic factor, in the number of EV users when each production unit is subject to convex constraints. We illustrate our approach by solving a real instance of a long-term UC problem, combining open-source data of the European grid (European Resource Adequacy Assessment project) and data originating from a survey of user behavior of the French EV fleet. I INTRODUCTION I-A Context As the installed capacity for renewable energy sources increases around the world, so does the need for flexibility of the electric power system to absorb their fluctuations. In particular, these flexibilities, including hydropower or EV ( EV ). must be correctly modeled in long-term optimization problems to evaluate their contribution to the system. UC ( UC ) problems are a focus of study in this context and consist in dispatching electricity to balance demand and production while respecting the constraints of large number of heteregeneous productions units, generally including nuclear power plants (subject to specific dynamic constraints), thermal plants, hydroelectric plants, and other renewable enery sources. The UC problem has been studied since the 1940s and progressively enriched by resolution techniques, as well as by the appearance of new production means, as demonstrated by the literature review of Abdou and Tkiouat [ 1 ] . We focus on the deterministic version of the UC , though it can also be studied in the context of uncertainties [ 31 ] . Typically, the UC is a very large MILP ( MILP ), modeling dispatch decisions over hundreds of time steps with thousands of power plants in a country. A common approach to solving these problems is through aggregation, i.e., replacing a group of similar units by a class representative in order to reduce problem size and compute solutions in reasonable time. The clustering of similar units has been explored by Meus et al. [ 20 ] , who demonstrate the benefits of aggregation in terms of tractability. However, aggregation generally leads to approximate solutions. In this paper, we consider the specific case of EV charging profiles, in particular the dispatch of power through smart charging by a centralized operator. The correct integration of EV in long-term, thus high-level, UC problems has an impact on realism of solutions. In France in 2035, there will be an estimated 15.6 million light-duty EV [ 29 ] ; if all vehicles charge simultaneously at 6kW, this amounts to a national demand of 93.6 GW. In comparison, the French installed production capacity is estimated to reach around 210GW (with 90GW of controllable means) in 2035 [ 30 ] , thus would be heavily impacted by uncoordinated charging. Hence, our goal is to integrate an accurate and tractable model of EV flexibilities in global UC formulations. Aggregating a large number of flexibilities boils down to computing, or approximating, the Minkowski sum of a large number of polytopes, where each summand represents the flexibility set of an individual user or group of similar users. This Minkowski sum generally has exponentially many inequalities; moreover, calculating the Minkowski sum of a family of polytopes defined by their facets is generally NP-hard [ 32 ] . Therefore, techniques must be explored to avoid an explicit computation of this Minkowski sum. The traditional, “direct”, aggregation method consists in summing the characteristics of individual users so as to have a ”super-user” that represents the whole population. This generally leads to an aggregation error. Special cases in which an exact and tractable aggregation is possible have been identified, by Beaude et al. [ 3 ] where each local constraint set has the structure of a (bipartite) network flow polytope, and recently by Mukhi et al. [ 24 ] , where each local constraint set is shown to have a generalized polymatroid structure. I-B Contribution We study a general UC model, including both power production units and a detailed model of EV flexibilities. This model captures charging constraint sets over a one week horizon, with multiple charging slots and specific energy consumption constraints (arising for instance from daily commuting). We leverage the generalized-polymatroid structure of the EV -component of the UC problem to develop an exact algorithm, combining a cutting-plane approach with submodular optimization. We show in particular that, when the constraint sets of the power plants are convex, the UC problem can be solved to optimality in a time which scales as N\log N , where N is the number of EV user profiles (see Corollary 6 ). We also present a practical cutting-plane algorithm ( Algorithm 1 ) and demonstrate its efficiency on a realistic case study, solving a long-term UC problem with European grid data (European Resource Adequacy Assessment project [ 10 ] ) and EV data taken from a survey of French driver behavior [ 21 ] . In particular, the algorithm scales well relative to the number of iterations and computed cutting planes. I-C Related work The specific case of EV aggregation has already been studied, though not always in the context of a large UC problem. A local use case is the resource allocation problem in which an aggregator must optimize a global cost under given EV constraints and a global power bound. Müller et al. [ 25 ] offered an alternative to direct aggregation with an inner approximation of the Minkowski sum relying on zonotopes, themselves stable by Minkowski sum. Jacquot et al. [ 16 , 3 ] studied a similar EV resource allocation problem with the additional constraint of preserving the privacy of individuals. To do so, they developped an exact aggregation method exploiting the combinatorial properties of the model (Hoffman cuts for bipartite network flows). More recently, the aggregated power allocation problem in the context of smart charging (no V2G ( V2G )) was found to have the structure of a generalized permutahedron by Mukhi and Abate [ 22 ] , ensuring an exact aggregation of EV constraint sets. Panda and Tindemans [ 27 ] derived a different approach on a more restrictive use case of homogeneous charging slots based on a concept of UL-flexiblity elaborated by the authors. This notion exploits the permutability of charging patterns to allow for stability by Minkowski sum, thus giving an efficient and scalable approximation. Mukhi et al. [ 24 ] observed that EV flexibility sets have the structure of generalized polymatroids, a fundamental class of polyhedra studied extensively by Frank and Tardos [ 11 ] . They are also special cases of the polyhedra associated to unimodular systems, studied in