An Exact Characterisation of Flexibility in Populations of Electric Vehicles

Increasing penetrations of electric vehicles (EVs) presents a large source of flexibility, which can be used to assist balancing the power grid. The flexibility of an individual EV can be quantified as a convex polytope and the flexibility of a population of EVs is the Minkowski sum of these polytopes. In general computing the exact Minkowski sum is intractable. However, exploiting symmetry in a restricted but significant case, enables an efficient computation of the aggregate flexibility. This results in a polytope with exponentially many vertices and facets with respect to the time horizon. We show how to use a lifting procedure to provide a representation of this polytope with a reduced number of facets, which makes optimising over more tractable. Finally, a disaggregation procedure that takes an aggregate signal and computes dispatch instructions for each EV in the population is presented. The complexity of the algorithms presented is independent of the size of the population and polynomial in the length of the time horizon. We evaluate this work against existing methods in the literature, and show how this method guarantees optimality with lower computational burden than existing methods.