Dynamic Game-based Maintenance Scheduling of Integrated Electric and Natural Gas Grids with a Bilevel Approach
Chong Wang Zhaoyu Wang Yunhe Hou Kang Ma
math.OC






Dynamic Game-based Maintenance Scheduling of Integrated Electric and Natural Gas Grids with a Bilevel Approach
    
Chong Wang, Member, IEEE, Zhaoyu Wang, Member, IEEE, Yunhe Hou, Senior Member, IEEE, and Kang Ma,  Member, IEEE

This work is supported by the National Science Foundation under CMMI 1745451 and National Natural Science Foundation of China under Grant 51677160.	

C. Wang is with the College of Energy and Electrical Engineering, Hohai University, Nanjing 211100, China (e-mail: wangchonghhu@gmail.com).

Z. Wang is with the Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 5001, USA (email: wzy@iastate.edu).

Y. Hou is with the Department of Electrical & Electronic Engineering, The University of Hong Kong, Pokfulam, Hong Kong (email: yhhou@eee.hku.hk).

K. Ma is with Electronic & Electrical Engineering Department, University of Bath, BA2 7AY, UK (e-mail: K.Ma@bath.ac.uk).
 


    
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




This paper proposes a dynamic game-based maintenance scheduling mechanism for the asset owners of the natural gas grid and the power grid by using a bilevel approach. In the upper level, the asset owners of the natural gas grid and the power grid schedule maintenance to maximize their own revenues. This level is modeled as a dynamic game problem, which is solved by the backward induction algorithm. In the lower level, the independent system operator (ISO) dispatches the system to minimize the loss of power load and natural gas load in consideration of the system operating conditions under maintenance plans from the asset owners in the upper level. This is modeled as a mixed integer linear programming problem. For the model of the natural gas grid, a piecewise linear approximation associated with the big-M approach is used to transform the original nonlinear model into the mixed integer linear model. Numerical tests on a 6-bus system with a 4-node gas grid and a modified IEEE 118-bus system with a 20-node gas grid show the effectiveness of the proposed model.


bilevel approach, dynamic game, maintenance scheduling, natural gas and electric grids


[2.75cm]
[I01]b,b'Index of power buses.
[I02]n,n'Index of gas nodes.
[I03]uIndex of generators that will be under maintenance during the given time window.
[I04]u'Index of generators that will not be under maintenance during the given time window.
[I05]wIndex of gas wells.
[I06]sIndex of gas storages.
[I07]lIndex of lines that will be under maintenance during the given time window.
[I08]l'Index of lines that will not be under maintenance during the given time window.
[I09]pIndex of pipelines that will be under maintenance during the given time window.
[I10]p'Index of pipelines that will not be under maintenance during the given time window.
[I11]pcIndex of pipelines with compressors.
[I12]t,t'Index of time periods.
[I12]kIndex of the linear functions.
[I13]Ω _b^USet of generating units at power bus b.

[I15]Ω _b^BSet of power buses connected to bus b.
[I16]Ω _n^WSet of gas wells at natural gas node n.
[I17]Ω _n^SSet of gas storages at natural gas node n.
[I18]Ω _n^GSet of gas-fired units at natural gas node n.

[I20]Ω _n^NSet of gas nodes connected to natural gas node n.



[P01]A_p,t^k,A_p',t^kSlopes of piecewise linear segments.
[P02]B_p,t^k,B_p',t^kIntercepts of piecewise linear segments.
[P03]B_b,b'Electrical susceptance of line b-b'.
[P04]C_l,t^M,C_p,t^M, C_u,t^MMaintenance costs for line l,  pipeline p and generator u at t.
[P05]C_u,t^F,C_u,t^LFixed cost and linear cost of generator u at t.
[P05]C_u',t^F,C_u',t^LFixed cost and linear cost of generator u' at t.
[P06]C_u',t^SStart up cost of generator u at t.
[P07]C_u,t^P, C_u',t^PRevenue of generator u and u' at t.
[P08]C_w,t,C_s,tCost of gas production and storage at t.
[P09]C_b,t^LSCost of power load shedding of bus b at t.
[P10]C_n,t^LSCost of gas load shedding of node n at t.
[P11]C_n,n'Weymouth constant of pipeline n-n'.
[P12]T_u^ON,T_u^OFFMin on and off time periods of generator u.
[P13]T_w^ON,T_w^OFFMin on and off time periods of gas well w.
[P14]T_l^M,T_p^M,T_u^MPeriods of maintenance of line l and pipeline p.
[P15]EF_uEfficiency factor of gas-fired unit u.
[P16]f_p^k,f_p^kMin/Max gas flow of linear segments for pipeline p.
[P16]f_p'^k,f_p'^kMin/Max gas flow of linear segments for pipeline p'.
[P17]G_w, G_wMin and max outputs of gas well w.
[P18]G_s, G_sMin and max outputs of gas storage s.
[P19]L_n,tGas load of gas node n at t (non-gas-fired unit).
[P20]L_b,tPower load of bus b at t.
[P21]M^L,M^P,M^θLarge numbers.

[P29]N_t^L,M, N_t^P,MMax number of lines and pipelines under maintenance at t.
[P29]N_t^U,MMax number of generators under maintenance at t.
[P30]P_u, P^uMax and min outputs of generator u.
[P31]P_b,b'^LMin/Max capacity of line b - b'.
[P32]R_u, R_u', R_u, R_u'Ramp-up and ramp-down limits of generator u and u', respectively.
[P33]R_s, R_sIn-flow and out-flow limits of gas storage s.
[P34]θ_b, θ_bMin/max of phase angles of bus b.
[P34]θ^LPhase angle difference limit.
[P35]π_n, π_nMin/max squared pressures.
[P36]λ _pcCompression factor.

[N01]F_n,n',tGas flow from n to n' at t.
[N02]f_p',t^k,f_p,t^kPiecewise linear gas flow at t.
[N03]G_w,tGas production of gas well w at t.
[N04]G_s,t,G_s,t - 1Gas inventory of gas storage s at t and t-1.
[N05]L_u,tGas consumption of gas-fired unit u at t.
[N06]ΔL_n,tGas load shedding of gas node n at t.
[N07]ΔL_b,tPower load shedding of bus b at t.
[N08]v_l,t,v_l,t-1,v_l,t'Binary variables to indicate if transmission line l is under maintenance at t, t-1, and t', respectively. `1' denotes maintenance, otherwise `0'
[N09]v_p,t,v_p,t-1,v_p,t'Binary variables to indicate if pipeline p is under maintenance at t, t-1, and t'. `1' denotes maintenance, otherwise `0'.
[N10]v_u',t,v_u',t - 1, v_u',t'Binary variables to indicate if generator u' is under maintenance at t, t-1, and t', respectively. `1' denotes maintenance, otherwise `0'.
[N10]v_u,t,v_u,t-1,v_u,t'Binary variables to indicate the states of generator u at t, t-1, and t', respectively. `1' and `0' denote on and off-state, respectively. These variables are used for unit commitment.
[N11]v_w,t,v_w,t - 1, v_w,t'Binary variables to indicate the states of gas well w at t, t-1, and t'. `1' and `0' denote on and off-state, respectively.
[N12]P_u,t, P_u,t-1Power generation of generator u at t and t-1, respectively.
[N12]P_u',t, P_u',t-1Power generation of generator u' at t and t-1, respectively.
[N13]P_b,b',t^LPower from bus b to bus b' at t.
[N14]PS_n,t, PS_n',tPressure of gas nodes n and n' at t.
[N15]o_u',tBinary variable to indicate if generator u' is started up at t.
[N16]θ _b,t,θ _b',tPhase angles of buses b and b' at t.
[N17]η _p',t^k,η _p,t^kBinary variables to indicate if the piecewise linear function k is selected. `1' denotes `selected', and `0' denotes `non-selected'.
[N18]π _n,t,π _n',tSquared pressures of gas nodes n and n'.

[X01]i ∈{ pn,pe}Player i. pn and pe denote the owner of the natural gas grid and the owner of power grid, respectively.
[X02]eDecision epoch e in the game tree.
[X03]H_i,eSet of decision nodes of the player i at the decision epoch e.
[X04]h_i,eA decision node of the player i at the decision epoch e, h_i,e∈ H_i,e.
[X05]D_h_i,eSet of decisions that can be made at the decision  node h_i,e.
[X06]d_h_i,eA decision that can be made at the decision node h_i,e, d_h_i,e∈D_h_i,e.
[X07]d_h_i,e^ *Optimal decision at the decision node h_i,e.
[X08]ℵ (d_h_i,e)A decision node followed a decision d_h_i,e.
[X09]ν (h_i,e)A path from the initial decision node to h_i,e.
[X10]ζ ^ * (h_i,e)Optimal path from h_i,e to the end decision node.
[X11]F_i( ∙ )Function value of player i with a path `∙'.
[X12]SPNESubgame perfect Nash equilibrium.




§ INTRODUCTION

DUE to higher efficiency, less contamination, and lower costs compared to conventional coal plants, more natural gas-fired units are integrated into power systems. Based on the data from the Energy Information Administration (EIA), 32.1% of U.S. electricity was supplied by natural gas-fired units in the first month of 2016 <cit.>. More than 60% of new generation required from 2025 to 2040 in the U.S. will be fueled by natural gas <cit.>. Growing consumption of natural gas promotes the construction of pipeline networks, which lead to a coupled system associated with the electric grid. Since the natural gas grid is coupled with the electric grid via gas-fired units, it has a great influence on the electric grid <cit.>. An interruption or an outage in the natural gas system may lead to the loss of gas supply for the gas-fired units, which can jeopardize the power system security and result in electric load shedding. For example,  in 2002, a disruption on a single pipeline forced the loss of 2019 MW electricity generation at the Collins generating station near Chicago, and further led to cascading power outages in nearby areas <cit.>. Therefore, it is necessary to ensure high reliability of the coupled natural gas and electric system. Maintenance scheduling, as an important means to enhance system reliability <cit.>, should include the interactions between the natural gas grid and the electric grid. Particularly, if the assets of the natural gas grid and the electric grid belong to different owners, these owners would like to maximize their own revenues when they make maintenance scheduling. Therefore, it is inevitable to appropriately schedule maintenance for the natural gas grid and the electric grid.

Considering the interdependency between the natural gas grid and the power grid <cit.>, the issues such as expansion planning and operation in the coupled grid have been re-investigated <cit.>. The steady-state models based on Weymouth equations have been applied in studies on optimal unit commitment with security constraints of the natural gas system <cit.> and optimal power flow of the electric system with the natural gas system <cit.>. To deal with the nonlinear models of pipelines, a piecewise linear method by using the mixed integer programming formulation can be employed <cit.>. In addition, some relaxation-based approaches are proposed to deal with the nonlinear Weymouth equations <cit.>. The above studies mainly focus on the steady-state model. To accurately represent the influences of the natural gas grids, the dynamics of the gas pipeline networks are discussed in <cit.>.

Currently, there are some studies on maintenance scheduling for the power system. To include the deterioration processes of devices, Markov models are introduced <cit.>. In addition to Markov models, some models based on the mixed integer linear programming (MILP) are proposed to schedule maintenance activities on electric devices <cit.>. With the deregulation of the power system, centralized maintenance scheduling is not suitable. Some coordination-based and game-based mechanisms are developed <cit.>. For the natural gas system, condition-based approaches <cit.>, risk-based approaches <cit.>, and tree-based approaches <cit.> are developed to support maintenance scheduling of gas pipelines. However, maintenance scheduling of the integrated natural gas and power systems, especially when the natural gas grid and the power grid are owned by different companies, has been little investigated. In practice, the natural gas grid and the power grid may belong to different companies <cit.>. The company of the natural gas grid owns assets in the natural gas grid, and the company of the power grid owns assets in the power grid <cit.>. When scheduling maintenance, the owners of the natural gas grid and the electric grid both expect to maximize their revenues <cit.>. In addition, there are independent system operators (ISOs) for the coupled system, and they coordinate, control and monitor the operation of the system <cit.>. For different owners of the natural gas grid and the power grid, they have the rights to schedule maintenance for their own assets, and ISOs are in charge of the system operation to ensure high reliability of the systems. Since the two grids may belong to different owners, different sequences of determining maintenance scheduling for different owners may happen, and the sequence of determining maintenance scheduling can impact the revenues of the owners for the natural gas grid and the electric grid. Therefore, we propose a dynamic game-based maintenance scheduling mechanism for the electric and natural gas grids by using a bilevel approach. In the upper level, the different owners of the natural gas grid and the power grid schedule maintenance with the objective to maximize their own revenues. The interactions between different owners are formulated as a dynamic game problem, which is solved by the backward induction algorithm. In the lower level, ISOs dispatch the natural gas grid and the power grid to minimize the loss of power load and gas load with the operating conditions under the maintenance schedules from the different owners. This is formulated as a mixed integer linear programming problem. A piecewise linear approximation with the big-M approach is used to transform the original nonlinear model of the natural gas grid into a mixed integer linear model. A 6-bus system with a 4-node gas grid and a modified IEEE 118-bus system with a 20-node gas grid are used to verify the effectiveness of the proposed model. 

The main contributions are listed as follows. 1) A dynamic game-based maintenance scheduling mechanism for different owners of the electric grid and the natural gas grid is proposed by using a bilevel model. The dynamic game model addresses the sequence of scheduling maintenance for different owners of the natural gas grid and the power grid. The bilevel model deals with that the asset owners determine the maintenance windows of the assets and ISOs determine the system operating conditions. 2) The subgame perfect Nash equilibrium (SPNE) for the owners of the natural gas grid and the electric grid is obtained by using the backward induction algorithm. 3) The influences of maintenance durations and the number of piecewise linear functions on the SPNE are analyzed. Suggestions on maintenance durations are provided.

The remainder of this paper is organized as follows. Section II shows the maintenance scheduling formulation, including the framework of the proposed model, the upper level model and the lower level model. Section III presents the solution, and the case studies are demonstrated in Section IV. The work is concluded in Section V. 



§ MAINTENANCE SCHEDULING FORMULATION

This section shows the formulation of the dynamic game-based maintenance scheduling with a bilevel approach. First, the framework of the proposed model is presented. Second, the upper level model, including the model for the owners of the natural gas grid and the power grid, is introduced. Third, the lower level model for the ISO with the operating constraints is established.


 §.§ Framework of the proposed model

Fig. <ref> shows the framework of the proposed dynamic game-based model, which is a bilevel model. The upper-level model schedules maintenance with the objective to maximize the revenues for the owners of the natural gas grid and the power grid, and the lower-level model calculates the system operating points for the ISO with the objective to minimize the loss of power load and gas load. In this paper, there are the following assumptions: 1) For the system, there is one owner of the natural gas grid and one owner of the power grid. In addition, there is one ISO who is responsible for dispatching the system. 2) Knowledge about one owner is available to the other owner and the ISO. 



In the upper level, possible maintenance can be listed with the scheduling constraints and the scheduling sequence. For possible maintenance, the lower level model is employed to minimize the loss of load with the operating constraints of the natural gas grid and the power grid, and it is a mixed integer linear programming problem. Based on the operating points, the game tree with payoffs can be established. Then, the game tree is solved by using the backward induction algorithm, and SPNE is obtained. SPNE corresponds to the maintenance scheduling for the owners of the natural gas grid and the power grid.    



 §.§ Upper Level Model



  §.§.§ Power Grid Owner's Model

In the upper-level model, the owner of the power grid schedules maintenance activities while keeping a maximum revenue. The objective can be expressed as follows. 

    [ max  ∑_u ∑_t ( C_u,t^P ·P_u,t)_1.a  + ∑_u'∑_t ( C_u',t^P ·P_u',t)_1.b  -;        ∑_u ∑_t ( C_u,t^M ·v_u,t)_1.c  - ∑_l ∑_t ( C_l,t^M ·v_l,t)_1.d  -;                        ∑_u ∑_t ( C_u,t^F ·v_u,t + C_u,t^L ·P_u,t)_1.e  -; ∑_u'∑_t ( C_u',t^F ·v_u',t + C_u',t^L ·P_u',t + C_u',t^S ·o_u',t)_1.f  -;                                           ∑_b ∑_t ( C_b,t^LS·ΔL_b,t)_1.g ]

s.t.

    [  v_l,t - 1 - v_l,t + v_l,t'≤ 1; 1 ≤ t' - (t - 1) ≤ T_l^M,∀ l,t ]
       [  v_u,t - 1 - v_u,t + v_u,t'≤ 1; 1 ≤ t' - (t - 1) ≤ T_u^M,∀ u,t ]
       ∑_t ( 1 - v_l,t) = T_l^M    ∀ l         
       ∑_t ( 1 - v_u,t) = T_u^M    ∀ l         
       ∑_l( 1 - v_l,t) ≤N_t^L,M    ∀ t 
       ∑_u( 1 - v_u,t) ≤N_t^U,M    ∀ t 
       v_l,t, v_u,t∈{ 0,1}  ∀ l,t 
       [               ΔL_b,t,v_u',t,P_u,t,; P_u',t, o_u',t∈{Lower Level Model} ]

where (<ref>.a) and (<ref>.b) show the revenues from power generation, (<ref>.c) is the cost of implementing maintenance on generators, and (<ref>.d) is the cost of implementing maintenance on lines. (<ref>.e) is the operating cost of generators that will be under maintenance during the given time window. It is assumed that the generators to be under maintenance will not participate in unit commitment in the lower-level model. (<ref>.f) is the operating cost of generators that will not be under maintenance during the given time window, and these generators can participate in unit commitment in the lower-level model. (<ref>.g) is the penalty cost due to unserved power load.
(<ref>) is the maintenance duration constraint for the line l, and (<ref>) is the maintenance duration constraint for the generator u.
(<ref>) and (<ref>) ensure that maintenance will be implemented during the given time window, (<ref>) is the constraint of the maximum allowable number of lines under maintenance in one period, and (<ref>) is the constraint of the maximum allowable number of generators under maintenance in one period. (<ref>) is the binary constraint. (<ref>) shows the variables optimized in the lower-level model.

In (<ref>)-(<ref>), the variables v_l,t, v_u,t ∀ l,u,t, which represent the maintenance states, are determined in the upper-level model. This is because the owner of the power grid only determines maintenance windows for the devices. The variables ΔL_b,t,v_u',t,P_u,t, P_u',t, o_u',t ∀ u,u',b,t, which represent the system operating conditions, are determined by the ISO in the lower-level model.



  §.§.§ Natural Gas Grid Owner's Model

In the upper-level model, the objective of the natural gas grid can be expressed as follows. 

    [ max  ∑_w ∑_t ( C_w,t·G_w,t)_10.a  + ∑_s ∑_t ( C_s,t·G_s,t)_10.b  -;  ∑_p ∑_t ( C_p,t^M ·v_p,t)_10.c  - ∑_n ∑_t ( C_n,t^LS·ΔL_n,t)_10.d ]

s.t.

    [  v_p,t - 1 - v_p,t + v_p,t'≤ 1; 1 ≤ t' - (t - 1) ≤ T_p^M,∀ p,t ]
       ∑_t( 1 - v_p,t) = T_p^M ∀ p 
       ∑_p( 1 - v_p,t) ≤N̅_t^P,M ∀ t 
       v_p,t∈{ 0,1} ∀ p,t 
       ΔL_n,t,v_w,t,G_w,t,G_s,t∈{Lower Level Model}

where (<ref>.a) and (<ref>.b) are the revenues for the owner of the natural gas grid. (<ref>.c) is the maintenance cost, (<ref>.d) is the penalty cost caused by unserved natural gas load, (<ref>) is the constraint of  maintenance on pipelines, (<ref>) guarantees that maintenance will be implemented during the given time window, (<ref>) enforces the maximum number of pipelines that can be maintained in one period, (<ref>) is the binary constraint, (<ref>) shows the variables optimized in the lower-level model.

In (<ref>)-(<ref>), the variables v_p,t ∀ p,t, representing the maintenance states, are determined by the owner of the natural gas grid in the upper-level model. The variables ΔL_n,t,v_w,t,G_w,t,G_s,t ∀ n,w,s,t, representing the operating conditions, are determined by the ISO in the lower-level model.



 §.§ Lower Level Model



  §.§.§ Objective function

In the lower-level model, the ISO minimizes the loss of power load and natural gas load while satisfying the operating constraints with the scheduled maintenance from the owners of the natural gas grid and the power grid. The objective of the lower-level model is expressed as follows. 

    min  ∑_b∑_t( C_b,t^LS·ΔL_b,t)  + ∑_n∑_t( C_n,t^LS·ΔL_n,t)



  §.§.§ Constraints

When minimizing the objective function, the operating constraints of the natural gas grid and the electric grid should be satisfied.  


  
Natural gas supply constraints
In each period, the natural gas supply constraints should be satisfied. 

    G_w·v_w,t≤G_w,t≤G_w·v_w,t    ∀ w,t 
       [ - v_w,t - 1 + v_w,t - v_w,t'≤ 0; 1 ≤ t' - (t - 1) ≤ T_w^ON,∀ w,t ]
       [    v_w,t - 1 - v_w,t + v_w,t'≤ 1; 1 ≤ t' - (t - 1) ≤ T_w^OFF,∀ w,t ]
        G_s≤G_s,t≤G_s  ∀ s,t  
        R_s≤G_s,t - G_s,t + 1≤R_s  ∀ s,t

where (<ref>) shows the limit of gas production of each gas well, (<ref>) and (<ref>) show the constraints of on-off states of the gas wells, (<ref>) enforces the storage levels of the gas storages, (<ref>) represents the in-flow and out-flow rates of the gas storages.


  
Natural gas balance at each gas node
Natural gas balance at each gas node should be satisfied.

    [ ∑_w ∈Ω _n^WG_w,t  + ∑_s ∈Ω _n^S( G_s,t - 1 - G_s,t)  + ∑_n' ∈Ω _n^NF_n,n',t;                 - ∑_u ∈Ω _n^G( L_u,t· EF_u)  - ( L_n,t - ΔL_n,t) = 0  ∀ n,t ]
          0 ≤ΔL_n,t≤L_n,t                 ∀ t,n

where (<ref>) enforces the natural gas balance at each node, and (<ref>) denotes the constraint for natural gas load shedding.



  
Natural gas flow constraints
The gas flow in a pipeline in service can be expressed as the nonlinear Weymouth equation (<ref>).

    F_n,n',t·| F_n,n',t| = C_n,n'^2 · (PS_n,t^2 - PS_n',t^2) ∀ n,n',t

A piecewise linear formulation by using the mixed integer programming, as shown in Fig. <ref>, is employed to deal with the Weymouth equation. Substitute PS^2 with π, and the left side of (<ref>) can be approximately expressed as the sum of a group of piecewise linear functions. Each linear function is represented by a slope A, an axis intercept and a binary variable η.

For the pipelines that will not be under maintenance during the given time window, the model can be expressed as follows. 


    [   ∑_k ( A_p',t^k · f_p',t^k + B_p',t^k ·η _p',t^k); = C_n,n'^2( π _n,t - π _n',t)  ∀ t,p', (n,n') ∈ p' ]
       ∑_k η _p',t^k  = 1  ∀ t,p' 
        η _p',t^k ·f_p'^k ≤ f_p',t^k ≤η _p',t^k ·f_p'^k  ∀ k,t,p' 
        F_n,n',t = ∑_k f_p',t^k  ∀ t,p', (n,n') ∈ p'

where the sum of a group of piecewise linear functions in the left side of (<ref>) approximates the term F_n,n',t·| F_n,n',t| in (<ref>).
In Fig. <ref>, there are six piecewise linear functions, i.e., k = { 1,2, ⋯ ,6}. Since the variable η _p',t^k∈{0,1}, (<ref>) ensures that only one linear function will be selected. (<ref>) limits the variable f_p',t^k for the kth linear function. With the constraints (<ref>), (<ref>) and (<ref>), the gas flow in the pipeline n-n' can be expressed as (<ref>). 

For a pipeline that will be under maintenance during the given time window,  its state (i.e., the variable v_p,t) is determined in the upper-level model. The piecewise linear approximation model is shown as follows.

    [ ∑_k ( A_p,t^k · f_p,t^k + B_p,t^k ·η _p,t^k)≤ C_n,n'^2( π _n,t - π _n',t);                                  + ( 1 - v_p,t) ·M^P    ∀ t,p, (n,n') ∈ p ]
       [ ∑_k ( A_p,t^k · f_p,t^k + B_p,t^k ·η _p,t^k)≥ C_n,n'^2( π _n,t - π _n',t);                                  - ( 1 - v_p,t) ·M^P    ∀ t,p, (n,n') ∈ p ]
         η _p,t^k ·f_p^k ≤ f_p,t^k ≤η _p,t^k ·f_p^k  ∀ k,t,p 
         F_n,n',t = ∑_k f_p,t^k  ∀ t,p, (n,n') ∈ p 
         ∑_k η _p,t^k  = v_p,t  ∀ t,p

where (<ref>) and (<ref>) represent the constraints of gas flow in pipelines. By introducing the binary variable v_p,t and a sufficiently large M^P, (<ref>) and (<ref>) are redundant when the corresponding pipelines are under maintenance at t. (<ref>) and (<ref>) have the similar meanings of (<ref>) and (<ref>), respectively. (<ref>) relates the variable η _p,t^k and v_p,t. For example, when the pipeline p at t is off due to maintenance, i.e., v_p,t=0, η _p,t^k for all piecewise linear functions will be zeros. In this case, (<ref>)-(<ref>) are all satisfied. When the pipeline p at t is on, i.e., v_p,t=1, the model is the same as (<ref>) - (<ref>). The binary variable v_p,t is determined in the upper-level model, and the binary variable η _p,t^k is determined in the lower-level model.



  
Natural gas pressure constraints
The pressure of each natural gas node should be within the limit.

    π_n≤π _n,t≤π _n          ∀ n,t 
       π _n',t≤λ _pc·π _n,t        ∀ pc,t,(n,n') ∈ pc

where (<ref>) is the constraint for the pressure. (<ref>) shows the constraint of pressures between the in-coming gas node and the out-coming gas node of a pipeline with a compressor.



  
Power flow constraints
The limits for power flow through lines should be satisfied.

    B_b,b'·( θ _b,t - θ _b',t) = P_b,b',t^L  ∀ t,l', (b,b') ∈ l' 
       | P_b,b',t^L| ≤P_b,b'^L  ∀ t,l', (b,b') ∈ l' 
       [ B_b,b'·( θ _b,t - θ _b',t) - P_b,b',t^L + (1 - v_l,t) ·M^L≥ 0;                                             ∀ t,l, (b,b') ∈ l ]
       [ B_b,b'·( θ _b,t - θ _b',t) - P_b,b',t^L - (1 - v_l,t) ·M^L≤ 0;                                             ∀ t,l, (b,b') ∈ l ]
        | P_b,b',t^L| ≤P_b,b'^L ·v_l,t    ∀ t,l, (b,b') ∈ l

where (<ref>) shows the relation between voltage angles and power flow through lines that will not be under maintenance during the given time window, (<ref>) shows the corresponding limit of power flow. (<ref>) and (<ref>) represent the physical relations between voltage angles and power flow through lines that will be under maintenance during the given time window. (<ref>) is the corresponding limit of power flow.



  
Generator's state constraint When scheduling maintenance, it is necessary to include the on-off constraints of generators. 

    [ - v_u',t - 1 + v_u',t - v_u',t'≤ 0;   1 ≤ t' - (t - 1) ≤ T_u^ON,∀ u',t ]
       [  v_u',t - 1 - v_u',t + v_u',t'≤ 1; 1 ≤ t' - (t - 1) ≤ T_u^OFF,∀ u',t ]
        - v_u',t - 1 + v_u',t - o_u',t≤ 0    ∀ u',t

where (<ref>) denotes the minimum on-time constraint of the generator u', (<ref>) is the minimum off-time constraint of the generator u'. These constraints are used for unit commitment. (<ref>) is the start-up constraint of the generator u'. 



  
Power balance At each time, the power system should satisfy power balance. 

    [ ∑_u ∈Ω _b^UP_u,t  + ∑_u' ∈Ω _b^UP_u',t  - ( L_b,t - ΔL_b,t) +;                          ∑_b' ∈Ω _b^BP_b,b',t^L  = 0    ∀ t,b ]
           0 ≤ΔL_b,t≤L_b,t        ∀ t,b 
          P_u,t = L_u,t· EF_u   ∀ u ∈Ω _n^G,n,t

where (<ref>) enforces power balance at each bus in each time period. (<ref>) is the constraint of load shedding. (<ref>) denotes the relation between natural gas and real power produced from gas-fired units.



  
Phase angle constraint The constraint for the phase angle at each bus, and the constraint for the phase angle difference between two buses on each line should be satisfied. 

    | θ _b,t - θ _b',t| ≤v_l,t·θ^L  + (1 - v_l,t) ·M^θ  ∀ t,l,(b,b') ∈ l 
       | θ _b,t - θ _b',t| ≤θ^L  ∀ t,l',(b,b') ∈ l'

where the constraint (<ref>) shows the phase angle difference limit on the line that will be maintained during the given time window, and (<ref>) shows the phase angle difference limit on the line that will not be maintained during the given time window.



  
Ramp-up and ramp-down constraints The generators should satisfy the ramp-up and ramp-down constraints.

    P_u·v_u,t≤P_u,t≤P_u·v_u,t    ∀ u,t 
       [ P_u,t - P_u,t - 1≤ (2 - v_u,t - 1 - v_u,t) ·P_u +;             (1 + v_u,t - 1 - v_u,t) ·R_u    ∀ u,t ]
       [ P_u,t - 1 - P_u,t≤ (2 - v_u,t - 1 - v_u,t) ·P_u +;             (1 - v_u,t - 1 + v_u,t) ·R_u    ∀ u,t ]

where (<ref>) is the capacity limits of the generator u, (<ref>) and (<ref>) are ramp-up and ramp-down constraints of the generators u. When v_u,t=1 and v_u,t-1=0, the constraints become P_u,t - P_u,t - 1≤R_u and P_u,t - 1 - P_u,t≤R_u, and these two constraints are the conventional ramping limits. When v_u,t=1 and v_u,t-1=0, the constraints can be rewritten as P_u,t≤P_u and -P_u,t≤P_u +2R_u. Associated with (<ref>), we can conclude P_u,t=P_u. This means that the generation of the generator u is P_u after it is restarted. When v_u,t=0 and v_u,t-1=1, we have P_u,t-1=P_u and P_u,t=0. It means the generation of the generator u will be dispatched to P_u at t-1 when the generator u should be offline at t. For the generators that will not be under maintenance during the given time window, the ramp-up and ramp-down constraints are similar with (<ref>)-(<ref>).



§ SOLUTIONS

This section presents the solution procedures to obtain maintenance plans for the owners of the natural gas grid and the power grid. The solution procedures include 1) establishing the game tree, 2) calculating payoffs of each path in the game tree, and 3) obtaining SPNE by using the backward induction algorithm.  




 §.§ Game Tree Establishment

In the upper-level model, the owners of the natural gas grid and the power grid schedule their own maintenance. With the constraints (<ref>)-(<ref>) and the constraints (<ref>)-(<ref>), a game tree representing possible sequential decisions can be established. Since the decision variables in (<ref>)-(<ref>) and (<ref>)-(<ref>) are discrete, the established game tree is a finite game tree. 

For example, the owner of the natural gas grid can make maintenance scheduling A and B, and the owner of the power grid can make maintenance scheduling C and D. When the owner of the natural gas grid first makes maintenance scheduling, the game tree is illustrated in Fig. <ref>. DN_1 is the decision node for the owner of the natural gas grid. DN_2 and DN_3 are the decision nodes for the owner of the power grid.




 §.§ Payoff Calculation

For each path in the game tree, i.e., the scheduled maintenance, the ISO dispatches the system to ensure the high reliability and minimizes the loss of power load and natural gas load. The variables v_l,t, v_u,t, v_p,t in each path come from the upper-level model, i.e., the owners of the power grid and the natural gas grid. Therefore, the lower-upper model for each path can be expressed as 

    Obj.   (<ref>) 
        s.t.     (<ref>)-(<ref>) 
             Given   v_l,t, v_u,t, v_p,t  ∀ l, p, t

where (<ref>) is a mixed integer linear program, which is solved with the CPLEX solver in this research. After solving (<ref>), the payoffs of the owners of the natural gas grid and the power grid for each path can be obtained by using (<ref>) and (<ref>). In this case, a finite game tree with payoffs can be established.


 §.§ Game Tree Solution

Backward induction is a deduction process operating backwards from the end of the game tree to determine a sequence of optimal activities for different players at decision epochs. The optimal decision at each decision node can be expressed as follows.

    d_h_i,e^ *  = max_d_h_i,e∈D_h_i,eF_i( ν (h_i,e),d_h_i,e,ζ ^ * (ℵ (d_h_i,e)))  ∀h_i,e
       ζ ^ * (h_i,e) = {d_h_i,e^ * ,ζ ^ * (ℵ (d_h_i,e^ * ))}  ∀h_i,e

where (<ref>) shows the optimal decision at the decision node h_i,e, and (ν (h_i,e),d_h_i,e,ζ ^ * (ℵ (d_h_i,e))) constructs a path from the initial decision node to a terminal decision node. (<ref>) shows the optimal path from the decision node h_i,e to the terminal decision node. By solving the established game tree in sections III.A and III.B with (<ref>) and (<ref>), maintenance plans corresponding to SPNE can be obtained.



§ CASE STUDIES

In this section, two test systems are used to verify the proposed model. The first system is a 6-bus power grid with a 4-node natural gas grid, and the second system is a modified IEEE 118-bus power grid with a 20-node natural gas grid. The cases are tested in MATLAB 2017a using the CPLEX 12.6 solver on computers with 3.1 GHz i5 processors and 8 GB RAMs.


 §.§ 6-bus Power Grid with 4-Node Natural Gas Grid



  §.§.§ Data description

The 6-bus power grid and the 4-node natural gas grid refer to <cit.> and <cit.>. The integrated system is shown in Fig. <ref>. The forecast power load curve during the given time window is shown in Fig. <ref>.






During the given time window, the lines 1-4 and 3-6 in the power grid will be under maintenance, and maintenance activities need 22 and 24 time intervals, respectively. In each time interval, only one line can be under maintenance. Their maintenance costs are $500 and $600 per time interval. In addition, maintenance on the pipeline 2-3 in the natural gas grid should be implemented with $500 per time interval. The maintenance activities need 31 time periods.









  §.§.§ Maintenance corresponding to SPNE

The possible maintenance activities on lines in the power grid are listed in Table <ref>, and the possible maintenance activities on the pipelines in the natural gas grid are listed in Table <ref>. 

Fig. <ref> (a) shows the game tree when the owner of the power grid first schedules maintenance. A blue path denotes the best response of the owner of the natural gas grid to a maintenance plan scheduled by the owner of the power grid. For example, if the owner of the power grid has the maintenance plan m_l,1, the best response of the owner of the natural gas to m_l,1 is m_p,5. With m_l,1 and m_p,5, the payoffs of the owners of the natural gas grid and the power grid are $1.3665×10^8 and $3.9231×10^8, respectively. If the owner of the power grid has the maintenance plan m_l,3, the best response of the owner of the natural gas grid to m_l,3 is m_p,13. With m_l,3 and m_p,13, their payoffs are $1.6762×10^8 and $3.9924×10^8, respectively. Results show that the payoffs are different with diverse maintenance and the responses. Since the two owners expect to maximize their own payoffs, they should take into full account each other's maintenance. The backward induction method is used to obtain the optimal strategies corresponding to SPNE for the two sides. For the scenario in Fig. <ref> (a), the optimal strategies corresponding to SPNE is m_l,7 and m_p,17. The payoffs for the owners of the power grid and the natural gas grid are $4.1072×10^8 and $1.5226×10^8, respectively.



Fig. <ref> (b) shows the game tree when the owner of the natural gas grid first schedules maintenance. The red path represents the best response of the owner of the power grid to a maintenance plan scheduled by the owner of the natural gas grid. For example, if the owner of the natural gas grid has the maintenance scheduling m_p,1, the best response of the owner of the power grid to m_p,1 is m_l,12. With the backward induction method, the optimal strategies, which correspond to SPNE, for the two sides are m_p,4 and m_l,12. The payoffs of the owners of the power grid and the natural gas grid are $4.1051×10^8 and $1.3909×10^8, respectively.

The payoffs corresponding to SPNE in Fig. <ref> (b) are both smaller than those in Fig. <ref> (a). 
This is because the strategy with a larger payoff of one owner may be excluded from the optimal strategy when the other owner makes the maintenance plan. For example, m_l,7 and m_p,17 in Fig. <ref> (a) correspond to SPNE when the owner of the power grid first schedules maintenance. In Fig. <ref> (b), m_l,12 rather than m_l,7 is the best response to m_p,17 since $4.1207×10^8 is greater than $4.1072×10^8.  
Based on the above analysis, we can conclude that different sequences have great influences on the optimal strategies, i.e., SPNE, and the payoffs.



Fig. <ref> (a) and (b) show the fitting surfaces of the payoffs. A_1 and A_2 represent the payoffs corresponding to SPNE for the power grid and the natural gas grid when the owner of the power grid first schedules maintenance.
B_1 and B_2 represent the payoffs corresponding to SPNE for the power grid and the natural gas grid when the owner of the natural gas grid first schedules maintenance.
The results show that SPNE may not have the largest payoffs. This is because one strategy with the largest payoff for one owner may be excluded when the other owner makes maintenance plans. Due to this reason, SPNEs are located at different positions of the fitting surfaces of the payoffs, e.g., at the local peaks A_1/A_2/B_2 and the non-local peak B_1. To further analyze the position of SPNEs, 400 scenarios with different cost data are implemented, and we get 800 SPNEs in consideration of different sequences of the owners. For these SPNEs, there are 591 SPNEs locating at the local peaks, i.e., about 74% of SPNEs locate at the local peaks.

Fig. <ref> shows the average load shedding of each path in the game tree for different scenarios. The x-axis represents the scenario, and the y-axis represents the average load shedding. Different color bars in each scenario represent the different paths in the game tree. Each black dash-dotted line marks the path corresponding to SPNE in each scenario. Some scenarios (e.g., the scenarios 2, 6 and 9) have SPNEs with the minimum loss of load, and the others (e.g., the scenarios 1, 3, 4, 5, 7, 8, and 10) have SPNEs with the non-minimum loss of load. One critical reason for this is that the strategy with the minimum loss of load may be excluded when the other player makes maintenance plans.





  §.§.§ Influences of maintenance duration
  
Fig. <ref> (a) and (b) show the payoffs corresponding to  SPNEs with different maintenance durations. The x-axis and the y-axis represent the maintenance durations of the line L_14 and the pipeline PL_23, respectively. The z-axis represents the payoffs. The results show that the payoffs corresponding to SPNEs gradually increase with the shorter maintenance durations. We can interpret this pattern qualitatively as follows. 

	
  * When the maintenance duration of the line L_14 decreases, the maintenance cost for the line can be reduced. Furthermore, the loss of load could be reduced due to a larger power transport capability, and in consequence the generation revenue increases.
	
  * When the maintenance duration of the pipeline PL_23 decreases, the maintenance cost for the pipeline can be reduced, and the loss of gas load could be reduced. In addition, the generation from the gas-fired units can increase due to the larger gas transport capacity, and in consequence the loss of load can be reduced.  


Based on the results and the analysis, it is concluded that the owners of the natural gas grid and the power grid should shorten the maintenance durations when they would like to obtain SPNE with higher payoffs.





  §.§.§ Influences of different piecewise linear functions

Fig. <ref> shows the relative errors of the payoffs corresponding to SPNE for the power grid (a) and the natural gas grid (b) when using different piecewise functions. The x-axis and the y-axis represent the number of piecewise functions and the relative error, respectively. The different color bars represent scenarios with different cost data. The results with fifteen piecewise functions are used as reference values. The results are more accurate with more piecewise functions, and nine piecewise functions can achieve the results with high accuracy.

Furthermore, the payoffs of the owner of the natural gas grid are more sensitive to the number of piecewise functions compared to the payoffs of the owner of the power grid. For example, the average relative error of the payoff is about 1.4% for the power grid, and about 28% for the natural gas grid when using three piecewise functions. When using nine piecewise functions, the average relative error of the payoff is about 0.25% for the power grid, and about 1% for the natural gas grid.     



 


  §.§.§ Influences of maintenance on different components

Maintenance on generators may need to be scheduled associated with maintenance on lines during the given time window. To compare the results, the line L_36 in the above case is replaced by the generator G_2 that needs maintenance, and the other settings remain unchanged. We compare the results when the owner of the power grid first makes maintenance scheduling. Table <ref> shows the comparison results. The scenario S_1 is the original case, and the scenario S_2 is the updated case with the generator G_2 to be under maintenance.



The payoff of the scenario S_2 corresponding to the equilibrium point for the power grid ($3.4550 ×10^8) is smaller than that of the scenario S_1 ($4.1072 ×10^8). The main reason for this is that the loss of load increases when the generator G_2 is under maintenance.

The payoff of the scenario S_2 corresponding to the equilibrium point for the natural gas grid ($1.7761 ×10^8) is larger than that of the scenario S_1 ($1.5226 ×10^8). This is because the gas-fired units G_1 and G_3 need more natural gas for electric power to reduce the loss of load when the generator G_2 is under maintenance, and the increased natural gas production increases the revenues of the natural gas grid.





 §.§ 118-bus electric grid with 20-node gas grid



  §.§.§ Data description

The data for the power grid and the natural gas grid refer to <cit.> and <cit.>, respectively. Table <ref> shows the gas-fired units and the corresponding gas nodes in the natural gas grid. During the given time window (48 time intervals), three transmission lines 69-47, 69-70 and 69-75 will be maintained with 24 time intervals, and two pipelines 10-14 and 10-11 will be maintained with 23 time intervals. The maximum numbers of lines and pipelines that can be maintained in one period are 2 and 1, respectively. 





  §.§.§ Simulation Results

This section shows the maintenance scheduling (the equilibrium) for the two owners with different decision-making sequences. Table <ref> shows the maintenance scheduling and the payoffs when the owner of the power grid first makes the maintenance plan. Table <ref> shows the maintenance scheduling and the payoffs when the owner of natural gas grid first makes the maintenance plan. The results show that different decision making sequences result in different SPNEs, and therefore cause different maintenance plans. 





We shorten the maintenance durations of the line L_69-47 and the pipeline L_10-14 to 20 and 19, respectively. Table <ref> shows the payoffs corresponding to the equilibrium points. When the owner of the power grid first makes the schedule, the payoffs for the owners of the power grid and the natural gas grid are $52.4254×10^8 and $6.8107×10^8, respectively. They are larger than the scenario in Table <ref>. When the owner of the natural gas grid first makes the schedule, the payoffs for the owners of the power grid and the natural gas grid are $52.4172×10^8 and $6.8211×10^8, respectively. They are larger than the scenario in Table <ref>. The results show that the payoffs corresponding to the equilibrium point increase when the owners shorten the maintenance durations. This conclusion is consistent with that in Section IV.A.3.





 §.§ Discussion

In this paper, the natural gas grid and the power grid are coupled via natural gas-fired units. In addition to the gas-fired units, there are some other ways such as energy hubs for receiving, sending, converting and storing different types of energy, and these energy hubs are also critical to the natural gas system and the power system. There are many research studies on the steady-state models of the energy hubs <cit.>. When an energy hub is included in the natural gas grid, its steady-state model can be expressed as O=C×I, in which I and O are vectors of energy at input and output ports, and C is the coupling matrix that describes the conversion of energy from the input to the output. The elements in C represent the converter efficiencies and the hub internal topology <cit.>. This steady-state model has a similar form as the relation between natural gas and electric power, i.e., the constraint (<ref>). Therefore, the the model of the energy hub can be easily integrated in the proposed model.

Currently, we mainly consider maintenance on power lines, gas pipelines and the generating units. We would like to emphasize that the proposed dynamic game-based model is suitable for other components in the system. The models for the other components can be established by analogy with lines, pipelines and generating units. For example, the maintenance model for a transformer can be established by analogy with the maintenance model for the line, and the maintenance model for a gas well can be established by analogy with the maintenance model for the generating unit.

When modeling the natural gas system in this paper, a piecewise linear approximation approach is used to transform the nonconvex and nonlinear Weymouth gas flow equations into a series of piecewise linear functions. Since maintenance scheduling is a planning problem, appropriate piecewise linear functions can satisfy the accuracy requirements. To further improve the accuracy, some state-of-the-art methods based on the second-order conic relaxation <cit.> can be used to deal with the Weymouth equations. When using the second-order conic relaxation, we just need to replace the piecewise linear model for Weymouth equations by the second-order conic relaxation, and the optimization model in each game tree becomes a mixed integer nonlinear programming (MINLP) model.

For a large scale system, it may need a long computation time to obtain the maintenance plans. However, maintenance scheduling belongs to a planning topic, it does not require online calculation. In addition, one critical point for power systems and natural gas grids is to ensure a high reliability level. To this end, the number of transmission lines/pipelines that can be out of service in the same time period is limited <cit.>. Meanwhile, the number of paths is also constrained by the continuous minimum periods for maintenance activities. Considering the above practical points, i.e., the constraints (2)-(8), the number of paths is limited, particularly when the number of all transmission lines/pipelines to be under maintenance with a given time window is limited. Furthermore, many simulation platforms such as Rescale <cit.>, IBM Could <cit.> and Nimbix <cit.> with high performance computing (HPC), can be used to solve the proposed model efficiently.

Some techniques can be used to reduce the computation time. First, parallel computing can be employed when constructing the game tree since each path in the game tree are independent <cit.>. Second, some methods, e.g., the parallel branch & bound method <cit.> and the modified Benders decomposition method <cit.>, can be used to accelerate the convergence of the solution for each path. 



§ CONCLUSION

This paper proposes a dynamic game-based maintenance scheduling mechanism for natural gas and power grids by using a bilevel approach. In the upper-level model, the different owners of the power grid and the natural gas grid schedule maintenance with the objective to maximize their own revenues. This is modeled as a dynamic game problem, which is solved by the backward induction algorithm. In the lower-level model, the operating point under the scheduled maintenance is calculated. This is modeled as a mixed integer linear programming problem. For the model of natural gas grids, the piecewise linear approximation associated with the big-M approach is used to transform the original nonlinear model into a mixed integer linear model. 

The proposed model was validated by two test systems. The major findings are as follows. 1) The subgame perfect Nash equilibrium for the power grid and the natural gas grid may not have the maximum payoffs, however, it has a high probability to locate a local peak of the payoff surface. 2) The maintenance duration has a great impact on the payoff corresponding to the subgame perfect Nash equilibrium. When the owners of the power grid and the natural gas grid expect to obtain an equilibrium point with the higher payoffs, it is suggested that they should shorten the maintenance durations. 3) The payoff corresponding to the equilibrium for the owner of the natural gas grid has a high sensitivity to the number of piecewise functions compared to the payoff corresponding to the equilibrium for the owner of the power grid.

This work can be extended to consider the integration of renewables. Furthermore, some state-of-the-art methods based on the second-order conic relaxation can be used to deal with the Weymouth equations, and the optimization model in each game tree can be established as a mixed integer nonlinear programming (MINLP) model.





















IEEEtran




	


















