1 Introduction

The goal of this paper is to establish a mathematical model for analyzing long-term infrastructure investment decisions in a deregulated electricity market. To this end, several modeling challenges need to be addressed. In order to keep a concrete ground for discussion, we focus on the United States as a special case of deregulated market. First of all, a power supply system often involves non-cooperative behaviors of multiple decision entities. For example, in the United States there are multiple generation companies supplying electricity to a region’s electricity grid, which is often operated by a separate non-profit Independent System Operator (ISO). ISO is in charge of coordinating, controlling and monitoring the operation of the electrical system in order to keep stability and efficiency of the network and instantaneously balance supply and demand (CalISO 2013). Capturing the interactive behaviors of different system players simultaneously requires modeling techniques beyond conventional optimization approaches based on single decision entity. Secondly, the physical infrastructure for producing and delivering energy are interdependent due to their spatial and functional correlations (Rinaldi et al. 2001; Abrell and Weigt 2012), which requires a network-based modeling framework to capture the spatiality of supplies/demands and the transmission network connecting them (Leuthold et al. 2012). As demonstrated by Hobbs et al. (2008), inclusion of transmission network constraints may result in significantly different predictions on generators’ behaviors in a competitive market. Coping with uncertainty is another major challenge in long term planning, especially considering the evolvement of technologies and demand in the future. Recently, there are many stochastic models developed for energy market operations, including decisions on unit commitment, energy production, storage, and flow transmission (Abrell and Kunz 2015; Conejo et al. 2010). However, uncertainty issue has not been well incorporated into long-term infrastructure planning of a competitive power market despite of its importance as identified in IEA (2006) and fruitful results engaging stochastic, robust, and flexible design reported in the general infrastructure network design literature (Melese et al. 2016; Fan and Liu 2010; Li et al. 2011; Do Chung et al. 2011; Liu et al. 2009).

The electricity market in the United States is generally considered as an oligopoly market, even though the levels of market competitiveness vary by regions (Bushnell et al. 2007). Depending on the decision variables and anticipation of rivals’ reaction (Day et al. 2002), an US electricity market is often modeled based on one of the following: in a Cournot competition (Cournot and Fisher 1897), each generator submits a fixed supply quantity; and in a Supply Function Equilibrium (SFE), each generator submits a production function (i.e. available production quantity as a function of price). It can be shown that if firms know exactly the market realization, SFE and Cournot models yield the same solution (Willems et al. 2009). The advantage of Cournot models is their simplicity and therefore can be integrated with more complex market and system settings (Willems et al. 2009; Hu et al. 2004; Metzler et al. 2003). However, Cournot model is known to be sensitive to demand parameters. SFE models on the other hand provide more flexibility in addressing varying demand conditions (Day et al. 2002). Based on one of these assumptions, researchers have provided in-depth analyses on the impacts of market competition (Hobbs et al. 2000; Hobbs and Pang 2007) and transmission network constraints (Hobbs et al. 2008) on power markets. Stochastic oligopolistic models have also been developed to analyze the operation of power markets under demand and cost uncertainties (Genc et al. 2007; Pineau and Murto 2003). All these studies focus on the operational aspects of a power market with fixed infrastructure and do not consider investment decisions on the physical infrastructure.

With wholesale electricity market deregulated, traditional capacity expansion models developed for regulated firms, such as Murphy et al. (1982), became inadequate, and studies dealing with both investment and operations in an oligopolistic electricity market were critically needed (Kagiannas et al. 2004). A series of studies have been developed based on game theoretic models and multi-agent based simulation (Wogrin et al. 2011). One of the main benefits of game-theoretic models is their capability to capture strategic behaviors of each player when making long-term investment decision (Ventosa et al. 2002; Murphy and Smeers 2005). In a closed-loop model, investment decisions and market operation decisions are assumed to happen in separate stages. Typically a bi-level model is used, with upper level focusing on investment decision and the lower level on daily operation (i.e. generation decision) under given capacities. This type of models can also be categorized as an Equilibrium Problem with Equilibrium Constraints (EPEC) or Mathematical Programming with Equilibrium Constraints (MPEC), for which existence and uniqueness of equilibrium solutions are not always guaranteed (Ralph and Smeers 2006). In an open-loop model, investment and generation decisions are assumed to be made simultaneously. This simplification significantly reduces computation difficulty, and has a real implication: forward contract (Ventosa et al. 2002; Murphy and Smeers 2005), even though it weakens the ability to capture possible market power of players’ first-stage investment decisions on short-term markets. In this paper, we adopt an open-loop approach. Readers may refer to Wogrin et al. (2013) for more discussion on open vs. closed loop models.

Considering non-cooperative games on a network structure adds more complexity. In the literature on power generation capacity expansion in oligopolistic markets, only a few studies explicitly model the transmission and location effects. In (Kazempour and Conejo 2012), a stochastic MPEC model is developed with the upper level focusing on a strategic player’s investment decision and the lower level capturing the ISO’s electricity dispatch problem. In that model, the rivals do not participate in competition on generation capacities as their investment decisions are treated as model input instead of decision variables. In Kazempour et al. (2013), a deterministic EPEC model is developed for modeling capacity expansion decisions of rival investors considering transmission network constraints. There are also studies approaching from an energy supply chain perspective, in which a detailed transmission network is replaced by direct links between generators and demands. For example, (Liu and Nagurney 2011) proposed an analytical model for energy firm merging and acquisition through supply chain network integration. In addition, there are also supply-chain-based studies focusing on the operational issues without considering the strategic planning of infrastructure, such as integration of renewables with other fuel markets (Matsypura et al. 2007; Nagurney and Matsypura 2007; Liu and Nagurney 2009) and a general closed-loop supply chain equilibrium model (Hamdouch et al. 2016).

In summary, little work has been reported in the literature for modeling generation infrastructure planning considering all three challenges: uncertainty, infrastructure interdependency, and oligopoly competition. In this paper, we establish a stochastic multi-agent optimization model that supports strategic infrastructure planning in an oligopolistic power market. In the proposed model, uncertain parameters are described by a discrete set of scenarios and their associated probabilities. Each investor aims to maximize the expected total profit by choosing the best first-stage investment decision and the second-stage scenario-dependent generation decisions. The ISO dispatches electricity from the generators to the demands to maximize consumer surplus while satisfying the transmission network constraints and the market clearing conditions. A system equilibrium is achieved when all agents solve their problems optimally.

The remaining part of this paper is organized as follows. In Section 2, we first introduce a general stochastic multi-agent modeling framework, which is an extension of the classic single-player two-stage stochastic programming to multi-decision-maker cases. We then describe the behavior of each party involved in the power grid, and give specific assumptions and formulation of the proposed model. In Section 3, we demonstrate how the original energy problem may be reformulated and converted to multiple user-equilibrium traffic network assignment problems. In Section 4, we present numerical results and draw planning and policy implications. The last section concludes the paper with insights, discussions, and future extensions.

2 Mathematical Model and Analyses

2.1 A Stochastic Multi-agent Optimization Modeling Framework

The research question is stated as: How should energy investors strategically plan their production infrastructure (where and at what capacities to build their production facilities), to ensure long-term economic benefit while integrating with the existing power grid?

Even though our emphasis is on the strategic planning of production infrastructure, the cost-effectiveness of a planning decision depends on how the system is likely to be operated afterwards. To model the planning and operational stages in an integrated framework, one should recognize the very distinguishable natures of the two types of decisions against uncertainty, which may be related to demand, supply, and technology. At this point, let us use a general notation ξ to represent the uncertain vector. We assume ξ follows a discrete probability distribution, described by a set of discrete scenarios and associated probabilities. Planning decisions, such as infrastructure setup, are usually made before future uncertainty is revealed and are difficult to readjust once implemented. On the other hand, operational decisions such as electricity production and dispatching quantities can be adjusted based on the actual realization of uncertain parameters (for example, the actual demand or a more accurate hour-ahead demand forecast). This feature fits well in a stochastic programming framework (Louveaux 1986; Birge and Louveaux 2011), which recognizes the non-anticipativity of planning decisions while allowing recourse for operational decisions.

The classic two-stage stochastic program for a single decision maker, in the simplest form, may be presented as follows (Birge and Louveaux 2011):

$$\begin{array}{@{}rcl@{}} && \underset{\boldsymbol{x}}{\text{minimize}} \qquad\qquad\qquad f(\boldsymbol{x}) + \text{E}_{\xi}\left[ Q(\boldsymbol{x}, \xi)\right] \end{array} $$
(1a)
$$\begin{array}{@{}rcl@{}} && \text{subject to} \qquad\qquad\qquad \boldsymbol{x} \in F \end{array} $$
(1b)
$$\begin{array}{@{}rcl@{}} && \qquad\qquad\qquad\qquad\qquad Q(\boldsymbol{x}, \xi) = \inf_{\boldsymbol{y}}\left\{ g(\boldsymbol{x}, \boldsymbol{y}, \xi) | \boldsymbol{y} \in G(\boldsymbol{x}, \xi)\right\} , \end{array} $$
(1c)

where x represents the planning-stage decision, and y the operational decision, which depends on the choice of planning decision and the actual realization of the uncertain parameters ξ. The objective is to minimize the first-stage planning cost, f(x), plus the expected value of the second-stage operational cost, Q(x,ξ), subject to the feasibility constraints of x and y.

In our problem, each decision entity makes her own decision, but needs to simultaneously account for other decision entities’ behaviors given the interdependence among them. For example, too much electricity generation at a local point may increase transmission congestion, which could affect all parties in the power system. Note that even though the decision entities are interdependent, they are assumed non-cooperative in this paper. Readers who are interested in modeling coordination of generators in a competitive market may refer to (Csercsik 2015). Using a two-player problem as an example, the above formulation (1a ∼1c) may be extended to the following:

$$\begin{array}{@{}rcl@{}} &&(\boldsymbol{x}_{1}, \boldsymbol{y}_{1}) = \arg\min_{\boldsymbol{x}_{1}, \boldsymbol{y}_{1}}\left\{ f_{1}(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}) + \text{E}_{\xi}\left[ g_{1}(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \boldsymbol{y}_{1}, \boldsymbol{y}_{2}, \xi)\right]\right\} \\ &&(\boldsymbol{x}_{2}, \boldsymbol{y}_{2}) = \arg\min_{\boldsymbol{x}_{2}, \boldsymbol{y}_{2}}\left\{ f_{2}(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}) + \text{E}_{\xi}\left[ g_{2}(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \boldsymbol{y}_{1}, \boldsymbol{y}_{2}, \xi)\right]\right\} \\ &&\text{s.t.} \qquad (\boldsymbol{x}_{1}, \boldsymbol{x}_{2}) \in F \qquad \text{and} \qquad (\boldsymbol{y}_{1}, \boldsymbol{y}_{2}) \in G(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \xi), \end{array} $$

where x i and y i (ξ) represent the planning decision and the operational decision of player i (i=1,2), respectively; and f i and g i are the first-stage and second-stage costs of player i, respectively. Each player aims at minimizing her own total expected cost, i.e. the planning plus the expected operating cost. Note that y i (ξ) is ξ-specific, but for brevity, we write it as y i . Also, for generality, we denote f i as a function of the planning decisions of both players, which may be simplified to f i (x i ) in many cases. This problem may be classified as a stochastic multi-agent optimization problem, for which new research endeavors are being pursued to better understand the analytical and numerical properties (Jofre and Wets 2014).

2.2 Detailed Formulation for Each Decision Entity

2.2.1 Modeling the Decision of Electricity Generation Companies

In this study, we assume the generators follow an open-loop Cournot competition. A new energy generator that is entering the system has two types of decisions to make. During the planning stage, it decides where and at what capacity to invest its production facilities. At the operational stage, it chooses its best production strategy. This generator makes all these decisions to maximize the expected total profit while taking into account the decisions of other entities in the system. For each generation Firm ∀i∈I:

$$\begin{array}{@{}rcl@{}} \underset{{g_{i}^{j}}(\boldsymbol{\xi}), {c_{i}^{j}}}{\text{maximize}} &&- {\sum}_{k \in K}{\sum}_{j \in J_{k}} \phi_{c} ({c_{i}^{j}} ) \!+ \mathrm{E}_{\boldsymbol{\xi}} \left\{ {\sum}_{k \in K}^{}{{\sum}_{j \in J_{k}}^{}{ \left[ \rho_{k} (\boldsymbol{\xi}){g_{i}^{j}}(\boldsymbol{\xi}) \,-\, \phi_{g} ({g_{i}^{j}}(\boldsymbol{\xi}), \boldsymbol{\xi} ) \right] }}\right\} \end{array} $$
(2a)
$$\begin{array}{@{}rcl@{}} \text{subject to} &&{g_{i}^{j}}(\boldsymbol{\xi}) \leq {c_{i}^{j}}, \; \forall j \in J_{k}, k \in K, \boldsymbol{\xi} \in {\Xi}; \end{array} $$
(2b)
$$\begin{array}{@{}rcl@{}} && {g_{i}^{j}}(\boldsymbol{\xi}) \geq 0, \; \forall j \in J_{k}, k \in K, \boldsymbol{\xi} \in {\Xi}; \end{array} $$
(2c)
$$\begin{array}{@{}rcl@{}} && {c_{i}^{j}} \geq 0, \; \forall j \in J_{k}, k \in K. \end{array} $$
(2d)

where:

J k :

: set of candidate investment locations connecting to access pointFootnote 1 k, indexed by j;

K :

: set of access points, indexed by k;

I :

: set of companies, indexed by i;

\({c_{i}^{j}}\) :

: added capacity at location j of firm i;

\({g_{i}^{j}}\) :

: production quantity by firm i at location j ;

ρ k :

: ISO’s electricity purchasing price at each accessing point k;

ϕ c (⋅):

: total capital cost function with respect to facility capacity;

ϕ g (⋅):

: total production cost function with respect to generation quantity and scenario;

ξ :

: vector of uncertain parameters, whose support is denoted by Ξ.

Note that throughout the entire paper, we denote vectors in lowercase bold font. The objective function (2a) maximizes the total profit of each firm, which is the total revenue minus the total capital and production costs. The decision variables include the capacity and generation amount at each potential production location. We assume a uniform nodal price (Locational Marginal Price), thus the total revenue is calculated by \({\sum }_ {k \in K}^{}{\sum }_{j \in J_{k}}^{} \rho _{k} {g_{i}^{j}}\) . Constraint (2b) ensures that the total electricity generated at a production facility does not exceed its production capacity. Note that for some renewable technologies such as solar or wind, the right-hand-side of constraint (2b) may be attached with a weather-related factor to reflect its effective capacity. The rest are non-negative restrictions. Note that to keep consistent time scale, we treat all agents’ problems at an hourly basis.

2.2.2 Modeling the Decision of Independent System Operator (ISO)

The ISO decides the wholesale price and transmission flow of each transmission line to balance electricity supply and demand in the network instantaneously. Considering the non-profit nature of ISO, we set its goal as to maximize total social welfare. To capture congestion effect of transmission lines, we assume that transmission cost is a monotone increasing function of the transmitted flow quantity, which is a similar treatment as in Hearn and Yildirim (2002). Denote the transmission network by \(\mathcal {G} = (\mathcal {N}, \mathcal {V})\) , where \(\mathcal {N}\) is the set of nodes (indexed by n) and \(\mathcal {V}\) is the set of links (indexed by a). Electricity from a supply (origin) node to a demand (destination) node is modeled as an O-D flow. Since ISO’s decisions are operational, these can be adjusted based on the actual realization of future uncertainty. This means that all decision variables of ISO are scenario dependent, but for brevity, we do not carry ξ in the formulation below. ISO’s problem, in a given scenario, is formulated as:

$$\begin{array}{@{}rcl@{}} \underset{\boldsymbol{x}, \boldsymbol{t}}{\text{minimize}}&& \qquad\qquad{\phi_{t}}(\boldsymbol{v})^{T}\boldsymbol{v} +{\sum}_{i \in I} {\sum}_{k \in K}^{}{\sum}_{j \in J_{k}}^{}{\phi_{g}}({g_{i}^{j}}) - {\sum}_{k\in K}{\int}_{0}^{d_{k}} w_{k}(s) \mathrm{d}s \end{array} $$
(3a)
$$\begin{array}{@{}rcl@{}} \text{subject to}&& \qquad\qquad \boldsymbol{v} = {\sum}_{q \in Q} \boldsymbol{x}^{q}, \end{array} $$
(3b)
$$\begin{array}{@{}rcl@{}} && \qquad\qquad A\boldsymbol{x}^{q} = t^{q} E^{q}, \; \forall q \in Q, \end{array} $$
(3c)
$$\begin{array}{@{}rcl@{}} (\boldsymbol{\rho})&& \qquad\qquad {\sum}_{q \in Q} t^{q}E^{q +} = \boldsymbol{g}, \end{array} $$
(3d)
$$\begin{array}{@{}rcl@{}} && \qquad\qquad {\sum}_{q \in Q} t^{q}E^{q -} = \boldsymbol{d}, \end{array} $$
(3e)
$$\begin{array}{@{}rcl@{}} && \qquad\qquad \boldsymbol{x}^{q} \geq 0 , \; \forall q \in Q, \end{array} $$
(3f)
$$\begin{array}{@{}rcl@{}} && \qquad\qquad t^{q} \geq 0 , \; \forall q \in Q. \end{array} $$
(3g)

where:

v :

: aggregated link flow vector. Each element corresponds to a link;

t :

: O-D flow vector. Each element corresponds to an O-D pair;

ϕ t (⋅):

: transmission cost function, which depends on link flow;

ρ :

: wholesale price vector. Each element corresponds to a node;

g :

: electricity supply vector. The j th element corresponds to the total energy supplied by all companies at node j, that is \(g_{j}={\sum }_{i \in I} {g_{i}^{j}}\);

x q :

: link flow vector associated with OD pair q. Each element corresponds to a link ;

d :

: electricity demand vector. Each element corresponds to a node;

d k :

: total electricity demand at node k;

w k (⋅):

: inverse demand function at node k;

A :

: node-link incidence matrix, whose rows correspond to nodes and columns correspond to links, with +1 indicates the starting node of a link and -1 the ending node.

Q :

: set of O-D pairs, indexed by q;

t q :

: O-D flow associate with O-D pair q;

E q :

: O-D incidence vector of O-D pair q with +1 at the origin and -1 at the destination;

E q+ :

: “O” incidence vector of O-D pair q with +1 at the origin;

E q− :

: “D” incidence vector of O-D pair q with +1 at the destination.

The objective function (3a) maximizes (minimizes the negative value of) the total system surplus. The first term in function (3a) is the total transmission cost, the second term is the total production cost for all the electricity consumed in the system. The third term is the willingness to pay by all consumers. Constraint (3a) defines the aggregate link flow vector as the sum of all O-D flow vectors. Constraints (3a–3a) ensure the flow conservation at each node, including the supply and demand nodes.Footnote 2 The rest constraints set non-negative restrictions on flow and demand. With an emphasis on the long-term planning decision, we have chosen to omit the Kirchhoff’s second law, phase angle constraint. We acknowledge that such simplification may lead to certain level of accuracy loss, e.g. loop flows may not be accounted in our model. We shall also point out that the market clearing conditions adopted in several studies, such as Nagurney (2006), are implied by the ISO formulation, which becomes clear in Section 2.4. Note that this model, different from the typical DC models used for short-term transmission network operation, incorporates elastic demand, which reflects long-term effect of market equilibrium.

Directly solving the above stochastic multi-agent optimization model can be numerically challenging. In Section 2.3, we show how the stochastic problem can be reduced to simpler problems through scenario decomposition. In Section 2.4, we convert each scenario problem, by using variational inequalities, to a traffic user equilibrium problem, for which efficient solution algorithms have been developed in the transportation literature.

2.3 Scenario Decomposition

There is a rich literature on scenario decomposition for solving large-scale stochastic programming problems via augmented Lagrangian method (Rockafellar 1976). Let us first introduce an important concept, nonanticipavity (Rockafellar and Wets 1991), which states that a reasonable policy should not require different actions relative to different scenarios if the scenarios are not distinguishable at the time when the actions are taken. Let S be a discrete set of possible scenarios for ξ and s(s∈S) denote an individual scenario with probability p s. One may consider solving each scenario-dependent problem and denote its solution as x s for each s. However, these solutions cannot be directly implemented, because at the time when an investment decision is made, one does not know yet which scenario is going to happen. In order to consolidate the s-dependent solutions to an implementable solution, we must impose the following nonanticipativity condition:

$$ \boldsymbol{x}^{s} = \boldsymbol{x}^{s^{\prime}}, \forall s \in S, s^{\prime} \in S, s \neq s^{\prime} $$
(4)

or equivalently

$$ \boldsymbol{x}^{s} - \boldsymbol{z} = 0, \forall s \in S $$
(5)

where z is a vector of free variables.

Through introducing an augmented Lagrangian function that adds a penalty of violating the nonanticipativity condition to the original objective function, Rockafellar and Wets (1991) developed a scenario-decomposition method, the progressive hedging (PH) method, for classic two-stage stochastic programming problems involving a single decision-maker. In this work, we extend the idea of scenario decomposition to multiple decision-maker cases.

Let \(\boldsymbol {x}_{i}^{s}\) and \(\boldsymbol {y}_{i}^{s}\) be the planning decision and the operational decision of player i(∈I) in scenario s(∈S), respectively. The stochastic multi-agent optimization problem can be reformulated as:

$$\begin{array}{@{}rcl@{}} &&(\boldsymbol{x}_{i}^{s}, \boldsymbol{y}_{i}^{s}) = \arg\min_{\boldsymbol{x}_{i}^{s}, \boldsymbol{y}_{i}^{s}}\left\{ E\left[f_{i}(\boldsymbol{x}_{i}^{s}, \boldsymbol{x}_{-i}^{s}) + g_{i}(\boldsymbol{x}_{i}^{s}, \boldsymbol{x}_{-i}^{s}, \boldsymbol{y}_{i}^{s}, \boldsymbol{y}_{-i}^{s}, \xi)\right]\right\}, \qquad \\ &&\text{s.t.} \qquad (\boldsymbol{x}_{i}^{s}, \boldsymbol{x}_{-i}^{s}) \in F, \qquad \boldsymbol{x}_{i}^{s} = \boldsymbol{z_{i}}, \qquad \text{and} \qquad (\boldsymbol{y}_{i}^{s}, \boldsymbol{y}_{-i}^{s}) \in G(\boldsymbol{x}_{i}^{s}, \boldsymbol{x}_{-i}^{s}, \xi), \\ &&\forall i \in I, s \in S \end{array} $$

For the i th player, define

$$\begin{array}{@{}rcl@{}} \mathcal{L}^{s}_{i}(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}, \boldsymbol{\omega}) &=& {f_{i}^{s}}(\boldsymbol{x}^{s}) + {g_{i}^{s}}(\boldsymbol{x}^{s}, \boldsymbol{y}^{s}) + \boldsymbol{{\omega^{s}_{i}}}^{T}(\boldsymbol{x}_{i}^{s} - \boldsymbol{z}_{i}) + \frac{1}{2}\gamma\|\boldsymbol{x}^{s}_{i} - \boldsymbol{z}_{i}\|^{2} \end{array} $$
(6)
$$\begin{array}{@{}rcl@{}} &&\mathcal{L}_{i}(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}, \boldsymbol{\omega}) = {\sum}_{s \in S}p^{s}\mathcal{L}^{s}_{i}(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}, \boldsymbol{\omega}) \end{array} $$
(7)

as the augmented Lagrangian, where \(\boldsymbol {{\omega ^{s}_{i}}}\) is the dual vector associated with the nonanticipativity constraints (5) and γ>0 is a penalty parameter. Therefore, the augmented Lagrangian integrates the nonanticipativity constraints with the original objective function. The stochastic problem for player i becomes

$$ \text{minimize} \quad \mathcal{L}_{i}(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}, \boldsymbol{\omega}) \quad \text{over all feasible} \boldsymbol{x}_{i}^{s} \text{and} \boldsymbol{y}_{i}^{s}. $$
(8)

Due to the nonseparable penalty term \( {1}/{2}\gamma \|\boldsymbol {x}_{i}^{s} - \boldsymbol {z}_{i}\|^{2}\) in (6), the problem cannot be decomposed directly. The PH method achieves decomposition by alternatingly fixing the scenario solutions \((\boldsymbol {x}_{i}^{s},\boldsymbol {y}_{i}^{s})\) and the implementable solution z i in (8). The implementation procedure is summarized in Algorithm 1. Recent successful applications of PH method in solving large-scale stochastic mix-integer problems can be found in Chen and Fan (2012), Fan and Liu (2010), and Waston and Woodruff (2010). As pointed out by Rockafellar and Wets (1991), parameter γ plays an important role in the convergence of the PH method in practice. In addition, several studies (Løkketangen and Woodruff 1996; Mulvey and Vladimirou 1991, 1992; Chen and Fan 2012; Waston and Woodruff 2010) reported some important factors that may influence the setting of penalty parameter γ. For example, it was suggested that an effective value for the penalty parameter should be close in magnitude to the coefficient of decision variable (Waston and Woodruff 2010).

figure a

2.4 Analyzing Each Scenario-Dependent Problem

Once the large-scale stochastic problem is decomposed, we need to iteratively solve many scenario-dependent deterministic problems. Each scenario-dependent problem itself is a multi-agent optimization problem, which is still computationally challenging. Next, we will show that, through creation of a virtual network and reformulation, we can convert the problem of interest to a traffic equilibrium problem, which allows us to exploit efficient algorithms developed by the transportation network science community. Of course, both multi-agent optimization and traffic equilibrium problems can be expressed using variational inequalities (VI). In some sense, it is not surprising that the two problems can be converted to each other, even though the equivalence is not apparent at first. For numerical implementation, one could directly rely on general purpose solvers designed for VI problems. On the other hand, there is an advantage in exploiting special problem structure, such as many efficient algorithms specifically developed for traffic equilibrium problems.

Let us first convert each player’s optimization to a VI. Note that all the functions and variables are deterministic in each scenario dependent problem, therefore we do not carry the notation ξ in the following discussion. Assuming objective function (2a) is concave and continuously differentiable, the model can be rewritten as the following VI:Footnote 3

$$\begin{array}{@{}rcl@{}} &\sum\limits_{k \in K} \sum\limits_{j \in J_{k}}& \left\{ - \left[ \rho_{k}^{\ast} + \sum_{k^{\prime} \in K} \left( \frac{\partial \rho_{k^{\prime}}}{\partial {g_{i}^{j}}}\left|{~}_{\boldsymbol{g} = \boldsymbol{g^{*}} }\sum_{j \in J_{k^{\prime}}}{g_{i}^{j \ast}} \right) - \frac{\partial \phi_{g}}{\partial {g_{i}^{j}}}\right|{~}_{ {g_{i}^{j}} = g_{i}^{j \ast}} -\lambda_{c}^{ij\ast} \right]\right.\\ &&\times \left( {g_{i}^{j}} - g_{i}^{j \ast}\right) \\ &&-\left[ -\left. \frac{\partial \phi_{c}}{\partial {c_{i}^{j}}} \right|_{{c_{i}^{j}}= c_{i}^{j \ast}}+ \lambda_{c}^{ij \ast} \right] \left( {c_{i}^{j}} - c_{i}^{j \ast} \right) +\left( -g_{i}^{j \ast} + c_{i}^{j \ast}\right)\\ &&\times\left( \lambda_{c}^{ij} - \lambda_{c}^{ij \ast} \right)\left. \right\} \geq 0, \forall \left( \boldsymbol{g}_{i}, \boldsymbol{c}_{i}, \boldsymbol{\lambda}_{i} \right) \in \mathcal{K}_{i}^{1} \end{array} $$
(9)
$$\mathcal{K}_{i}^{1} \equiv \left\{ \begin{array}{l}\left( \boldsymbol{g}_{i}, \boldsymbol{c}_{i}, \boldsymbol{\lambda}_{i} \right) \in R_{+}^{3l_{i}} | (2b)~\text{is satisfied} \end{array} \right\} $$

where:

\(\lambda ^{ij}_{c}\) :

: dual variable of capacity constraint of firm i on location j;

g i :

: vector that concatenates \({g_{i}^{j}}\) variables;

c i :

: vector that concatenates \({c_{i}^{j}}\) variables;

λ i :

: vector that concatenates \(\lambda _{c}^{ij}\) variables;

l i :

: number of optional locations for each conpanies i;

\(\mathcal {K}^{1}_{i}\) :

: feasible set of firm i’s decision.

Similarly, the ISO’s problem can be expressed using VI as follows:

$$\begin{array}{@{}rcl@{}} &&{\sum}_{q \in Q} \left[\phi_{t}({\boldsymbol{v}^{\ast}} ) + \nabla \phi_{t}({\boldsymbol{v}^{\ast}}) \boldsymbol{v}^{\ast} - A^{T}\lambda^{q\ast}\right]^{T}\left( \boldsymbol{x}^{\; q} - \boldsymbol{x}^{\; q \ast}\right)\\ &&+ {\sum}_{q \in Q} \left[E^{q T}\lambda^{q \ast}\,+\,\boldsymbol{\rho}^{\ \ast T} E^{q +}\!- w(\boldsymbol{d}^{\ast T}) E^{q -} \right] \left( t^{q} \!- t^{q \ast}\right)\!\geq\! 0 , \forall \boldsymbol{x}^{\; q}, \boldsymbol{t}^{\;q} \!\in\! \mathcal{K}^{2} \end{array} $$
(10)
$$\mathcal{K}^{2} \equiv \left\{ \begin{array}{l} \left( \boldsymbol{x}, \boldsymbol{t} \right) | (3b) \sim (3g)~\mathrm{is~satisfied} \end{array} \right\} $$

where:

∇ϕ t (⋅):

: Jacobian matrix of link cost function;

λ q :

: dual vector associated with constraint (3a) of O-D pair q. Each row corresponds to a link;

\(\mathcal {K}^{2}\) :

: feasible set of ISO decision.

Note that the market clearing conditions (Nagurney 2006) are implied by the ISO formulation: The second term in Eq. 10 means that if the demand of OD pair q, t q, is zero, then the wholesale price plus the transmission cost can be larger than the consumer willingness to pay; otherwise, the wholesale price plus the transmission cost must be equal to the consumer willingness to pay. In addition, note that in constraint (3a), ISO is required to balance demand and supply at all time, so the dual variable associated with this equality constraint is a free variable.

As stated before, the decisions of all participants in this system are interdependent and should be modeled simultaneously as a whole system. We state the system equilibrium more formally by the following definition.

Definition 1

(Power System Equilibrium). The equilibrium state of a power system is that all generators achieve their own optimality (cf. (9)) and ISO achieves its optimality (cf. (10)).

We claim the following Lemma, which provides the equivalent condition of the power system equilibrium conditions.

Lemma 1

(Variational Inequality Condition for the Power System Equilibrium). The equilibrium conditions governing the power system equilibrium are equivalent to finding solutions satisfying the following variational inequality (11):

$$\begin{array}{@{}rcl@{}} &&{\sum}_{k \in K}^{}{{\sum}_{j \in J_{k}}^{} {\left[ \!- {\sum}_{k^{\prime} \in K}^{} \left( \left.\frac{\partial \rho_{k^{\prime}}}{\partial {g_{i}^{j}}}\right|_{\boldsymbol{g}= \boldsymbol{g}^{*}}{\sum}_{j \in J_{k^{\prime}}}{g_{i}^{j \ast}} \right)\,+\, \left. \frac{\partial \phi_{g}}{\partial {g_{i}^{j}}}\right|_{{g_{i}^{j}} = g_{i}^{j \ast}} \,+\,\left. \frac{\partial \phi_{c}}{\partial {c_{i}^{j}}} \right|_{{c_{i}^{j}}= c_{i}^{j \ast}}\!\right] \left( {g_{i}^{j}} \!- g_{i}^{j \ast} \right)}} \\ &&+ \left[\phi_{t}({\boldsymbol{v}^{\ast}} ) + \nabla \phi_{t}({\boldsymbol{v}^{\ast}} ) \boldsymbol{v}^{\ast} \right]^{T}\left( \boldsymbol{v} - \boldsymbol{v}^{\ast}\right) - w(\boldsymbol{d}^{\ast T} ) \left( \boldsymbol{d}- \boldsymbol{d}^{\ast}\right)\\ &&+ {\sum}_{k \in K}^{}{{\sum}_{j \in J_{k}}^{} { }} \left \{ \left. \frac{\partial \phi_{c}}{\partial {c_{i}^{j}}} \right|_{{c_{i}^{j}}= c_{i}^{j \ast}} \left[ \left( {c_{i}^{j}} - {g_{i}^{j}} \right) - \left( c_{i}^{j\ast} - g_{i}^{j \ast}\right)\right]\right.\\ &&- \left.\lambda_{c}^{ij\ast}\left[ \left( {c_{i}^{j}} - {g_{i}^{j}} \right) - \left( c_{i}^{j\ast} - g_{i}^{j \ast}\right)\right] +\left( c_{i}^{j \ast} -g_{i}^{j \ast} - 0\right) \left( \lambda_{c}^{ij} - \lambda_{c}^{ij \ast} \right) {\vphantom{\frac{\partial \phi_{c}}{\partial {c_{i}^{j}}}}}\right \} \geq 0 \\ &&\forall \left( \boldsymbol{g}_{i}, \boldsymbol{c}_{i}, \boldsymbol{\lambda}_{i} \right) \in \mathcal{K}_{i}^{1}, \forall i, \forall \left( \boldsymbol{x}, \boldsymbol{t} \right) \in \mathcal{K}^{2} \end{array} $$
(11)

Proof 1

Combining VI (2) and (4), we have the following terms cancelled out:

  1. 1.

    \({\sum }_{q \in Q} \left [ - A^{T}\gamma ^{q\ast }\right ]^{T}\left (\boldsymbol {x}^{q} - \boldsymbol {x}^{q \ast }\right )\) and \({\sum }_{q \in Q} E^{q T}\gamma ^{q \ast } \left (t^{q} - t^{q \ast }\right )\)

  2. 2.

    \( {\sum }_{k \in K}^{}{{\sum }_{j \in J_{k}}^{}{ }} \rho _{k}^{\ast } \left ({g_{i}^{j}} - g_{i}^{j \ast }\right ) \) and \({\sum }_{q \in Q} \boldsymbol {\rho }^{\ \ast T} E^{q +} \left (t^{q} - t^{q \ast }\right )\)

The first cancellation is derived by Constraint (3a), and the second cancellation is derived by Constraint (3a). Then, add \(-\left .\frac {\partial \phi _{c}}{\partial {c_{i}^{j}}}\right |_{{c_{i}^{j}} = c_{i}^{j \ast }} \left ({g_{i}^{j}} - g_{i}^{j \ast }\right )\) and subtract \(-\left .\frac {\partial \phi _{c}}{\partial {c_{i}^{j}}}\right |_{{c_{i}^{j}} = c_{i}^{j \ast }} \left ({g_{i}^{j}} - g_{i}^{j \ast }\right )\), and reorganize the formulation in terms of variables g and c−g. Finally, after the use of Constraint (3a) and (3a) to substitute (x,t) with (v,d), VI (11) is derived. □

Next we will show the VI problem in (11) is equivalent to a transportation network user equilibrium problem. Let us use a simple case illustrated in Fig. 1 as an example to explain the construction of a virtual network corresponding to a traffic network equilibrium problem. In Fig. 1a virtual node C denotes an investment firm; F denotes a potential investment location or an existing generator. The link flow from a node C to a node F means the capacity that firm C invests at location F. For an existing generator, link flow of C-F is set to be the existing generation capacity. Each node P or U corresponds to a firm. The flows on link F-P and link F-U denote the electricity production quantity and the unused capacity of that firm at location F, respectively. Virtual node I is created to denote electricity that shares the same transmission infrastructure to access the existing power grid. Physical node A denotes an access point or a demand node in the power grid. In general, there are multiple access points and demand nodes in a power network. The flow on link P-I denotes the total electricity production of each firm, and the flow on link I-A or P-A denotes the transmission quantity between the corresponding locations.

Fig. 1
figure 1

A network structure of the problem

Full size image

Theorem 2

(Virtual Network Equivalence) The VI (11) is identical with the VI governing transportation user equilibrium of the virtual network shown in Fig. 1 if link costs and demand market are defined in the following manner:

  • For the links within “Capital investment” layer in Fig. 1 (i.e. from Node C to Node F), the link cost is set to be the marginal capacity cost, i.e. \({\partial \phi _{c} ({c_{i}^{j}})}/{\partial {c_{i}^{j}}}\) . In case of existing generators, the cost attached to this link is set to be zero.

  • For links connecting Node F and Node P, the link cost is marginal production cost, i.e. \({\partial \phi _{g} ({g_{i}^{j}})}/{\partial {g_{i}^{j}}}\).

  • For links connecting Node F and Node U, the link cost represents the cost of shutting off unused generation capacity. In case such cost is negligible, it can be set to zero.

  • For links connecting Node P and Node I, we interpret the link cost as strategic escalating of electricity price of each generator, which is set to \(-{\sum }_{k^{\prime } \in K}^{}{\left (\frac {\partial \rho _{k^{\prime }}}{\partial {g_{i}^{j}}}\left (\boldsymbol {g}\right ){\sum }_{j \in J_{k^{\prime }}}{{g_{i}^{j}}} \right ) }\) (see Appendix 4 for the calculation of \(\frac {\partial \rho _{k^{\prime }}}{\partial {g_{i}^{j}}}\)). Because we assume oligopoly competition, rather than perfect competition in the electricity supply industry, each firm will try to produce electricity at a level where the wholesale price equals to the marginal cost plus this term so that the profit is maximized.

  • For links within the power grid, a marginal transmission cost is imposed by the ISO, i.e. ϕ t (v)+∇ϕ t (v)v.

  • The demand functions of the nodes within the power grid are assumed to be given and depend on the retail price only, while the demand function of Node U is assigned zero despite of the value of capacity shadow price.

Before we give the proof of Theorem 2, we introduce the following Theorem provided in Nagurney (2006):

Theorem 3

A travel link flow pattern and associated travel demand and disutility pattern is a traffic network equilibrium if and only if the variational inequality holds: determine \((f^{*}, d^{*}, \lambda ^{*}) \in \mathcal {K}^{3}\) satisfying:

$$\begin{array}{@{}rcl@{}} &&{\sum}_{a \in L} \phi_{a}\left( f^{*}\right) \times (f_{a} - f_{a}^{*}) - {\sum}_{n \in N} \lambda^{*}_{n}\times (d_{n} - d_{n}^{*}) \\ &&+ {\sum}_{n \in N} [ d_{n}^{*} - d_{n}(\lambda^{*})]\times [\lambda_{n} - \lambda_{n}^{*}] \geq 0, \forall (\boldsymbol{f}, \boldsymbol{d}, \boldsymbol{\lambda}) \in \mathcal{K}^{3} \end{array} $$
(12)
$$\mathcal{K}^{3} \equiv \left\{ (\boldsymbol{f}, \boldsymbol{d}, \boldsymbol{\lambda}) \in R_{+}^{|L| + 2|N|} |~there~exist~an~\boldsymbol{\chi}~satisfying~(13)~and~(14) \right\} $$
$$\begin{array}{@{}rcl@{}} f_{a} = {\sum}_{p \in P} \chi_{p} \delta_{ap}, \forall a \in L \end{array} $$
(13)
$$\begin{array}{@{}rcl@{}} d_{n} = {\sum}_{p\in P_{n}}\chi_{p}, \forall n \in N \end{array} $$
(14)

where:

  • N : demand node set of virtue transportation network (indexed by n);

  • L : link set of virtue transportation network (indexed by a);

  • P: path set of virtue transportation network (indexed by p);

  • δ ap : binary indicator, δ ap =1 if link a is contained in path p, and δ ap =0 otherwise;

  • ϕ a (⋅): link cost function of link a with respect to link flow;

  • f a : link flow of link a;

  • d n : demand at demand node n;

  • d n (⋅) : demand function at demand node n with respect to travel disutility;

  • λ n : travel disutility at demand node n;

  • χ p : path flow of path p;

Notice that in Theorem 3, travel disutility is restricted to non-negative value, which is not applicable in power market, where price can become negative if necessary (e.g. the ISO may pay consumers to use electricity if supply exceeds demand and shutting down production facilities is too costly). So we propose the following Corollary to account for this situation.

Corollary 4

(Unrestricted Locational Price). In a virtual transportation network where consumer can gain time (instead of spend time) to travel, a travel link flow, travel demand and disutility pattern (negative means utility) is a traffic network equilibrium if and only if it satisfies the following VI: determine \((f^{*}, d^{*}, \lambda ^{*}) \in \mathcal {K}^{4}\) satisfying:

$$ \begin{array}{l} {\sum}_{a \in L} \phi_{a}\left( f^{*}\right) \times (f_{a} - f_{a}^{*}) - {\sum}_{n \in N} \lambda^{*}_{n}\times (d_{n} - d_{n}^{*}) \geq 0, \forall (\boldsymbol{f}, \boldsymbol{d}, \boldsymbol{\lambda}) \in \mathcal{K}^{4} \end{array} $$
(15)
$$\mathcal{K}^{4} \equiv \left\{ (\boldsymbol{f}, \boldsymbol{d}, \boldsymbol{\lambda}) \in R_{+}^{|L| + |N|} \times R^{|N|} | \text{there exist an \(\boldsymbol{\chi}\) satisfying (15) and (14)} \right\} $$

Note that since the dual vector λ does not have sign restriction, its corresponding optimality condition is simply the original constraints associated with it, i.e. (3c), which can be equivalently expressed by (13) and (14).

Now we propose the proof for Theorem 2.

Proof 2 (Proof of Theorem 2)

There are two types of demand nodes in the virtual transportation network: the nodes within transmission network, denoted by “A”; and the virtual nodes representing unused capacity, denoted by “U”. A-nodes do not have non-negativity constraint on price, so VI (15) is applied for these nodes (Corollary 4), while VI (12) is applied for U-nodes (Theorem 3). After algebraic simplification, the VI governing the virtual transportation network is identical with VI (11). □

Note that in each iteration of the PH method, the objective function is updated by adding a Lagrange multiplier and a penalty term, i.e. \(\boldsymbol {{\omega ^{s}_{i}}}^{T}(\boldsymbol {x}_{i}^{s} - \boldsymbol {z}_{i}) + \frac {1}{2}\gamma \|\boldsymbol {x}_{i}^{s} - \boldsymbol {z}_{i}\|^{2}\), which is a function of the planning decision variable. Therefore, the corresponding VI that needs to be solved during each iteration of the PH procedure should be modified as:

$$\begin{array}{@{}rcl@{}} &&{\sum}_{k \in K}^{}{\sum}_{j \in J_{k}}^{}\left [ - {\sum}_{k^{\prime} \in K}^{} \left( \left. \frac{\partial \rho_{k^{\prime}}}{\partial {g_{i}^{j}}}\right|_{\boldsymbol{g}= \boldsymbol{g}^{*}}{\sum}_{j \in J_{k^{\prime}}}{g_{i}^{j \ast}} \right) + \left. \frac{\partial \phi_{g}}{\partial {g_{i}^{j}}} \right|_{{g_{i}^{j}} =g_{i}^{j \ast}} + \left. \frac{\partial \phi_{c} }{\partial {c_{i}^{j}}} \right|_{{c_{i}^{j}} = c_{i}^{j \ast}}+ \omega_{ij}^{s*}\right.\\ &&\left.+ \gamma \left( c_{i}^{js^{\ast}} - \overline{c}_{i}^{js\ast}{\vphantom{\frac{\partial \rho_{k^{\prime}}}{\partial {g_{i}^{j}}}}}\right) \right ] \left( {g_{i}^{j}} - g_{i}^{j \ast} \right) + \left[\phi_{t}({\boldsymbol{v}^{\ast}}) + \nabla \phi_{t} ({\boldsymbol{v}^{\ast}}) \boldsymbol{v}^{\ast} \right]^{T}\left( \boldsymbol{v} - \boldsymbol{v}^{\ast}\right) - w(\boldsymbol{d}^{\ast T}) \left( \boldsymbol{d}- \boldsymbol{d}^{\ast}\right)\\ &&+ {\sum}_{k \in K}^{}{{\sum}_{j \in J_{k}}^{} { }} \left \{ \left[ \left. \frac{\partial \phi_{c} }{\partial {c_{i}^{j}}} \right|_{{c_{i}^{j}} = c_{i}^{j \ast}} + \omega_{ij}^{s*} + \gamma \left( c_{i}^{js^{\ast}} - \overline{c}_{i}^{js\ast}\right) \right] \left[ \left( {c_{i}^{j}} - {g_{i}^{j}} \right) - \left( c_{i}^{j\ast} - g_{i}^{j \ast}\right)\right]\right.\\ &&-\left. \lambda_{c}^{ij\ast}\left[ \left( {c_{i}^{j}} - {g_{i}^{j}} \right) - \left( c_{i}^{j\ast} - g_{i}^{j \ast}\right)\right] +\left( c_{i}^{j \ast} -g_{i}^{j \ast} - 0\right) \left( \lambda_{c}^{ij} - \lambda_{c}^{ij \ast} \right) {\vphantom{\frac{\partial \phi_{c} }{\partial {c_{i}^{j}}}}}\right \} \geq 0 \\ &&\forall \left( \boldsymbol{g}_{i}, \boldsymbol{c}_{i}, \boldsymbol{\lambda}_{i} \right) \in \mathcal{K}_{i}^{1}, \forall i, \forall \left( \boldsymbol{x}, \boldsymbol{t} \right) \in \mathcal{K}^{2} \end{array} $$
(16)

The additional terms involving \(\omega _{ij}^{s*} + \gamma \left (c_{i}^{js^{\ast }} - \overline {c}_{i}^{js\ast }\right )\) is attributed to the nonanticipativity condition. Therefore the link cost associated with C-F should be modified from \({\partial \phi _{c} ({c_{i}^{j}})}/{\partial {c_{i}^{j}}}\) (see Theorem 2) to:

$$ \text{modified C-F link cost} = {\partial \phi_{c} ({c_{i}^{j}})}/{\partial {c_{i}^{j}}} + \omega_{ij}^{s} + \gamma \left( c_{i}^{js^{\ast}} - \overline{c}_{i}^{js}\right) $$
(17)

Based on the same network structure shown in Fig. 1, we now have the PH-transportation network solution procedure for the stochastic problem as shown in Algorithm 2. Following this decomposition procedure, the original stochastic energy supply chain problem is converted to many scenario-dependent deterministic traffic network equilibrium problems, which can be solved efficiently by Frank-Wolf algorithm (LeBlanc et al. 1975), which is implemented in this study, or by other recent methods summarized in Bar-Gera (2010).

figure b

We shall note that in general the VI defined in (16) may have multiple solutions. For the numerical implementation reported herein, we consider only the single-solution case. Alternatively, one may consider a min-max formulation to seek the best investment decision in the equilibrium condition that returns the worst-case performance.

3 Numerical Examples

3.1 A Simple Example for Illustration and Solution Validation

Example 1 is constructed to illustrate how the energy problem may be decomposed and converted to traffic network equilibrium problems. The example is intentionally set to be symmetric so that a benchmark solution can be easily obtained analytically, which then is used to validate the proposed solution procedure. This example includes two energy investment companies, one candidate investment location, and one electricity demand market. Two scenarios with equal probability are considered. Transmission cost is set to be zero and transmission capacity unlimited. The specifics of cost and demand functions are given in Table 1.

Table 1 Parameter setting in Example 1
Full size table

Figure 2 shows the corresponding virtual network, with four paths: p 1=(C1,F1,P1,I1,A1), p 2=(C2,F1,P2,I1,A1), p 3=(C1,F1,U1), p 4=(C2,F1,U2). The solution yielded from our solution algorithm is given in Table 2. Each path in the virtual transportation network carries a physical meaning in the energy supply chain. For example, path flow on p 1 means the amount of power supplied by firm C1 from location F1 to demand market A1; path flow on p 3 represents the unused capacity of firm C1 at location F1. In addition to path flow, link flow also has a corresponding implication in the energy supply chain. For example, link flow from C1 to F1 represents the total capacity investment by firm C1 at location F1. The multiplier λ A1 tells us the marginal electricity price at node A1. The multipliers λ U1 and λ U2 tell us the marginal benefit of increasing one unit of production capacity at node F1 by C1 and C2, respectively. Using this correspondence, we extract the numerical solutions for the energy infrastructure investment problem, as shown in Table 3. Note that in this simple example, the consumer surplus is computed at the wholesale level. These results are consistent with Cournot-Nash equilibrium calculated analytically. The optimal solution to the stochastic multi-agent optimization problem suggests that each firm invest for a generation capacity of 16 units. As a comparison, if the company could wait until future uncertainty is revealed before making investment decision, the deterministic solutions would be 12 units for scenario 1 and 18 units for scenario 2.

Fig. 2
figure 2

The virtual network for Example 1. (Note: the number attached to each arc is the assigned link cost defined in Theorem 2)

Full size image
Table 2 Traffic equilibrium solutions for the virtual network
Full size table
Table 3 Power market equilibrium results
Full size table

Table 4 summarizes the numerical implementation details, including the parameter setting, computing environment, and computing time. The convergence pattern of the two scenario-dependent planning decisions is plotted in Fig. 3, in which the termination criterion is reached within less than 30 iterations.

Table 4 Numerical implement information
Full size table
Fig. 3
figure 3

Convergence of the planning decision

Full size image

3.2 A Realistic Case Study Based on SMUD Power Network

To draw meaningful practical implications from the theoretical results reported here, we implement our model and algorithm on a regional power network in Sacramento Municipal Utility District (SMUD). The transmission network consists of 25 nodes, 11 of which are demand nodes (Node 1 ∼11), and 65 links. The network structure is shown in Fig. 4.

Fig. 4
figure 4

Sacramento Municipal Utility District (SMUD) network

Full size image

Four optional investment locations (Node 21 ∼24) are being considered, two of which are in remote areas (Node 21 and 22) with lower investment costs but also lower transmission resource; the other two locations (Node 23 and 24) are just the opposite. The two further locations are connected to Node 20 by a single transmission line; the two closer locations are connected to Node 2 and 3 via separate transmission lines. We consider two firms with different technologies as investors. Firm 2 has mature technologies whose production cost is certain, while Firm 1 represents emerging technology, whose future production cost is uncertain. We also assume that the investment cost of one firm is independent of the other firm’s decisionFootnote 4. The parameter values are given in Appendix 3. This setting is referred as base case in the following analysis.

An optimal solution is obtained using Algorithm 2 on the same computer as in Example 1, with a total computing time of 3312 seconds. The PH algorithm converges in 13 iterations with an absolute gap of 0.615 (see Fig. 5). Each scenario-dependent problem within the PH algorithm is solved using Frank-Wolfe algorithm. See Fig. 6 for its convergence pattern.Footnote 5

Fig. 5
figure 5

Convergence of PH algorithm

Full size image
Fig. 6
figure 6

Convergence of Frank-Wolfe algorithm

Full size image

In Table 5, we examine the impacts of transmission network on investment decisions by comparing results from two cases: the base case, and the case where no transmission cost or constraint is considered (free-transmission Case). In the base case, both firms invest less in the further locations (location 21 and 22) due to transmission restrictions and costs. However if the transmission network is ignored, the firms would increase their investment in the further locations to take advantage of cheaper capital cost. This comparison shows that ignoring transmission network may lead to poor investment recommendations. Therefore, a supply chain model that captures the essence of transmission network between supplies and demands is critical.

Table 5 Impacts of transmission network on investment decisions (MW)
Full size table

Next, we will use the proposed model to explore the impacts of oligopolistic competition on total investments, average electricity price (see Fig. 7), and total system surplus (see Fig. 8). The total system surplus is defined as the total consumer willingness-to-pay subtracts the total system cost. The consumer surplus is defined as the total consumer benefits subtracts the total electricity bill they pay. Thus we decompose total system surplus into three components: consumer surplus, generators profits (surplus) and transmission revenues.Footnote 6 We compare the results among three market types (cases): the base case, monopoly case (only Firm 2) and perfect-competition case. From Fig. 7, with more competition involved in power supply side, lower electricity price and higher total investment can be expected. This is mainly due to the fact that electricity generally has low price elasticity of demand. Lacking competition will allow suppliers to exert market power by strategically withholding their investment (long term) and manipulate the market price (short term). From Fig. 8, we can see that as market competition level increases, the total system surplus increases, the transmission revenues increases and the generator surplus decreases to zero. These results demonstrate that an energy planning model capturing oligopoly market is critical - simplifying an oligopolistic electricity market to either a central-planner case or a perfect market case would compromise the long-term investment decisions and thus the total system surplus.

Fig. 7
figure 7

Impacts of strategic behavior on price ($/MWh) and investment (MW)

Full size image
Fig. 8
figure 8

Impacts of strategic behavior on total system surplus ($)

Full size image

Finally, we explore the impacts of uncertainty. In Table 6, we compare results from the stochastic model (base case) and a deterministic approach. The deterministic approach takes the expected value of Firm 1’s production cost as model input, in which case the two firms become symmetric. The results show that when there is no uncertainty about future technology, both firms reduce their investment. This is somehow counter intuitive because it is generally believed that uncertainty discourages industry from investing. In the investor’s model, since the firms are allowed to adjust their production quantities in the operational stage (second stage of stochastic programming), they can always maintain a non-negative profit in each scenario. Therefore, firms are more “optimistic” when they make the first stage investment decisions - with uncertainty about future production cost, both firms will focus more on the good scenario for themselves. However, if the firms take a more risk-averse attitude instead of a risk-neutral one, we expect to have different results.

Table 6 Comparing investment decisions (MW) between stochastic and deterministic approach
Full size table

4 Discussion

This study focuses on energy infrastructure planning in a restructured electricity market. The main contribution is on the development of modeling and solution methods to address challenges brought by uncertainties and oligopolistic competition among energy producers over a complex network structure. Directly solving the stochastic multiple-agent model using general-purpose solvers may not be possible as we have demonstrated in the numerical example. To overcome the computational difficulty, we have combined two ideas. The first is using stochastic decomposition to convert a large-scale stochastic problem to many smaller scenario-dependent problems that are more easily solvable. The second is using variational inequalities to convert a multi-agent optimization problem to a single traffic equilibrium problem, allowing exploitation of efficient solution techniques that over perform general-purpose solvers.

There are several directions for future research. One may explore the roles of risk attitudes and information quality on energy infrastructure investment strategies, which may be used to design efficient information sharing strategy across stakeholders in the system. In addition, with the connections established between the energy planning and traffic network equilibrium problems, one may extend the rich knowledge generated in the transportation literature to energy modeling. For example, knowledge about price of anarchy, congestion pricing, and dynamic equilibrium may be extended to energy system planning and policy related questions, such as how to influence individual energy investment decisions from user-optimal to system-optimal through economic incentives. We hope the work reported here will inspire more interdisciplinary research across transportation and energy.