Surrogate DC Microgrid Models for Optimization of Charging Electric Vehicles under Partial Observability

Abstract

Many electric vehicles (EVs) are using today’s distribution grids, and their flexibility can be highly beneficial for the grid operators. This flexibility can be best exploited by DC power networks, as they allow charging and discharging without extra power electronics and transformation losses. From the grid control perspective, algorithms for planning EV charging are necessary. This paper studies the problem of EV charging planning under limited grid capacity and extends it to the partially observable case. We demonstrate how limited information about the EV locations in a grid may disrupt the operation planning in DC grids with tight constraints. We introduce two methods to change the grid topology such that partial observability of the EV locations is resolved. The suggested models are evaluated on the IEEE 16 bus system and multiple randomly generated grids with varying capacities. The experiments show that these methods efficiently solve the partially observable EV charging planning problem and offer a trade-off between computational time and performance.

1. Introduction

The increasing penetration of electric vehicles (EVs) and renewable energy sources (RES) into distribution grids provides new opportunities, but also poses new challenges for the system operators. As EVs and some of the RES inherently use DC, they can be integrated into DC grids without additional converters and with smaller power losses [1]. For this reason, DC in distribution grids is considered to be a suitable alternative to the currently used AC [2]. Unlike conventional loads, EVs are flexible in terms of when their demand should be served. This flexibility is provided by a special entity, the EV aggregator [3], which coordinates the charging of EVs. The goal of the aggregator is to solve the EV charging planning (EVCP) problem, i.e., to minimize the sum of unmet demand and operation costs, while not violating the physical constraints of the grid.

In practice, there are two main challenges related to solving the EVCP problem. First, information about the EV parameters (e.g., arrival and departure times, demand and locations in the grid) and/or the grid state (topology, physical properties of the nodes or lines) may not be fully available to the EV aggregator. Hence, the aggregator might have to operate using incomplete information. Second, as the relation between current and voltage is hyperbolic, the power flow equation makes the EVCP problem non-convex [4]. That means not only that there is no theoretical guarantee of obtaining the globally optimal solution, but also that the problem may become computationally intractable for large grids and long planning horizons.

A popular perspective on the EVCP problem is to simplify or even omit the power flow equations and grid constraints, in order to make the problem tractable. Various studies have pursued this approach and focused on dealing with the uncertainty of the future EV arrivals. Sadeghianpourhamami et al. [5] applied a reinforcement learning algorithm to coordinate the EV charging in a constraint-free grid. In [6], the authors minimized the problem’s Lagrangian in a decentralized fashion to optimize the charging of the EVs located in a single building with stochastic wind power supply. Wu and Sioshansi [7] designed a two-stage optimization algorithm with a sample-average approximation technique to solve the EVCP problem using a linearization of the AC power flow. On the other hand, some studies have combined the EVCP with the non-convex optimal power flow (OPF) problem and included the exact power flow equations and grid constraints in it. Kayacık et al. [8] formulated the EVCP problem as a multi-timestep OPF problem extended with additional constraints on the CO₂ emissions and derived a convex second-order cone programming relaxation that can be solved efficiently. In [9], a fuzzy-logic controller was developed to minimize power costs and emissions simultaneously. Chen et al. [10] solved the EVCP+OPF problem by decoupling the OPF part from the planning and using the convex dual problem for it. However, no studies have included both incomplete information or EV uncertainties and power flow equations in the EVCP problem.

While the uncertainty of the EV parameters and non-convexity of the OPF are usually considered separately in the existing literature, in reality the EV aggregator should solve both problems simultaneously. The direct combination of the existing solutions for these problems does not seem possible: two-stage optimization of a non-convex problem easily becomes intractable. On the other hand, model-free methods, such as reinforcement learning, are generally hard to apply to constraint optimization problems. Moreover, if the present, rather than the future, is not fully known (e.g., due to privacy concerns), the standard EVCP formulation becomes irrelevant, and further research is required to formulate and solve the partially observable version of the problem.

An important input group of parameters for the EVCP problem is the locations of the EVs in the grid, as they are necessary to compute the power flow required for charging. This study investigates the EVCP with partial observability of the EV locations. The problem is reformulated to account for partial observability, and we investigate how it affects the EV aggregator by answering the following questions:

• How crucial is it for the EV aggregator to know exact locations of the EVs in the grid?
• How can one obtain a well-performing, scalable solution when the EV locations are known only up to certain degree?

In order to answer the first question, we conducted experiments on DC grids with various topologies and capacities to evaluate how different degrees of awareness about EV locations affect the planning. The experimental results demonstrate that a lack of information about the locations of the EVs currently present in the grid considerably disrupts the performance, whereas locations of the EVs that are yet to arrive are much less vital. To deal with this issue, this paper introduces two alternatives for modeling the grid topology without knowing the exact locations of the EVs. Experiments on both real and randomly generated grids show that the suggested models perform better than a naive baseline and offer a trade-off between computational cost and performance.

2. Background

2.1. EVCP Problem Formulation

Existing studies consider various formulations of the EVCP problem depending on the optimization objective, EV charging approach, and optimization approach [3]. This study adopts the perspective of an EV aggregator that represents the combined interest of all the EVs in a grid. Its goal is to maximize the social welfare—the sum of the demand provided to the EVs—with minimal operation costs. Following [10,11], EV charging optimization is combined with power flow equations and grid constraints. Unlike most existing studies, this work does not assume that all vehicles can be charged fully. To account for that, all EVs have a linear utility function quantifying how much value each car assigns to being charged for one Watt Hour.

Advances in power electronics allow for new solutions in the microgrid design. Various aspects of DC microgrids’ control, protection, and energy management are being studied in the literature (e.g., see [12] for an overview). As this paper aims at solving the charging planning problem with partial observability, we employ the relatively simple DC microgrid model suggested in [13]. For the same reason, this work does not consider the properties of the EV batteries, as they does not affect the charging planning algorithm. This study considers DC microgrids that consist of multiple EV charging stations and one or several generators that can represent connections to an external power grid or distributed generators (DGs). Prior to defining the optimization problem for the EVCP in DC grids, we introduce the necessary notation.

The set $\mathcal{N}=\mathcal{L}\bigsqcup \mathcal{G}$ of nodes in the grid (the squared cup symbol ⊔ is the disjoint union operator) is a disjoint union of the loads $\mathcal{L}$ and generators $\mathcal{G}.$ For convenience, we use n and m as subscripts when we mean an arbitrary node and use subscripts l and g to highlight the difference between the loads and generators. The set of lines $\mathcal{E}\subset \mathcal{N}\times \mathcal{N}$ contains the node pairs $(n,m)$ that are connected by a line. The set $\{t_0,t_1,\dots ,t_T\}$ is the set of planning timesteps, each timestep having a constant length, being defined as $\mathrm{\Delta }t:=t_{s+1}-t_s,\forall s\in \{0,\dots ,T-1\}.$ At each timestep $t,$ voltage and power in the loads l and generators g are denoted by $v_l^t,p_l^t$ and $v_g^t,p_g^t$ correspondingly. Line current and conductance between nodes n and m are denoted by $i_{nm}^t$ and $y_{nm}$, respectively. For each generator $g\in \mathcal{G}$, we define energy supply costs as a linear function of the generator’s power with coefficient $c_g^t$. We use a convention that power at the generators is negative and power at the loads is positive. The bounds for the voltages, power, and currents are denoted by ${\overline{V}}_n,{\underset{¯}{V}}_n,{\overline{P}}_n,{\underset{¯}{P}}_n,{\overline{I}}_{nm}.$ The set of the electric vehicles is denoted by $\mathcal{K},$ and each EV $k\in \mathcal{K}$ has several parameters. Let $t_k^{arr},t_k^{dep}$ be the arrival and departure times, ${\overline{E}}_k$ be the desired state-of-charge (SOC) at departure, and $u_k$ be the coefficient of the linear utility function specifying the priority of the particular EV. SOC at timestep t is denoted by $e_k^t.$ For simplicity, we use $l\left(k\right)$ to denote the load where EV k is being charged and $k\left(l\right)$ for the EV at load $l.$

First, the power flow constraints are defined as follows:

$${\underset{¯}{V}}_l\le v_l^t\le {\overline{V}}_l,{\underset{¯}{P}}_l\le p_l^t\le {\overline{P}}_l,\forall l\in \mathcal{L}$$

(1a)

$${\underset{¯}{V}}_g\le v_g^t\le {\overline{V}}_g,{\underset{¯}{P}}_g\le p_g^t\le {\overline{P}}_g,\forall g\in \mathcal{G}$$

(1b)

$$-{\overline{I}}_{nm}\le i_{nm}^t\le {\overline{I}}_{nm},\forall (n,m)\in \mathcal{E}$$

(1c)

$$i_{nm}^t=(v_n^t-v_m^t)y_{nm},\forall (n,m)\in \mathcal{E}$$

(1d)

$$p_n^t=-v_n^t\sum _{\left\{m\right|(n,m)\in \mathcal{E}\}}{y}_{nm}(v_n^t-v_m^t),\forall n\in \mathcal{N}$$

(1e)

Then, the EV state-of-charge is subject to the following constraints:

$$e_k^{t_k^{arr}}=0,\forall k\in \mathcal{K}$$

(2a)

$$0\le e_k^t\le {\overline{E}}_k,\forall k\in \mathcal{K},\forall t\in [t_k^{arr},t_k^{dep}]$$

(2b)

$$e_k^{t+1}=e_k^t+\mathrm{\Delta }t{p}_{l\left(k\right)}^t,\forall k\in \mathcal{K},\forall t\in [t_k^{arr},t_k^{dep})$$

(2c)

The optimization objective of the EVCP problem is defined as

$$J\left(p\right)=\sum _t\left(\sum _{l\in \mathcal{L}}{u}_{k\left(l\right)}{p}_l^t\mathrm{\Delta }t+\sum _{g\in \mathcal{G}}{c}_g^t{p}_g^t\mathrm{\Delta }t\right).$$

(3)

We call J the social welfare as it combines the fulfilled demand weighted by the EV utility coefficients and the negative of the operation costs. The coefficients $c_g^t$ can represent the generation costs or price for buying power from the external grid. The utility coefficients $u_k$ are defined per EV and represent the importance of each vehicle. It is worth mentioning that it is possible to define the utility coefficients per load rather than per EV. In that case, it can be used to model the pricing tariff in the grid. However, the problem will not change mathematically, and hence we do not deliberately study this case. The constraints (1a–e) and (2a–c) and the objective (3) define the EVCP problem:

$$\begin{array}{cccc}\hfill \underset{v,i,p,e}{max}& \hfill J\left(p\right)& \hfill & \\ \hfill \mathrm{subject}\mathrm{to}:& \hfill \left(1\mathrm{a})-(1\mathrm{e}\right)& \hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left(\mathrm{Exact}\mathrm{EVCP}\right)\\ \hfill & \hfill \left(2\mathrm{a}\right)-\left(2\mathrm{c}\right)& \hfill \end{array}$$

2.2. SOCP Relaxation

Due to the Equation (1e), the OPF problem and hence the EVCP problem are non-convex. Several methods to convexify the OPF problem are suggested in the literature, including semi-definite programming (SDP) [4] and second-order convex programming (SOCP) [13] formulations. As the latter has been shown to perform optimally in multiple real DC grids [13], we adapt it to the EVCP problem. The SOCP relaxation can be obtained by the following change of variables:

$$\left\{\begin{array}{cc}{\widehat{v}}_n^t\hfill & ={\left(v_n^t\right)}^2\hfill \\ p_{nm}^t\hfill & =({\left(v_n^t\right)}^2-v_n^t{v}_m^t)y_{nm}\hfill \\ l_{nm}^t\hfill & =y_{nm}^2{(v_n^t-v_m^t)}^2\hfill \end{array}\right.$$

The constraints (1a–e) can be relaxed to the following quadratic cone constraints:

$${\underset{¯}{V}}_l^2\le {\widehat{v}}_l^t\le {\overline{V}}_l^2,{\underset{¯}{P}}_l\le p_l^t\le {\overline{P}}_l,\forall l\in \mathcal{L}$$

(4a)

$${\underset{¯}{V}}_g^2\le {\widehat{v}}_g^t\le {\overline{V}}_g^2,{\underset{¯}{P}}_g\le p_g^t\le {\overline{P}}_g,\forall g\in \mathcal{G}$$

(4b)

$$-{\overline{I}}_{mn}^2\le l_{mn}^t\le {\overline{I}}_{mn}^2,\forall (m,n)\in \mathcal{E}$$

(4c)

$$\frac{l_{nm}^t}{y_{nm}}=p_{nm}^t+p_{mn}^t,\forall (n,m)\in \mathcal{E}$$

(4d)

$$y_{nm}({\widehat{v}}_n^t-{\widehat{v}}_m^t)=p_{nm}^t-p_{mn}^t,\forall (n,m)\in \mathcal{E}$$

(4e)

$$p_n^t=\sum _{\left\{m\right|(n,m)\in \mathcal{E}\}}{p}_{nm}^t,\forall n\in \mathcal{N}$$

(4f)

$$l_{nm}^t{\widehat{v}}_n^t\ge {\left(p_{nm}^t\right)}^2,\forall (n,m)\in \mathcal{E}$$

(4g)

Then, the SOCP relaxation of the EVCP problem is the following optimization problem:

$$\begin{array}{ccc}\hfill \underset{\widehat{v},l,p,e}{max}& \hfill J\left(p\right)& \hfill \\ \hfill \mathrm{subject}\mathrm{to}:& \hfill \left(4\mathrm{a}\right)-\left(4\mathrm{g}\right)& \hfill \left(\mathrm{Relaxed}\mathrm{EVCP}\right)\\ \hfill & \hfill \left(2\mathrm{a}\right)-\left(2\mathrm{c}\right)& \hfill \end{array}$$

2.3. Including Uncertainties

If the full information about the EVs and the grid is available to the EV aggregator, then the only challenge for solving the exact EVCP problem is its non-convexity. As discussed in the previous section, convex relaxation techniques such as SDP or SOCP are demonstrated to be effective solutions for that. In practice, however, the information that the aggregator has access to might be limited. For example, due to causality, parameters of an EV usually become known only after it arrives in the grid, hence making the EVCP a stochastic optimization problem. Moreover, if RES [6] or inelastic loads [10] are included in the problem, their generation and demand are usually also modeled as random variables. A common approach to solving the EVCP problem with uncertainties is online planning, where the problem is repeatedly solved at each timestep.

An important feature of online planning is that it allows one to obtain a feasible solution of the EVCP problem even in the presence of future uncertainties. However, a conceptually different example emerges when the state of the grid is only partially observable. For example, changes in the grid topology, variations in nodal and line limits, or locations of the EVs in the grid might be reported to the aggregator with a delay. In this case, the EVCP problem cannot be formulated in the standard way, because its constraints are unknown. Furthermore, as the solution is not guaranteed to be feasible, the objective value cannot be used to evaluate the solution’s quality. The next section presents a way to define the EVCP problem with partial observability and introduce an evaluation framework that can be used with it.

3. Partially Observable EVCP

In a partially observable EVCP (PO-EVCP) problem, the EV aggregator may be unaware of some input parameters of the EVCP problem. This study considers the case when the locations of the EVs in the grid are only partially known. Specifically, the loads in a distribution grid are divided in several regions, which are referred to in this paper as cables. For example, the cables can correspond to charging stations at different streets or EV parking lots. Then, the EV aggregator only knows at which cables EVs are parked. In practice, that can be relevant due to the privacy concerns or limited communication between the EV aggregator and the grid operator.

First, let $\mathcal{C}$ be the set of cables, where a single cable $c\in \mathcal{C}$ contains several loads $c\subset \mathcal{L}.$ Every load in the grid belongs to one cable, i.e., $\mathcal{L}={⨆}_{c\in \mathcal{C}}c.$ For simplicity, the cable corresponding to load l is denoted by $c\left(l\right).$ The EV aggregator only knows the cable where an EV is parked, $c\left(k\right),$ but the particular load $l\left(k\right)$ is a random variable. Its distribution can be obtained by the following process: initially, all loads in the grid are unoccupied. Then, for each timestep $t\in \{t_0,\dots ,t_T\},$ if an EV k arrives in the grid, its location $l\left(k\right)$ is sampled uniformly from the unoccupied nodes in the cable $c\left(k\right).$ The sampled load $l\left(k\right)$ becomes occupied until the EV departs.

In the PO-EVCP problem, the feasibility region defined by (1a–e) and (2a–c) is stochastic. The remainder of this section introduces three approximate approaches to resolving the partial observability of the problem.

3.1. Blind Guessing Model

The simplest way to derive a deterministic approximation for the PO-EVCP problem is to sample the positions of incoming EV uniformly from the unoccupied loads. Note that the sampled and the actual positions will rarely coincide. Let $\overrightarrow{l}$ and $\overrightarrow{k}$ be vectors of the loads and EVs, respectively, and let $\overrightarrow{l}(\overrightarrow{k})$ be the true unknown assignment of grid loads to EVs. Blind guessing is defined as this random sampling of an assignment ${\overrightarrow{l}}^{\prime }(\overrightarrow{k})$, and we denote the resulting EV-to-load and load-to-EV maps as $l^{\prime }\left(k\right)$ and $k^{\prime }\left(l\right)$, respectively. In the EVCP problem, only constraint (2c) and objective (3) depend on ${\overrightarrow{l}}^{\prime }(\overrightarrow{k}).$ Hence, they can be rewritten as follows:

$$e_k^{t+1}=e_k^t+\mathrm{\Delta }t{p}_{l^{\prime }\left(k\right)}^t,k\in \mathcal{K},t\in [t_k^{arr},t_k^{dep})$$

(5)

$$\widehat{J}\left(p\right)=\sum _t[\sum _{l\in \mathcal{L}}{u}_{k^{\prime }\left(l\right)}{p}_l^t+\sum _{g\in \mathcal{G}}{c}_g^t{p}_g^t].$$

Then, the PO-EVCP problem with blind guessing can be defined:

$$\begin{array}{ccc}\hfill \underset{v,i,p,e}{max}& \hfill \widehat{J}\left(p\right)& \hfill \\ \hfill \mathrm{subject}\mathrm{to}:& \hfill \left(1\mathrm{a}\right)-\left(1\mathrm{e}\right)& \hfill (\mathrm{Guessing}\mathrm{PO}-\mathrm{EVCP})\\ \hfill & \hfill \left(2\mathrm{a}\right),\left(2\mathrm{b}\right),\left(5\right)& \hfill \end{array}$$

Essentially, the blind guessing model resolves the uncertainty in the PO-EVCP problem by randomly assuming where EVs are parked within the corresponding cable. Then, the problem is reduced to the standard exact EVCP problem, defined in Section 2.1.

3.2. Surrogate Grid Models

As an alternative to blindly guessing the EV assignments, it is possible to instead modify the grid topology used in the optimization problem. The goal is to derive a surrogate grid with such topology that the optimization problem becomes independent of the non-observable information. In other words, such surrogate grid should be invariant over different EV assignments, as it effectively makes the problem deterministic. This section presents two different surrogate grid models with this property. Before defining these models, some additional notation is introduced. For each pair of nodes $m,n\in \mathcal{N},$ let

$$p(m,n)=\{(m,n_1),(n_1,n_2),\dots ,(n_u,n)\}$$

denote a path from m to n. The path conductance $y_p$ is defined by the equation

$$1/y_p=\sum _{(i,j)\in p(m,n)}1/y_{ij}.$$

Then, let $p^{*}$ be the path from m to n with the highest conductance. The conductance of this path is denoted by $y_{mn}^{path}$ and its current limit by

$${\overline{I}}_{mn}^{path}:=\underset{(n_i,n_j)\in p^{*}}{min}{\overline{I}}_{n_i{n}_j}$$

The conductance between a cable $c\in \mathcal{C}$ and an external node $m\notin c$ is defined as the average conductance over the paths from m to loads in $c:$

$$y_{mc}^{path}:=\frac{1}{\left|c\right|}\sum _{n\in c}{y}_{mn}^{path}.$$

The current limit between c and m is defined as

$${\overline{I}}_{mc}^{path}:=\underset{n\in c}{min}{\overline{I}}_{mn}^{path}.$$

Parallel nodes model. The parallel nodes model transforms each cable c into a set of nodes connected in parallel. To derive the parallel nodes surrogate grid, all lines that connect nodes within c are removed. For each connection $(m,n)$ from an external node $m\notin c$ to $n\in c,$ a new node $\widehat{n}$ is added and connected to m with ${\overline{I}}_{m\widehat{n}}={\overline{I}}_{mn}$ and $y_{mn}=\infty .$ Then, node $\widehat{n}$ is connected to all loads in the cable $n_i\in c$ with new lines, such that ${\overline{I}}_{\widehat{n}{n}_i}={\overline{I}}_{mn}$ and $y_{\widehat{n}{n}_i}=y_{m{n}_i}^{path}.$ The new node $\widehat{n}$ is passive; i.e., ${\underset{¯}{P}}_{\widehat{n}}={\overline{P}}_{\widehat{n}}=0.$ The parallel nodes’ surrogate grid is illustrated in Figure 1.

Let ${\mathcal{N}}_{par}={\mathcal{L}}_{par}\bigsqcup {\mathcal{G}}_{par}$ and ${\mathcal{E}}_{par}$ be the sets of nodes and lines in the parallel nodes surrogate grid. Then, the optimization problem for the parallel nodes models is the same as the exact EVCP problem with ${\mathcal{N}}_{par},{\mathcal{E}}_{par}:$

$$\begin{array}{ccc}\hfill \underset{v,i,p,e}{max}& \hfill \sum _t\left(\sum _{l\in {\mathcal{L}}_{par}}{u}_{k\left(l\right)}{p}_l^t\mathrm{\Delta }t+\sum _{g\in {\mathcal{G}}_{par}}{c}_g^t{p}_g^t\mathrm{\Delta }t\right)& \hfill \\ \hfill \mathrm{subject}\mathrm{to}:& \hfill \left(1\mathrm{a}\right)–\left(1\mathrm{e}\right)\mathrm{for}{\mathcal{N}}_{par},{\mathcal{E}}_{par}& \hfill (\mathrm{Parallel}\mathrm{PO}-\mathrm{EVCP})\\ \hfill & \hfill \left(2\mathrm{a}\right)–\left(2\mathrm{c}\right)& \hfill \end{array}$$

It is crucial that, due to the topology of the parallel nodes surrogate grid, the optimization problem is equivalent for all values of $l\left(k\right)$ and hence the partial observability is resolved.

Single node model. The single node model transforms each cable c into a single node $n_c.$ For each neighbouring node $m\notin c,$ such that $\exists i\in c,(m,i)\in \mathcal{E},$ a line $(m,n_c)$ is added. Its parameters are defined as ${\overline{I}}_{m{n}_c}={\overline{I}}_{mc}^{path}$ and $y_{m{n}_c}=y_{mc}^{path}.$ The power bounds for $n_c$ are defined as the sum over original nodes: ${\overline{P}}_{n_c}={\sum }_{n\in c}{\overline{P}}_n,$${\underset{¯}{P}}_{n_c}={\sum }_{n\in c}{\underset{¯}{P}}_n.$ Voltage bounds are defined as the average: ${\overline{V}}_{n_c}=\frac{1}{\left|c\right|}{\sum }_{n\in c}{\overline{V}}_n,$${\underset{¯}{V}}_{n_c}=\frac{1}{\left|c\right|}{\sum }_{n\in c}{\underset{¯}{V}}_n.$ The parallel nodes’ surrogate grid is illustrated in Figure 2.

In the single node surrogate model, all nodes from a cable c are mapped to new node $n_c.$ Hence, there are multiple EVs charging at $n_c.$ Prior to defining the optimization problem, new notation is introduced. Let $p_k^t$ be the power provided to EV k at timestep $t.$ Then, there are the following constraints on $p_k^t$ and EVs’ SOC.

$$e_k^{t+1}=e_k^t+\mathrm{\Delta }t{p}_k^t,\forall k\in \mathcal{K},\forall t\in [t_k^{arr},t_k^{dep})$$

(6)

$$p_k^t=0,\forall k\in \mathcal{K},\forall t\notin [t_k^{arr},t_k^{dep})$$

(7)

$$\sum _{k\in \{k\in \mathcal{K}|c\left(k\right)=c\}}{p}_k^t=p_{n_c}^t,\forall c\in \mathcal{C},\forall t\in [t_k^{arr},t_k^{dep})$$

(8)

Let ${\mathcal{N}}_{sng}={\mathcal{L}}_{sng}\bigsqcup {\mathcal{G}}_{sng}$ and ${\mathcal{E}}_{sng}$ be the sets of nodes and lines in the single node surrogate grid. Then, the optimization problem for the single node model is defined as follows:

$$\begin{array}{ccc}\hfill \underset{v,i,p,e}{max}& \hfill \sum _t\left(\sum _{l\in {\mathcal{L}}_{sng}}{u}_{k\left(l\right)}{p}_l^t\mathrm{\Delta }t+\sum _{g\in {\mathcal{G}}_{sng}}{c}_g^t{p}_g^t\mathrm{\Delta }t\right)& \hfill \\ \hfill \mathrm{subject}\mathrm{to}:& \hfill \left(1\mathrm{a}\right)–\left(1\mathrm{e}\right)\mathrm{for}{\mathcal{N}}_{par},& \hfill (\mathrm{Single}\mathrm{PO}-\mathrm{EVCP})\\ \hfill & \hfill \left(2\mathrm{a}\right),\left(2\mathrm{b}\right),\left(6\right)–\left(8\right)& \hfill \end{array}$$

Since all EVs belonging to a cable c in the original problem are charged at the same node $n_c$ in the single node model, the value of the true assignment $\overrightarrow{l}(\overrightarrow{k})$ does not affect the problem. Hence, the partial observability is resolved.

3.3. Planning and Execution

As the PO-EVCP problem with blind guessing or a surrogate grid has a feasibility region different from the one defined by the constraints (1a–e) and (2a–c), it can be impossible to execute its solution. Moreover, though Li et al. [13] demonstrate that SOCP relaxation is exact in various real grids, the theoretical guarantees of the exactness are limited in the presence of line current constraints. Therefore, the solution obtained by solving the PO-EVCP problem using the SOCP relaxation cannot be safely executed in the grid. To account for that, this paper proposes a planning and execution framework that divides the solution process into two consecutive steps. Planning is the process performed by the EV aggregator, aimed at computing the optimal charging schedule under partial observability. Its counterpart, the executor, can be seen as a part of the grid itself. It is a control algorithm responsible for maintaining the grid state within its physical limits. The executor is considered to be fully-aware of the grid state. In this study, the executor is solving a single-timestep OPF problem, since it is one of the most common grid control algorithms and can be implemented in hardware [14].

At each timestep $t,$ the planner solves an SOCP relaxation of the PO-EVCP problem (using blind guessing or a surrogate grid model). As discussed above, the obtained solution might be imperfect due to the inexactness of the relaxation and/or partial observability. To account for that, planner and executor work in an online fashion: at each timestep the planner solves the PO-EVCP problem and the executor runs the solution. Let ${\mathcal{K}}^t$ be the set of the EVs active at the timestep $t;$ i.e., ${\mathcal{K}}^t=\{k\in \mathcal{K}|t_k^{arr}\le t<t_k^{dep}\}.$ Furthermore, let ${\widehat{p}}_l^t$ denote the part of the planner’s solution corresponding to the power at timestep t at loads where the EVs from ${\mathcal{K}}^t$ are parked. Then, ${\widehat{p}}_k^t$ is used as an input to the executor’s OPF problem:

$$\begin{array}{ccc}\hfill \underset{v^t,i^t,p^t}{max}& \hfill J^t\left(p^t\right)=\sum _{l\in \mathcal{L}}{u}_{k\left(l\right)}{p}_l^t+\sum _{g\in \mathcal{G}}{c}_g^t{p}_g^t& \hfill \\ \hfill \mathrm{subject}\mathrm{to}:& \hfill \left(1\mathrm{a}\right)-\left(1\mathrm{e}\right)& \hfill \left(\mathrm{Executor}\right)\\ \hfill & \hfill p_{l\left(k\right)}^t\le {\widehat{p}}_k^t,k\in {\mathcal{K}}^t& \hfill \end{array}$$

If ${\widehat{p}}_k^t$ is feasible in terms of (1a–e) and the objective is monotonically increasing (which is true if $u_k\gg c_g$), the executor problem solution will match ${\widehat{p}}_k^t.$ The interaction between the planner and the execution is described by Algorithm 1.

Algorithm 1: Planning and execution framework.

Initialize total social welfare $J_{ex}=0$ Initialize EVs’ SOC $e_k=0,$ for $k\in \mathcal{K}$ for $t\in \{t_0,t_1,\dots ,t_T\}$do     For active EVs $k\in {\mathcal{K}}^t,$ obtain ${\widehat{p}}_k^t$ by solving the planner problem     Create the executor problem using ${\widehat{p}}_k^t$     Solve the executor problem, obtain power at loads $p_l^t$ and objective value $J^t\left(p^t\right)$     $J_{ex}\leftarrow J_{ex}+J^t\left(p^t\right)$     for $k\in {\mathcal{K}}^t$ do         $e_k\leftarrow e_k+\mathrm{\Delta }t\times p_{l\left(k\right)}^t$     end for end for

The planning and execution framework guarantees that each grid state is always feasible, and hence allows for evaluation of inexact planners, such as the surrogate grid and blind guessing planners.

4. Experiments

We simulated the EVCP problem using the planning and execution framework with different planners in order to answer the two following questions:

• How important is the knowledge of the precise EV locations in different DC grids for the EV aggregator to solve the EVCP problem?
• Which approach should the EV aggregator use when EV locations are known only at the cable level?

This section describes the details of the simulations and presents the results. Two main components of each simulation are the grid configuration and the scenario. The grid is defined by the numbers of loads, generators, and lines between them; the voltage and power limits of the nodes; and the current limits and conductance of lines. In the experiments, the grid topology was either sampled from the random topology classes (Figure 3) or taken from the real IEEE16 grid [13] (Figure 4). For both meshed and radial topologies of the IEEE16 grid, we considered two cases: with and without connection to the external grid. In the former case, capacities of the feeders A, B, and C were infinite ${\underset{¯}{P}}_g=\infty .$ In the disconnected case, the feeder capacities were set to zero ${\underset{¯}{P}}_g=0.$ For all nodes, the voltage limits were defined as ${\underset{¯}{V}}_n$ = 300 V, ${\overline{V}}_n$ = 400 V. The load power bounds were set to ${\underset{¯}{P}}_l=0,{\overline{P}}_l$ = 10,000 W. The generators power upper bound was set to zero ${\overline{P}}_g$ = 0 W (meaning generators cannot consume power), and the lower bound ${\underset{¯}{P}}_g$ varied across the experiments. The line current limits ${\overline{I}}_{mn}$ also varied. The conductance was equal for all lines in all grids, $y_{nm}$ = 15 S. We always set all generators to have the same capacity ${\underset{¯}{P}}_g$ and cost coefficient $c_g.$ The line capacities ${\overline{I}}_{nm}$ were also equal for all lines. In the experiments with random grids, we sampled one random topology per value of ${\underset{¯}{P}}_l$ and ${\overline{I}}_{mn}.$

Each scenario contained a power price and EV parameters. The power price for each scenario was sampled from the day-ahead price data for the Netherlands [15]. Figure 5a shows an example of the power price curve for a single day. To sample the EV arrival times, we simulated a non-homogeneous Poisson process independently in each load. The arrival rate was similar across the loads and scenarios and derived from the dataset of EV charging sessions in Dundee, Scotland [16]. Figure 5b demonstrates the dynamics of the EV arrival rate.

The demand, parking time, and utility coefficient were sampled from the normal distributions described in

Table 1. Distributions of the EV parameters.

	Distribution	Unit
Desired SOC ${\overline{E}}_k^t$	$\mathcal{N}(8500,500)$	Watt
Charging time $t_k^{dep}-t_k^{arr}$	$\mathcal{N}(3.75,0.5)$	Hour
Utility coefficient $u_k$	$\mathcal{N}(5\times {10}^{-4},5\times {10}^{-7})$	$/Watt

. It is worth mentioning that we chose values for the utility coefficients $c_k$ such that they were at least an order of magnitude larger than the power price $c_k^t.$ In this case, the objectives in the executor and planner problems were monotonically increasing, i.e., charging an EV always increases the social welfare.

The planning horizon was set to 24 h for all simulations, and timestep size to 30 min. For each grid topology and parameters, we used 6 scenarios to evaluate the performance of the planners.

The optimization routine was performed by MOSEK Fusion API for Python 9.3.10 [17] on a single machine with Intel^® Core i7-10700K Processor. We used default solver parameters except for setting basisRelTolS, basisTolS, and intpntCoTolDfeas to ${10}^{-9}.$ The initial conditions and convergence criteria were also default for MOSEK.

4.1. Importance of the Locations

To estimate the importance of knowing the precise EV locations, we tested a blind guessing SOCP planner on the PO-EVCP problem using different degrees of observability of the EV locations (

Table 2. Four degrees of observability of the EV locations.

Observability	Precisely Known Locations	Locations Known up to Cable
Full	All EVs	None
Present	EVs that have already arrived	EVs arriving in the future
Past	EVs that stayed in the grid for at least one timestep	EVs that have just arrived and future EVs
Blind	None	All EVs

). The planners were obtaining the assignments $\overrightarrow{l}(\overrightarrow{k})$ by first fixing the precisely known locations and then randomly sampling the remaining locations within the corresponding cables.

We evaluated all four planners by sampling random meshed grids (Figure 3c) with 12 nodes and 4 generators and varying generation capacity ${\underset{¯}{P}}_g$ and the lines’ current limit ${\overline{I}}_{mn}.$ Figure 6 demonstrates the provided social welfare as a function of ${\underset{¯}{P}}_g$ and ${\overline{I}}_{mn}.$ For better comparability between different topologies, the social welfare is normalized relative to the full planner.

The simulations imply that knowing EV locations becomes important when the line current constraints are tight. On the contrary, the tighter the generation constraints are, less effect is caused by the partial observability. Moreover, the planner with access to the present, but not the future, EV locations (labelled SOCP_present) performed almost optimally, while past and blind planners (SOCP_past and SOCP_blind, respectively) provided considerably less social welfare. Practically, that means that knowing locations of the EVs arriving in the future is not crucial and knowing currently present EVs locations is enough for the EV aggregator to compute the charging schedule. However, when the locations are unavailable even for the active EVs in the grid, the EV aggregator might want to use surrogate grid models for planning.

4.2. Surrogate Grid Models

As demonstrated in the previous section, the blind planner performs suboptimally for tight line constraints. In this section we compare single node and parallel nodes models with the blind planner and demonstrate their benefits for the EV aggregator.

We used all four random topologies from Figure 3 and two versions of the IEEE 16 buses grid (Figure 4) for the simulations. We varied ${\overline{I}}_{mn}$ to determine how the tightness of the line constraints affects planing. Importantly, we used different ranges for ${\overline{I}}_{mn}$ in different grids, such that the highest value in each range represents the case when the line constraints in the full planner’s solution were not binding. The results for random grids and IEEE16 grids are presented in Figure 7 and Figure 8, respectively. Appendix A also shows the solutions achieved by different planners at one planning timestep.

The results in Figure 7 suggest that all three planners reach nearly optimal performances as the line current constraints become irrelevant. In the tight constraints case, however, the parallel nodes planner (labeled SOCP_parallel) is clearly dominant. The single node (SOCP_single) performs slightly worse than the blind planner in the radial grids, but the gap decreases when the number of generators increases. In the meshed grids with additional DGs, the single node planner outperforms the blind guessing planner.

The results in Figure 8 demonstrate similar behavior. Interestingly, the parallel nodes planner is much more dominant in the radial version of the grid. In the meshed case, when more generators are connected to each cable, the single node model again slightly outperforms the blind planner.

Based on Figure 7 and Figure 8, we may conclude that the parallel nodes planner seems to be the best choice for tightly constrained grids in terms of performance. In practice, however, the computational time may also be an important factor for the EV aggregator. Larger grids and longer planning horizons may make the EVCP problem hardly tractable even using the SOCP relaxation. Since the parallel nodes’ surrogate grid uses more lines and passive nodes than the original grid, it is expected to be the slowest method. Similarly, the single node model should scale best. Figure 9 compares the planning time of different planners as a function of the grid size. For that experiment, we used random radial grids with DGs from Figure 3b. We investigated the planning time in the grids with three cables of varying cable lengths (Figure 9a) and in the grids with varying numbers of cables with six loads (Figure 9b).

The results in Figure 9 confirm the poor scalability of the parallel nodes planner and show the superiority of the single node solution.

5. Conclusions

In this paper, we have extended the EVCP problem for DC microgrids by including partial observability of the EV locations (PO-EVCP). We have studied the effects of partial observability on the performance of planners and suggested two solutions tailored to deal with the unknown EV locations. The experiments in this study lead to the following conclusions about the PO-EVCP:

1.

In DC grids with tight line constraints, knowing the locations of the active EVs in the grid is important for computing charging schedules which maximize the social welfare. Practically, this should be considered when designing a communication protocol between EV owners and the EV aggregator.

2.

If, due to the limitations of the communication scheme or privacy concerns, the EV aggregator can only partially observe the EV locations, it may prefer to use parallel nodes or single node models. The former model is clearly dominant performance-wise, but requires more resources, and the latter offers great scalability at the cost of a tiny performance drop.

To ensure realistic conditions, the experiments in this work included a wide range of line capacities and demands, and also randomly generated topologies. Therefore, we are confident that the conclusions drawn from these simulation results are quite general and will also hold in practice.