Hierarchical Game for Coupled Power System with Energy Sharing and Transportation System

EV

Electric vehicle.

GV

Gasoline vehicle.

CS

Charging station.

OD

Origin-destination.

PV

Photovoltaic.

TS

Transportation system.

PS

Power system.

DER

Distributed energy resource.

MILP

Mixed-integer linear program.

$\mathcal{E}_{N}$

Set of nodes in the power system.

$\mathcal{E}_{L}$

Set of lines in the power system.

$\mathcal{C}$

Set of CSs.

$C(i)$

Set of CSs powered by prosumer $i\in\mathcal{E}_{N}$.

$\mathcal{T}_{N}$

Set of nodes in the transportation system.

$\mathcal{T}_{A}$

Set of links in the transportation system.

$\mathcal{T}_{R}$

Set of origin nodes.

$\mathcal{T}_{S}$

Set of destination nodes.

$\mathcal{K}^{rs}_{g}$

Set of GV paths connecting OD pair $rs$.

$\mathcal{K}^{rs}_{e}$

Set of EV paths connecting OD pair $rs$.

$T_{A}^{R}$

Set of regular links.

$T_{A}^{C}$

Set of charging links.

$T_{A}^{B}$

Set of bypass links.

$S$

Set of partitions.

$p_{i}$

Renewable generator output at prosumer $i\in\mathcal{E}_{N}$.

$d_{i}^{f}$

Fixed power demand at prosumer $i\in\mathcal{E}_{N}$.

$\underline{D}_{i}/\overline{D}_{i}$

Lower/Upper bound of elastic demand at prosumer $i$.

$m_{a}$

Market sensitivity.

$r_{ni},x_{ni}$

Resistance and reactance of line $(n,i)$.

$l_{ni}$

Squared current magnitude of line $(n,i)$.

$v_{n}$

Squared voltage magnitude of node $n$.

$\underline{P_{i}}/\overline{P_{i}}$

Lower/Upper bound of $P_{i}$.

$\underline{Q_{i}}/\overline{Q_{i}}$

Lower/Upper bound of $Q_{i}$.

$\underline{v_{i}}/\overline{v_{i}}$

Lower/Upper bound of $v_{i}$.

$\overline{\ell_{ni}}$

Upper bound of $\ell_{ni}$.

$q^{rs}_{g}/q^{rs}_{e}$

Total traffic flow between $r\in\mathcal{T}_{R}$ and $s\in\mathcal{T}_{S}$ for GV/EV.

$\delta_{akg}^{rs}/\delta_{ake}^{rs}$

Indicator variable for GV/EV.

$t_{a}^{0}$

Free travel time of link $a$.

$h_{a}$

Free travel capacity of link $a$.

$t_{a,\mu}^{c}$

Average service time at CS $c$ of link $a$.

$t_{a,w}^{c}$

Maximum waiting time at CS $c$ of link $a$.

$h_{a}^{c}$

Maximum allowable EV flow at CS $c$ of link $a$.

$\gamma^{c}_{a}$

Electricity price of charging link $a$ with CS $c$.

$E_{b}$

EV battery charging demand.

$\omega$

A constant converting time to monetary value.

$Z$

Integer parameter for linear approximation.

$c_{m},A_{1},A_{2}$

Constant coefficient matrices in compact form.

$D_{TS},B_{2}$

Constant coefficient matrices in compact form.

$\lambda_{v,s}^{min}/\lambda_{v,s}^{max}$

Lower/Upper bounds of $\lambda_{v,s}$ for partition $s$.

$D_{TS,s}^{min}/D_{TS,s}^{max}$

Lower/Upper bounds of $D_{TS,s}$.

$|S|$

Partition number of McCormick envelope.

$d_{i}$

Elastic demand at node $i\in\mathcal{E}_{N}$.

$D_{i}^{T}$

Total charging demand of links $a\in C(i)$.

$q_{i}$

Sharing quantity of node $i\in\mathcal{E}_{N}$.

$\lambda_{i}$

Sharing price for node $i\in\mathcal{E}_{N}$.

$b_{i}$

Bid of prosumer $i\in\mathcal{E}_{N}$ in the sharing market.

$P_{ni}/Q_{ni}$

Active/Reactive power flow of line $(n,i)$.

$U_{i}$

Utility of prosumer $i\in\mathcal{E}_{N}$.

$f_{kg}^{rs}/f_{ke}^{rs}$

GV/EV traffic flow of a path $k\in\mathcal{K}^{rs}_{g}/\mathcal{K}^{rs}_{e}$.

$x_{a}$

Aggregate traffic flow of link $a\in\mathcal{T}_{A}$.

$x_{ag}/x_{ae}$

Aggregate GV/EV traffic flow of link $a\in\mathcal{T}_{A}$.

$t_{a}$

Travel time on link $a\in\mathcal{T}_{A}$.

$c_{kg}^{rs}$/$c_{ke}^{rs}$

Total cost of a path $k\in\mathcal{K}^{rs}_{g}/\mathcal{K}^{rs}_{e}$ for GV/EV.

$u^{rs}_{g}/u^{rs}_{e}$

Minimal cost from $r\in\mathcal{T}_{R}$ to $s\in\mathcal{T}_{S}$ for GV/EV.

$\xi^{z},\eta^{z}$

Auxiliary variables.

$y_{v}$

Vector variable in compact form.

$\lambda_{v},\mu_{v}$

Dual variable vectors in compact form.

$y_{s}$

Binary variable for partition $s\in S$.

$\lambda_{v,s}$

Dual variable $\lambda_{v}$ for partition $s\in S$.

$D_{TS,s}$

Variable $D_{TS}$ for partition $s\in S$.

$\sigma$

Auxiliary variable to replace bilinear term.

The power system can be modeled as a connected graph $\mathcal{G}_{E}=[\mathcal{E}_{N},\mathcal{E}_{L}]$, where $\mathcal{E}_{N}$ and $\mathcal{E}_{L}$ represent the set of nodes and power lines, respectively. Each prosumer node $i$ has a renewable generator whose output is $p_{i}$, fixed demand $d_{i}^{f}$, and elastic demand $d_{i}\in[\underline{D}_{i},\overline{D}_{i}]$. Other nodes only have fixed demand. For notation conciseness, for the nodes with fixed demand, we let their $p_{i}=0$ and $\underline{D}_{i}=\overline{D}_{i}=0$. Denote the set of CSs supplied by prosumer node $i$ as $C(i)$, which imposes total power demand $D_{i}^{T}$ by EVs. With the real-time renewable generator output $p_{i}$, the prosumer $i\in\mathcal{E}_{N}$ can adjust its elastic demand $d_{i}$ and share its excessive/deficit energy $q_{i}$ with other prosumers at a price $\lambda_{i}$ to maintain energy balancing. The utility of elastic demand can be represented by concave functions $U_{i}(d_{i}),\forall i$, so that $-U_{i}(d_{i}),\forall i$ are convex functions. We propose an energy sharing mechanism as follows:

To participate in energy sharing, each prosumer $i\in\mathcal{E}_{N}$ submits a bid $b_{i}$ to the market operator, indicating its willingness to buy. The energy sharing market prices $\lambda_{i},\forall i\in\mathcal{E}_{N}$ and the sharing quantities $q_{i},\forall i\in\mathcal{E}_{N}$ will be determined according to the bids. Their relationship can be represented by a generalized demand function $q_{i}=-m_{a}\lambda_{i}+b_{i}$, where $m_{a}>0$ is the market sensitivity. It shows that given the same price $\lambda_{i}$, the prosumer will buy more if it has a higher willingness to buy (the higher $b_{i}$, the higher $q_{i}$); the prosumer will buy less when energy is more expensive (the higher $\lambda_{i}$, the less $q_{i}$). The market operator clears the market by solving:

where

where $Q_{i}$ is bus $i$’s reactive power injection, $P_{ni}/Q_{ni}$ is the active/reactive power flow of line $(n,i)$, $r_{ni}/x_{ni}$ is the resistance/reactance, and $\ell_{ni}/v_{n}$ is the squared current/voltage magnitude. The objective function (1a) is designed to minimize the sum of square of the energy sharing prices. We will prove later in Proposition 1 that such a design can guarantee an equilibrium that is socially optimal. Constraints (2a)-(2d) describe the branch flow model. Second-order cone relaxation is applied, so the original equality constraint has been turned into the inequality constraint in (2d). Constraints (2e)-(2h) include the physical bounds of prosumer power injection capacities, squared bus voltage magnitudes, and squared line current magnitudes.

For each prosumer $i\in\mathcal{E}_{N}$, its net cost equals the energy sharing cost $\lambda_{i}q_{i}$ (when $q_{i}<0$, it means prosumer $i\in\mathcal{E}_{N}$ will sell energy to the market and receive revenue $-\lambda_{i}q_{i}$) minus its utility $U_{i}(d_{i})$. It can decide on the optimal values of $d_{i}$ and $b_{i}$ to minimize its net cost:

Constraint (3b) shows that the renewable generation plus the energy it buys from the energy sharing market can satisfy its fixed and elastic demands. Constraint (3c) is the demand adjustable range.

The aforementioned energy sharing mechanism can protect the privacy of both prosumers and the operator to some extent, since the network constraints (2a)-(2h) are known only to the operator and the individual capacity constraint (3c) is available only to the prosumer. If we take the market operator as a virtual player, then all prosumers and the operator play a generalized Nash game. A major feature that distinguishes the generalized Nash game from a standard Nash game is that both the objective function and the constraints of one player are influenced by the strategies of the other players [33]. Denote the objective function (1a) of the market operator as $\Gamma_{M}(\lambda)$ and its feasible set as $\mathcal{X}_{M}(b):=\{\lambda~{}|~{}\eqref{eq:market.2}~{}\mbox{is satisfied.}\}$. Denote the objective function (3a) of each node as $\Gamma_{i}(\lambda_{i},b_{i},d_{i})$ and its feasible set as $\mathcal{X}_{i}(\lambda_{i}):=\{(b_{i},d_{i})~{}|~{}\eqref{eq:eachnode.2}-\eqref{eq:eachnode.3}~{}\mbox{are satisfied.}\}$. The game consists of the following elements:

1. 1)

   The set of players, including prosumers $i\in\mathcal{E}_{N}=\{1,2,\ldots,I\}$ and the market operator $M$.

2. 2)

   Strategy sets: for prosumer $i$, it is $\mathcal{X}_{i}(\lambda_{i})=\{(b_{i},d_{i})~{}|~{}\eqref{eq:eachnode.2}-\eqref{eq:eachnode.3}~{}\text{are satisfied.}\}$, and for market operator $M$, it is $\mathcal{X}_{M}(b)=\{\lambda~{}|~{}\eqref{eq:market.2}~{}\text{is satisfied.}\}$.

3. 3)

   Payoff functions: for prosumer $i$, it is $\Gamma_{i}(\lambda_{i},b_{i},d_{i})$ and for the market operator, it is $\Gamma_{M}(\lambda)$.

To be concise, denote the energy sharing game by $\mathcal{G}_{1}=\{(\mathcal{E}_{N},M),(\mathcal{X}_{i},\mathcal{X}_{M}),(\Gamma_{i},\Gamma_{M})\}$.

In general, generalized Nash games are difficult to analyze, and there is no theoretical guarantee for the existence and uniqueness of an equilibrium. Moreover, as part of the power demand $D_{i}^{T}$ comes from the transportation system, the interaction among the two systems constitutes another Nash game described later in Section II-C. This makes the problem even more sophisticated. In Section III, we will derive an equivalent optimization model in Proposition 1 for computing the generalized Nash equilibrium efficiently.

Remark: With the proliferation of distributed energy resources (DERs), passive consumers turn into proactive prosumers, calling for innovative market mechanisms to coordinate their flexibility and reduce their overall operational costs [34, 5]. Energy sharing market has emerged as one of the potential solutions to this challenge [35]. In an energy sharing market, prosumer makes decisions based on their own interests, thus giving rise to competition and forming a game. Usually, the equilibrium of such a game is not socially optimal because of the conflicts of interest. In this paper, we propose an energy sharing market mechanism with the market clearing rule in (1). In particular, (1a) is designed as minimizing the sum of squares of prices. We prove that under the proposed mechanism, the energy sharing equilibrium can attain social optimum, as Proposition 1 in Section III states.

The transportation system can be modeled as a connected graph $\mathcal{G}_{T}=[\mathcal{T}_{N},\mathcal{T}_{A}]$, where $\mathcal{T}_{N}$ and $\mathcal{T}_{A}$ represent the set of nodes and roads (links), respectively. Each road (link) is denoted by $a\in\mathcal{T}_{A}$ and its traffic flow by $x_{a}$. Each driver needs to travel from an origin node $r$ to a destination node $s$. Each origin-destination (OD) pair $rs$ is connected by a set of paths. We consider two kinds of vehicles in the transportation system: GVs and EVs. The GV traffic flow of a path $k\in\mathcal{K}^{rs}_{g}$ is $f_{kg}^{rs}$ and the given total GV traffic flow from $r$ to $s$ is $q^{rs}_{g}=\sum_{k\in\mathcal{K}^{rs}_{g}}f_{kg}^{rs}$. Similarly, for EV traffic flow, $q^{rs}_{e}=\sum_{k\in\mathcal{K}^{rs}_{e}}f_{ke}^{rs}$. To characterize the relationship between $f_{kg}^{rs},f_{ke}^{rs},\forall k,\forall(rs)$ and $x_{a}$, we introduce the indicator variable $\delta_{akg}^{rs}$ ($\delta_{ake}^{rs}$) for GVs (EVs). $\delta_{akg}^{rs}=1$ ($\delta_{ake}^{rs}=1$) if road $a\in\mathcal{T}_{A}$ is part of the path $k\in\mathcal{K}^{rs}_{g}$ ($k\in\mathcal{K}^{rs}_{e}$); otherwise, $\delta_{akg}^{rs}=0$ ($\delta_{ake}^{rs}=0$). Therefore,

where $\sum_{rs}$ is used to abbreviate $\sum_{r}\sum_{s}$. The travel time $t_{a}$ on a link $a\in\mathcal{T}_{A}$ depends on its aggregate traffic flow $x_{a}$.

There are two types of links: the regular link without a CS $a\in T^{R}_{A}$ and the charging link with a CS. When an EV travels on the charging link, it can choose to get charged at the CS or bypass the CS. To facilitate the modeling and analysis, the original network is modified by adding a bypass link in parallel to the charging link, as shown in Fig. 2. The charging link is denoted by $a\in T^{C}_{A}$ while the bypass link by $a\in T^{B}_{A}$. $\mathcal{T}_{A}=T_{A}^{R}\cup T_{A}^{C}\cup T_{A}^{B}$.

For the regular link $a\in T^{R}_{A}$, we adopt the Bureau of Public Roads (BPR) function (6) to describe the travel time, which increases with the traffic flow [36].

where $t^{0}_{a}$ and $h_{a}$ are the free travel time and the capacity of link $a$. For a charging link ($a\in T_{A}^{C}$), the time spent on it is

where $t^{c}_{a,\mu},t^{c}_{a,w},h^{c}_{a}$ denote the average service time, the maximum waiting time, and the maximum allowable EV flow of the CS $c$ on link $a$. The travel time on a bypass link $a\in T_{A}^{B}$ is so short that is assumed to be zero, i.e., $t_{a}(x_{a})=0,~{}\forall a\in T_{A}^{B}$.

For a GV owner, its travel cost $c^{rs}_{kg}$ on path $k\in K_{g}^{rs}$ between OD pair $rs$ is only influenced by the travel time:

where $\omega$ is the monetary cost of travel time.

For an EV owner, when deciding its route, it cares about two factors: the travel time and the charging price. Denote the charging price of the charging link $a$ with CS $c$ by $\gamma^{c}_{a}$, and we have $\gamma^{c}_{a}=\lambda_{i}$ if CS $c\in C(i)$. The EV travel cost of a path $k\in\mathcal{K}^{rs}_{e}$ is

where $E_{b}$ represents an EV’s charging demand, which is a constant, e.g., 20kWh.

Given the total traffic flows $q_{rs}$ of all OD pairs $rs$, each driver will choose the route that can minimize its own travel cost. Meanwhile, the decisions of all drivers will affect the aggregate traffic flow $x_{a},\forall a\in\mathcal{T}_{A}$ and thus the travel time $t_{a}(x_{a})$. An equilibrium is reached when no driver can reduce its travel cost by changing its route unilaterally.

Take (10) as an example. For any used path $k\in\mathcal{K}^{rs}_{g}$, we have $f_{kg}^{rs*}>0$ and that $c_{kg}^{rs*}$ equals $u^{rs*}_{g}$. For any unused path, we have $f_{kg}^{rs*}=0$ and that the travel cost $c_{kg}^{rs*}$ is larger than or equal to $u^{rs*}_{g}$. The value of $u^{rs*}_{g}$ represents the minimum travel cost that is the same across all used paths from $r$ to $s$. As one driver’s driving behavior may influence other drivers’ travel time and travel cost, all drivers constitute a Nash game. The game consists of the following elements:

1. 1)

   The set of players, including EV owners $\mathcal{S}_{e}=\{1,2,\ldots,I_{e}\}$ and GV owners $\mathcal{S}_{g}=\{1,2,\ldots,I_{g}\}$.

2. 2)

   Strategy sets: for EV owner $i\in\mathcal{S}_{e}$ driving from $r$ to $s$, it is $\mathcal{Y}_{e}=\{f_{ke}^{rs},\forall k\in\mathcal{K}_{e}^{rs}|\sum_{k\in\mathcal{K}_{e}^{rs}}f_{ke}^{rs}=q_{e}^{rs}\}$; and for GV owner $i\in\mathcal{S}_{g}$ driving from $r$ to $s$, it is $\mathcal{Y}_{g}=\{f_{kg}^{rs},\forall k\in\mathcal{K}_{g}^{rs}|\sum_{k\in\mathcal{K}_{g}^{rs}}f_{kg}^{rs}=q_{g}^{rs}\}$.

3. 3)

   Payoff functions: for EV owners $i\in\mathcal{S}_{e}$ from $r$ to $s$, it is $\Gamma_{e}(x_{a}(f_{ke}^{rs},\forall e,k,rs;f_{kg}^{rs},\forall g,k,rs),\forall a)$ given by (9); for GV $g$ from $r$ to $s$, it is $\Gamma_{g}(x_{a}(f_{ke}^{rs},\forall e,k,rs;f_{kg}^{rs},\forall g,k,rs),\forall a)$ given by (8).

To be concise, denote by $\mathcal{G}_{2}=\{(\mathcal{S}_{e},\mathcal{S}_{g}),(\mathcal{Y}_{e},\mathcal{Y}_{g}),(\Gamma_{e},\Gamma_{g})\}$ the strategic form of this Nash game.

In Sections II-A and II-B, we introduced the generalized Nash game in the power system and the Nash game in the transportation system, respectively. Externally, the power and transportation systems couple in two ways:

1) The charging demand in the transportation system is part of the electric load in the power system

2) The electricity price $\gamma^{c}_{a}$ on each CS $c$ equals the sharing price $\lambda_{i}$ at node $i\in\mathcal{E}_{N}$ if $c\in C(i)$. Since each prosumer node can choose to sell energy in the sharing market or serve the transportation system, to prevent arbitrage, the prices for both options should be equal.

The interactions inside and between the two systems are shown in Fig. 3, which is a hierarchical game. To be specific, in the power system, there is a generalized Nash game among all prosumers participating in the energy sharing market. In the transportation system, all drivers strategically choose their route and play a Nash game. Moreover, the traffic flow in the transportation system will influence the demand in the power system, and the electricity price in the power system will impact the cost of EVs in the transportation system. Therefore, there is a generalized Nash game between two systems. The game consists of the following elements:

1. 1)

   Players: the power system as a whole, denoted by $S_{ps}$ and the transportation system as a whole, denoted by $S_{ts}$.

2. 2)

   Strategy sets: for the power system, it is $\mathcal{Z}_{ps}(D_{i}^{T},\forall i)=\{\lambda_{i},\forall i~{}|~{}\lambda$ is the energy sharing price at the equilibrium (1) given $D_{i}^{T},\forall i\}$; for the transportation system, it is $\mathcal{Z}_{ts}(\lambda)=\{D_{i}^{T},\forall i~{}|~{}D_{i}^{T}=\sum_{c\in\mathcal{C}_{i}}x_{a}E_{b},~{}x_{a}$ is given by the Wardrop User Equilibrium with $\lambda$.

3. 3)

   Payoff functions: for power system, it is the sum of (3a) for all $i$ at the energy sharing equilibrium (1) given $D_{i}^{T},\forall i$, denoted by $\Gamma_{ps}(D_{i}^{T},\forall i)$; for transportation system, it is the total travel cost of all EVs and GVs at the Wardrop User Equilibrium given $\lambda$, denoted by $\Gamma_{ts}$.

To be concise, denote the game above by $\mathcal{G}_{3}=\{(S_{ps},S_{ts}),(\mathcal{Z}_{ps},\mathcal{Z}_{ts}),(\Gamma_{ps},\Gamma_{ts})\}$.

We first provide two optimization models for computing the equilibrium inside the power and transportation systems, respectively, as stated in Propositions 1 and 2.

The proofs of Propositions 1 and 2 are in Appendices A and B, respectively. They facilitate our further analysis. It is worth noting that the property given by Proposition 1 is not trivial. In fact, at most of the time, the equilibrium of a generalized Nash game is not socially optimal; moreover, there is no guarantee on its existence and uniqueness [33]. Even in a linear and convex setting, it is challenging to analyze a generalized Nash game due to the variability and interdependency of strategy sets, i.e., each player’s strategy set depends on other players’ strategies. In Proposition 1, we prove that a unique energy sharing equilibrium exists and happens to be the optimal solution of the centralized problem (13). This shows the effectiveness of the proposed energy sharing mechanism and facilitates further analysis of the market equilibrium.

Two equivalent optimization models (13) and (14) are derived for computing the equilibrium in the power and transportation systems, respectively. As we can see from Fig. 3, there is a Nash game between the two systems since the electricity price affects the travel cost in the transportation system and the traffic flow affects the demand in the power distribution system. In the following, we convert the optimization problems (13)-(14) into a set of mixed-integer linear constraints by optimality conditions and linearizations, based on which we can obtain the hierarchical game equilibrium of the coupled power and transportation systems.

Regarding the energy sharing problem (13), though the second-order cone constraint (2d) is convex, its nonlinearity still presents a challenge for efficient computation. To address this, polyhedral approximation is applied to turn (2d) into a set of linear constraints. Further, we replace the energy sharing problem with its primal-dual optimality condition, which is different from the traditional method that is based on the KKT condition. In contrast, the transportation problem (14) is replaced by its KKT condition. This is because the energy sharing problem comprises mainly of inequality constraints, for which the KKT condition would result in numerous complementary slackness constraints and require a lot of binary variables to turn it into a solvable mixed-integer linear program (MILP). The primal-dual optimality condition can avoid the high computational burden since it requires no binary variable. For the transportation problem with few inequality constraints, we still replace it with its KKT condition.