수요의 불확실성을 고려한 확률적 발전계획문제에 대한 발전원 분해기법

1. 서 론

발전계획(Unit Commitment, UC)문제는 전력시스템의 운영자(System Operator)가 자신의 관할 구역의 발전원(원자력발전기, 화력발전기 등의 개별 발전기를 지칭함)들의 운영 스케줄을 결정하는 문제이다(Van Ackooij et al., 2018). 운영자는 전력을 생산하는 발전회사(Generation Company, GENCO)들로부터 제공받은 발전원들의 운영비용 정보와 전력 수요 예측에 기반하여, 관할 구역의 전력 수요를 충족시키기 위하여 전체 운영비용을 최소화하도록 개별 발전원의 발전상태(가동 또는 정지)와 발전량을 결정하는 발전계획을 주기적으로 수립한다. 고려하는 계획기간과 의사결정 범위에 따라 주간(week-ahead UC), 일간(day-ahead UC), 실시간(real-time UC) 발전계획 등으로 나눌 수 있는데, 향후 24시간의 계획기간을 일정한 시간 단위의 시구간들로 나누고(15분에서 몇 시간까지 다양함), 시구간별 발전원의 발전상태와 발전량을 결정하는 일간 발전계획(day-ahead UC)이 전력시장에서의 전력가격 결정 등에 있어 가장 기본적인 의사결정이다.

실제 전력 수요가 사전의 예측치에서 벗어난 상황에서도 전력시스템을 안정적으로 운영하기 위해서는, 발전계획 수립 시 불확실한 전력의 수요를 사전에 고려해야 한다. 이때, 수요 요인으로 소비자의 전력 사용량뿐만 아니라 재생에너지 발전량을 고려할 수 있으며, 후자는 운영자가 그 발전량을 조절할 수 없는 음의 수요로 간주한다. 점차 보급이 확대되는 재생 발전원을 포함한 전력시스템을 안정적으로 운영하기 위해서는 수요의 불확실성을 발전계획문제에 반영해야 한다. 본 연구에서는 불확실한 수요를 과거의 데이터 혹은 확률 분포 등으로부터 표본을 추출하고(추출된 하나의 표본은 수요 시나리오라고 지칭한다), 추출된 모든 수요 시나리오에 대한 기대비용을 최소화하는 확률적 발전계획문제를 탐구한다. 즉, 어떤 수요 시나리오가 발현될지 모른다고 가정한 상태에서 개별 발전원의 발전상태를 결정하고, 결정된 발전상태 하에서 각 수요 시나리오의 발현에 대해 조정(recourse action)하여 대응하는 2단계 의사결정모형을 적용한다. 이때, 발전원의 물리적인 운영 특성으로 인하여 개별 발전원의 발전상태를 단시간 내에 조정하는 것이 제한적이기 때문에 이를 수요 시나리오에 독립적으로 결정하며, 예비력 및 예비 발전자원의 활용 등 다양한 조정 방법도 가능하지만 본 연구에서는 각 수요 시나리오의 발현에 대해 개별 발전원의 발전량만을 조정하는 것을 상정한다.

이러한 2단계 확률적 발전계획모형은 수요 시나리오 수가 증가함에 따라 계산 부담이 증가한다는 특징이 있다. 이를 완화하기 위해 기존의 문헌에서 제안된 최적화 해법들은 주로 분해기법에 기반하고 있다. 이 중 발전원 분해기법(Unit decomposition)은 발전원간 연결 제약을 완화하여 라그랑지안 완화(Lagrangian relaxation)를 활용한 최적화 해법을 지칭한다(Van Ackooij et al., 2018). 발전원간 연결 제약을 완화하면, 나머지 구조는 발전원별로 분해될 수 있으며, 분해된 부문제(subproblem)는 하나의 발전원의 발전상태와 발전량을 결정하는 단일발전원 계획문제(single-unit commitment, 1UC)가 된다. 기존의 문헌들은 주어진 데이터가 확정적인(deterministic) 상황에서 단일발전원 계획문제에 대한 해법과 이를 발전계획문제에 적용한 발전원 분해기법을 제안하였다.

단일발전원 계획문제는 하나의 발전원을 소유한 개별 발전사업자(Independent Power Producer)가 주어진 전력 가격하에서 자신의 발전계획을 전력 시장에 제안하는 상황에서 발생한다는 점에서 그 자체로도 연구되었으며, NP-hard에 속함이 알려진 일반적인 발전계획문제와 대조적으로 다항시간 내 해결 가능함이 밝혀졌다. 기존 연구 중 Lee et al. (2004)와 Rajan et al.(2005)은 최소 가동/정지 시간 제약이 존재하는 발전상태 변수들로 이루어진 다면체의 유효 부등식(valid inequality)을 제안하여 해당 다면체의 구조를 제시하였다. 이후, 발전량 변수를 추가로 고려한 다면체에서의 유효 부등식도 제안되었는데(Ostrowski et al., 2011; Damcı-Kurt et al., 2016), 이들은 인접한 두 시구간(time period)의 발전량 증감을 제한하는 증/감발(ramping up/down) 제약을 반영하였다. 또한 기존의 연구에서, 단일발전원 계획문제에 대한 해법으로 주로 동적계획(dynamic programming)법이 활용되었다. Fan et al.(2002)은 가변 발전비용이 구간 선형함수인 단일발전원 계획문제를 해결하기 위한 다항시간 동적계획 알고리듬을 제시하였다. 이후 Frangioni and Gentile(2006)은 가변 발전비용이 볼록 이차함수인 경우에도 적용할 수 있는, 계산복잡도가 계획기간의 길이의 세제곱에 해당하는 동적계획 알고리듬을 제안하였다. 이 알고리듬은 매 시구간별 발전상태를 나타내는 상태-공간 그래프(state-space graph)를 구성하고 문제를 최단 경로 문제로 표현하는 것에 기반한다. 이후의 문헌들은 해당 연구를 확장하였다. Frangioni and Gentile(2015)과 Guan et al.(2018)은 상태-공간 그래프를 재정의하여 발전상태를 구하는 알고리듬의 계산복잡도를 개선하였다. 또한 발전상태에 대한 명시적인 정수 제약이 없어도 정수 해를 도출할 수 있는 extended formulation이 제안되었다(Frangioni and Gentile, 2015; Guan et al., 2018; Knueven et al., 2018). 그리고 Wuijts et al.(2021)은 상태-공간 그래프를 재정의하여 계산 속도를 개선하였다. 마지막으로, Frangioni et al.(2008)은 화력발전기와 양수발전기가 공존하는 전력시스템의 발전계획문제에 대해 부문제인 단일발전원 계획문제를 자신의 알고리듬(Frangioni and Gentile, 2006)으로 해결한 발전원 분해기법을 제안하였다.

앞서 언급한 것과 같이, 기존의 문헌들은 전력의 가격이 확정적인 단일발전원 계획문제에 대하여 다양한 해법을 제안하였고, 이를 수요가 확정적인 발전계획문제에 발전원 분해기법에 적용하였다. 하지만, 전력의 수요가 불확실한 경우의 확률적 발전계획문제에 대한 발전원 분해기법은 드물게 연구되었다. 이 경우 역시 발전원 분해기법을 적용하면 해당하는 부문제는 확률적 단일발전원 계획문제(stochastic 1UC)와 동등한 구조를 지닌다. 이 부문제를 효과적으로 해결하는 것은 확률적 발전계획문제를 위한 발전원 분해기법에 중요하다. 하지만, 두 문제에 관한 기존의 연구는 제한적이다. Pan and Guan(2016)은 다단계 확률적 단일발전원 계획모형에 대해 유효 부등식들을 제안하였으나, 많은 수의 시나리오에 대한 계산성능이 충분히 입증되지 못하였다. Guan et al.(2018)은 기존의 확정적인 단일발전원 계획문제의 해법을 확장한 동적계획 알고리듬을 제안하였으나, 알고리듬의 효과성이 실험적으로 입증되지 못하였다. 또한, 초기의 선행 연구는 확률적 발전계획문제에 대해 발전원 분해기법을 제시하였으나(Carpentier et al., 1996; Nowak and Römisch, 2000; Shiina and Birge, 2004), 해법의 효과성은 증/감발 제약 등 발전원들의 물리적인 특성을 충분히 고려하지 않아 부문제를 단순화한 것에 기인한다. 따라서 증/감발 제약을 반영한 확률적 발전계획문제에 대해 부문제의 효율적인 해법에 기반한 발전원 분해기법이 필요하다.

본 연구에서는 불확실한 전력 수요 하에서의 확률적 발전계획문제를 위한 발전원 분해기법을 제안하며, 연구의 의의는 다음과 같다. 우선, 발전원 분해기법에 핵심적인 부문제인 확률적 단일발전원 계획문제에 대해 다수의 시나리오를 효율적으로 다룰 수 있는 동적계획 알고리듬을 제시한다. 제시한 알고리듬은 분해기법의 핵심 요소로 활용되며, 또한 개별 발전사업자의 발전계획 수립에도 활용될 수 있다. 다음으로, 이를 바탕으로 2단계 확률적 발전계획모형에 대한 효율적인 발전원 분해기법을 제안한다. 제안한 분해기법은 시나리오 수가 많아짐에 따라 증가하는 계산 부담을 발전원별 부문제에 배분함으로써, 다수의 시나리오 하에서도 효율적으로 상한 및 하한을 도출할 수 있다. 마지막으로, 현실을 반영한 실험 데이터에 대하여 수치 실험을 진행하여 제안한 최적화 해법들의 효율성을 확인한다.

본 논문의 구성은 다음과 같다. 우선, 제2장에서는 확률적 단일발전원 계획문제와 이를 효율적으로 해결하기 위한 동적계획 알고리듬을 제시한다. 이를 활용하여, 제3장에서는 2단계 확률적 발전계획모형에 대한 발전원 분해기법을 제시한다. 또한, 제4장에서는 다양한 인스턴스에 대해 수치 실험을 진행하여 제안한 해법의 효율성을 분석한다. 마지막으로, 제5장에서는 본 연구의 결과를 요약하며 향후 연구 방향을 제시한다.

2. 확률적 단일발전원 계획문제에 대한 동적계획 알고리듬

2.1 확률적 단일발전원 계획문제

단일발전원 계획문제는, 하나의 발전원을 소유한 개별 발전사업자가 자신의 발전계획을 전력 시장에 제안하는 상황에서 발생한다(Pan and Guan, 2016). 이때, 발전사업자는 전력 시장의 주어진 전력 가격하에서 자신의 발전 수익을 최대화하는 발전상태와 발전량을 결정한다. 앞선 장에서 언급한 것과 같이, 발전원의 발전상태는 전력 가격 시나리오의 발현 전 결정하고, 발현된 전력 가격 시나리오에 대하여 발전량을 결정하는 2단계 의사결정모형을 적용한다. 표현의 일관성을 위하여, 본 연구에서는 모든 최적화 모형을 비용을 최소화하는 모형으로 표현하며, 본 문제를 표현하기 위해 사용되는 집합, 인덱스, 파라미터 등은 <Table 1>에 정리하였다. 불확실한 전력 가격의 시나리오 s와, 매 시구간 t에 대해 단위 발전량에 대한 순비용계수는 가변비용 계수에서 전력 가격을 제한값으로 정의하며, b_s,t로 명명하였다. 모든 시나리오에 대해 기대 순비용을 최소화하는 확률적 단일발전원 계획문제의 수리모형은 다음과 같다.

$\[ \text{min}\sum _{t\in T}\left(C_t^{ON}{x}_t+C_t^U{x}_t^U+C_t^D{x}_t^D\right)+\sum _{s\in S,t\in T}{p}_s{b}_{s,t}{y}_{s,t} \]$

(1)

$\[ \begin{array}{l}s\text{.}t\text{.}\begin{array}{l} x_k\ge x_t-x_{t-1},\hfill \\ \forall k\in \left\{t+1,\cdots ,\text{min}\left\{t+t^U-1,N_T\right\}\right\},t\in T,\hfill \end{array}\hfill \end{array} \]$

(2)

$\[ \begin{array}{l}1-x_k\ge x_{t-1}-x_t,\hfill \\ \forall k\in \left\{t+1,\cdots ,\text{min}\left\{t+t^D-1,N_T\right\}\right\}, t\in T,\hfill \end{array} \]$

(3)

$\[ \begin{array}{ll}{x}_t^U-x_t^D=x_t-x_{t-1}, \hfill & \forall t\in T,\hfill \end{array} \]$

(4)

$\[ \begin{array}{ll}{P}^{\text{min}}{x}_t\le y_{s,t}\le P^{\text{max}}{x}_t,\hfill & \forall s\in S,t\in T,\hfill \end{array} \]$

(5)

$\[ \begin{array}{ll}{y}_{s,t}\le y_{s,t-1}+R{x}_{t-1}+\stackrel{-}{R}\left(1-x_{t-1}\right),\hfill & \forall s\in S,t\in T,\hfill \end{array} \]$

(6)

$\[ \begin{array}{l}\begin{array}{ll}{y}_{s,t-1}\le y_{s,t}+R{x}_t+\stackrel{-}{R}\left(1-x_t\right),\hfill & \forall s\in S,t\in T,\hfill \end{array}\hfill \\ \begin{array}{ll}{x}_t,x_t^U,x_t^D\in \left\{\mathrm{0,1}\right\},y_{s,t}\ge 0,\hfill & \forall s\in S,t\in T.\hfill \end{array}\hfill \end{array} \]$

(7)

Table 1.

Nomenclature

목적 함수 (1)은 모든 시나리오에 대한 기대 발전비용이며, 발전비용은 고정비용과 가변비용으로 구성된다. 제약식 (2)와 (3)은 발전원이 한번 기동/정지하게 되면 그 상태를 유지해야 하는 최소한의 시간을 나타낸다. 여기서, x₀은 초기 발전상태이며, y_s,0는 각 시나리오 s ∈ S에 대한 초기 발전량이다. 다음으로, 제약식 (4)는 발전상태 변수와 기동/정지 변수 간의 논리적 관계를 나타낸다. 또한, 제약식 (5)는 발전원이 켜져 있을 때의 최소 및 최대 발전량을 제한한다. 마지막으로, 제약식 (6)과 (7)은 증/감발 제약으로, 인접한 두 시구간 사이의 증가하거나 감소하는 발전량의 상한을 의미한다.

2.2 동적계획 알고리듬

본 연구에서는, 다수의 시나리오 하의 확률적 단일발전원 계획문제를 효과적으로 해결하기 위하여 동적계획 알고리듬을 제안한다. 이는 기존에 확정적인 전력 가격 하의 단일발전원 계획문제에 제안된 동적계획 알고리듬(Frangioni and Gentile, 2006, 2015)을 확장한 해법이다. 우선, 발전상태를 구하기 위하여 기존의 연구에서 제안된 상태-공간 그래프(state-space graph)를 이용하여 문제를 <Figure 1>로 시각화한다. 그래프에서의 각 마디는 특정 시구간에서의 발전상태에 대응되며, 시작 마디 s부터 종료 마디 t까지의 경로는 발전원의 전체 계획기간동안의 발전상태를 나타낸다. 각 시구간 t ∈ T에 대해 두 가지 유형의 마디 ON_t와 OFF_t가 정의된다. 마디 ON_t는 시구간 t에서 발전원이 가동됨을 나타내며, 이는 t-1번째 시구간에서 발전원이 정지상태임을 의미한다. 마찬가지로 마디 OFF_t는 시구간 t 직후에 발전원이 꺼짐을 나타내며, 이는 t+1번째 시구간부터 발전원이 정지상태가 됨을 의미한다. 또한 서로 다른 유형의 마디 간의 호는 제약식 (2)-(3)의 최소 가동/정지 시간 조건이 충족될 때만 연결하도록 설정한다. 구체적으로, h,k ∈ T에 대해, 마디 ON_h에서 마디 OFF_k로의 호는 k ≥ h+t^U-1를 만족할 때만 연결한다. 마찬가지로 마디 OFF_h에서 마디 ON_k까지의 호는 k ≥ h+t^D+1를 충족시키는 경우에만 연결한다. 이를 통해, 상태-공간 그래프에서의 최단 경로를 구함으로써 확률적 단일발전원 계획문제의 최적해를 구할 수 있다.

Figure 1.

Illustration of a State-space Graph on Obtaining On/Off Decisions

상태-공간 그래프를 활용할 때, 전체 호의 비용을 사전에 효율적으로 계산하는 것이 중요하다. 마디 OFF_h와 ON_k를 연결하는 호의 비용은 시구간 k에서의 기동비용인 $$ C_k^U$$이다. 반면, 마디 ON_h와 OFF_k를 연결하는 호의 비용은 발전원이 시구간 h부터 k까지 가동될 동안의 기대 운영비용으로, 고정비용($$ C_k^D+\sum _{t=h}^k{C}_t^{ON}$$)과 기대 가변 발전비용을 합한 값이다. 각 시나리오 s ∈ S에 대해 가변 발전비용 z^D(s, h, k)을 다음과 같은 최적화 모형 D(s,h,k)의 최적 비용으로 정의할 때, 기대 가변 발전비용은 $$ \sum _{s\in S}{p}_s{z}^D\left(s,h,k\right)$$이다.

$\[ z^D\left(s,h,k\right):=\begin{array}{l}\text{min}\sum _{t\in \left[h,k\right]}{b}_{s,t}{q}_t\hfill \\ s.t.\begin{array}{l}{P}^{\text{min}}\le q_t\le P^{\text{max}}, \forall t\in \left[h,k\right],\hfill \\ q_h\le \stackrel{-}{R},\hfill \\ q_k\le \stackrel{-}{R},\hfill \\ q_{t+1}\le q_t+R, \forall t\in \left[h,k-1\right],\hfill \\ q_t\le q_{t+1}+R, \forall t\in \left[h,k-1\right].\hfill \end{array}\hfill \end{array} \]$

편의상, 두 정수 a와 b에 대해 $$ \left[a,b\right]:=\left\{v\in Z|a\le v\le b\right\}$$로 정의하였다. 이 문제는 상용 최적화 solver로 쉽게 해결할 수 있는 선형계획 문제이다. 그러나 계획기간의 모든 시구간의 조합과 전체 N_S개의 시나리오를 다룰 때 더욱 효율적인 해법이 필요하다. 본 연구에서는 다수의 가변 발전비용 $$ {\left\{z^D\left(s,h,k\right)\right\}}_{s\in S,h,k\in T}$$들을 효율적으로 계산하기 위하여 추가적인 동적계획 알고리듬을 제안한다.

제안한 해법은 선행 연구에서 증명된 D(s,h,k)의 최적해의 특징을 기반으로 한다. 이는 다음과 같이 개수가 유한한 발전량 집합 Q을 정의하였을 때, Q에 속한 발전량의 조합 중 최적해가 존재한다는 것이다(Guan et al., 2018). 집합 Q은 그 속한 모든 원소의 발전량이 최소(P^min)와 최대(P^max) 가능 발전량 사이이며, 정수 n에 대해 P^min+nR, P^max+nR, $$ \stackrel{-}{R}+nR$$, $$ \overline{R}-nR$$ 중 하나 이상을 만족하는 발전량의 집합으로 정의된다.

이를 바탕으로 D(s,h,k)의 최적해를 도출하는 동적계획 알고리듬을 제시한다. 각 발전량 q ∈ Q에 대해 Q(q)를 Q에 속하며 발전량 q와 증/감발 제약을 만족시키는 발전량의 집합으로 정의한다. 즉, Q(q) := {q′ ∈ Q | q-R ≤ q′ ≤ q+R}이다. 주어진 시나리오 s에 대해 시구간 집합 [h,k]에서, 마지막 시구간 k의 발전량이 q일 때의 최적 비용을 z′(s,h,k,q)로 정의한다. 그러면 재귀 방정식을 다음과 같이 작성할 수 있다.

$\[ \begin{array}{c}{z}^{\mathrm{\text{'}}}\left(s,h,h,q\right)=\left\{\begin{array}{ccc}\begin{array}{c}{b}_{s,h}q\hfill \\ \mathrm{\infty }\hfill \end{array}\hfill & \begin{array}{c}\text{if }q\le \stackrel{-}{R}\hfill \\ otherwise\hfill \end{array},\hfill & \forall s\in S,h\in T,q\in Q,\hfill \end{array}\right.\hfill \\ z^{\mathrm{\text{'}}}\left(s,h,h,q\right)=\begin{array}{l}\underset{q^{\mathrm{\text{'}}}\in Q\left(q\right)}{\text{min}} \left\{z^{\mathrm{\text{'}}}\left(s,h,k-1,q\right)+b_{s,k}{q}^{\mathrm{\text{'}}}\right\} ,\hfill \\ \forall s\in S,h\in T,k\in \left[h+1,N_T\right],q\in Q .\hfill \end{array}\hfill \end{array} \]$

(8)

최적 비용 z^D(s,h,k)는 수식 (9)와 같이 마지막 시구간 k에서의 발전량 q가 증/감발 제약을 만족할 때의 z′(s,h,k,q) 중 최소 비용이 된다.

$\[ \begin{array}{l}{z}^D\left(s,h,k\right)=\begin{array}{l}\underset{q\in Q}{\text{min}} \left\{z^{\mathrm{\text{'}}}\left(s,h,k,q\right) | q\le \stackrel{-}{R}\right\},\hfill \\ \forall s\in S,h\in T,k\in \left[h,N_T\right].\hfill \end{array}\hfill \\ \hfill \end{array} \]$

(9)

최적 비용을 구하는 과정을 <Figure 2>의 예시와 같이 최단 경로 문제로 변환할 수 있으며, 예시에서 유한개의 발전량 대안들의 집합은 Q= {q₁,q₂,q₃,q₄}로 정의하였다. 단, $$ q_1>\overline{R}\ge q_2>q_3>q_4$$ 이다. 또한, 식 (8)과 식 (9)를 고려하면, 주어진 s ∈ S, h,k∈ T와 모든 q ∈ Q에 대해 z′(s,h,k,q) 값을 구할 때, $$ {\left\{z^D\left(s,h,t\right)\right\}}_{t\in \left[h,k-1\right]}$$의 값을 동시에 추출할 수 있다. 이는 주어진 s ∈ S h ∈ T에 대해 k ∈ [h, N_T]로 단 한 번의 재귀를 수행함으로써 일련의 최적 비용 $$ {\left\{z^D\left(s,h,k\right)\right\}}_{k\in \left[h,N_T\right]}$$를 얻을 수 있음을 보여준다. 즉, 제안한 동적계획 알고리듬은 주어진 시구간 집합 T의 모든 시구간 쌍 (h,k)에 대한 가변 발전비용을 계산할 때 그 이점이 증가한다.

Figure 2.

Illustration of a Dynamic Programming Approach to Solve D(s,h,k)

3. 확률적 발전계획문제에 대한 발전원 분해기법

4. 실험 결과

4.2 확률적 단일발전원 계획문제에 대한 동적계획 알고리듬의 효과성

먼저 확률적 단일발전원 계획문제에 대한 최적화 해법들의 성능을 비교하였다. 전체 7개의 발전원 정보를 Kazarlis et al.(1996)을 참고하여 생성하였으며, 각 발전원별 상세 정보는 <Table 2>와 같다. 각 시나리오 s ∈ S와 각 시구간 t ∈ T별 순비용 계수 $$ {\left(b_{s,t}\right)}_{s\in S,t\in T}$$는 균등 분포 U[0,20]에서 추출하였다. 본 연구에서 제안하는 동적계획 알고리듬을 DP+DP로 표현하고, 이를 다른 두 가지 최적화 해법 MIP 및 DP+LP와의 성능을 비교하였다. 먼저 MIP는 상용 solver를 사용하여 해당 문제를 해결하는 방법이다. 다음으로 DP+LP는 기존 문헌에서 적용된 기본적인 동적계획 기반 해법이다. 이 해법에서는 2.2절의 <Figure 1>에서와 같이 동적계획법을 이용하여 발전상태를 결정하며, 가변 발전비용 $$ {\left(D\left(s,h,k\right)\right)}_{s\in S,h,k\in T}$$을 구할 때 해당 선형계획 문제를 일반적인 최적화 소프트웨어를 이용하여 계산한다. 본 연구에서 제안한 방법인 DP+DP는 2.2절의 <Figure 1>에서와 같이 동적계획법을 이용하여 발전상태를 결정한다는 점에서 DP+LP와 공통점을 가지지만, 가변 발전비용을 <Figure 2>에서와 같이 새롭게 제안된 동적계획 알고리듬을 통해 계산한다는 점에서 차이가 있다. 최소 1개부터 최대 10,000개까지의 다양한 수의 시나리오에 대해 세 가지 최적화 해법의 7개의 발전원에 대한 평균 계산시간을 로그 단위로 <Figure 3>에 나타내었다. 실험 결과는 제안한 해법 DP+DP의 우수한 계산성능을 보여준다. 이 해법은 대부분의 시나리오 수에 대해 가장 적은 계산시간이 소요되었으며, 시나리오 수의 증가에 따른 계산시간 증가가 가장 완만하게 나타났다. 반면, MIP는 시나리오 수가 적을 때 우수한 계산성능을 보이지만, 시나리오 수에 대한 계산시간 증가율이 세 가지 해법 중 가장 높게 나타났다. 또한, 해법 DP+LP은 적은 수의 시나리오에 대해서 가장 많은 계산시간을 보였지만, 많은 수의 시나리오에 대해서는 MIP 방법과 비슷한 성능을 보였다. 이는 발전상태만을 분해하는 동적계획 알고리듬 또한 시나리오 수의 증가에 효과적으로 대응함을 시사한다.

Table 2.

Characteristics of Generators

Figure 3.

Computation Times of Solution Approaches for the Stochastic Single-Unit Commitment Problem

4.3 확률적 발전계획문제에 대한 발전원 분해기법의 효과성

다음으로 확률적 발전계획문제에 대하여 제안한 분해기법의 성능을 분석한다. 54개의 발전원을 가진 전력 시스템의 발전원 특성 및 전력 수요의 정보를 Zimmerman et al.(2010)에서 추출하였다. 문헌에서 주어진 단일 시구간의 수요에 0.5~1.5에서 추출된 난수를 곱하여 모든 시구간에 대한 표준 수요 벡터 $$ \stackrel{-}{d}$$를 생성하고, 수요 시나리오를 정규 분포 $$ \mathrm{N}\left(\stackrel{-}{d},{\left(0.1\stackrel{-}{d}\right)}^2\right)$$에서 생성하였다. 시나리오 수는 최소 1개부터 최대 1,000개까지의 다양한 수를 사용하였다. 발전원 분해기법에서 라그랑지안 승수를 개선하기 위하여 문헌들에서 널리 사용된 subgradient방법을 이용하였고(Wolsey, 2020), n번째 반복단계에서의 stepsize는 $$ \frac{1}{N_G{N}_S}{\left(0.98\right)}^n$$으로 사용하였다. 초기 라그랑지안 승수는 모든 원소의 값이 1인 벡터로 설정하였으며, 해법 종료를 위한 반복단계의 최대 횟수는 250개로 설정하였다. 매 반복단계의 부문제인 확률적 단일발전원 계획문제는 제2장에서 제안한 동적계획 알고리듬으로 해결하였다. 모든 인스턴스에 대한 제한 시간은 5시간으로 설정하였다.

우선, 제안한 분해기법의 상/하한 수렴 추이를 표현하기 위하여 시나리오 수가 1개인 작은 규모의 발전계획문제에 대해 분해기법을 적용하여 <Figure 4>로 도식화하였다. 1개의 전력 수요 시나리오를 고려하는 확률적 발전계획문제는 전력의 수요가 확정적인 발전계획모형과 동등하며, 본 연구에서 제안한 모형과 해법이 적용할 수 있다. 실험 결과, 제안한 분해기법은 50회 이내 초기 반복단계에서는 좋은 하한과 상한을 도출하지 못하였지만, 그 이후 반복단계가 진행됨에 따라 상/하한을 모두 효과적으로 개선하였다. 반복횟수가 150회 이후인 경우, 상한 및 하한의 개선이 충분히 진행되어, 반복단계가 증가함에 따라 그 개선이 뚜렷하지는 않았다.

Figure 4.

Lower and Upper Bounds Trajectories of the Proposed Solution Approach for NS=1

다음으로, 다양한 수의 시나리오를 가진 모형에 대해 각각 250번의 반복단계 후 얻어진 상/하한을 <Figure 5>로 시각화하였다. 그리고 상한(UB)과 하한(LB)의 성능을 확장모형을 상용 solver로 해결하여 얻어진 목적함수값(MIP)과 선형완화(LP)와 비교하였다. 실험 결과, 제안한 최적화 해법의 상/하한이 상용 solver를 통해 해결하는 방법과 유사한 값을 가짐을 확인하였다. 우선, 발전원 분해기법의 상한은 MIP와 비교한 optimality gap이 평균적으로 1.5% 이내임을 확인하였으며, 그 차이는 시나리오 수가 증가함에 따라 감소하는 경향을 보였다. 다음으로, 하한은 대부분의 인스턴스에 대해 LP보다 좋음을 확인하였는데, 이는 3.3절의 Proposition 1의 결과와 일치한다. 시나리오 수가 증가함에 따라 라그랑지안 완화의 개선이 더디게 진행되어 하한이 선형완화보다 좋지 않은 경우가 있었지만, 그 차이가 0.1% 이내임을 확인하였다.

Figure 5.

Lower and Upper Bounds of the Proposed Solution Approach with Regard to Various Numbers of Scenarios

마지막으로, 다양한 수의 시나리오에 대해 제안한 발전원 분해기법(UD)의 계산시간을 확장모형을 상용 solver를 통해 해결하는 방법(EXTS)과 비교하였다. 계산시간은 로그 단위로 나타내어 <Figure 6>에 도식화하였다. 각 시나리오 수에 대한 두 방법의 제한 시간은 5시간(18,000초)이다. 실험 결과, 두 해법 모두 시나리오 수의 증가에 따라 계산시간이 증가하는 경향을 보였다. 특히 MIP의 경우 계산시간의 증가가 더욱 가파른 경향을 보이며, 시나리오가 500개 이상일 경우에는 변수 및 제약식의 방대한 개수로 인한 메모리 한계로 인하여 최적해를 제한 시간 내 도출하지 못하였다. 시나리오 개수가 500개인 경우, 제한 시간 내에 얻어진 가장 좋은 가능해의 목적함수값을 표시하였으며, 시나리오 개수가 1,000개인 경우, 제한 시간 내 가능해를 도출하지 못하여 표시하지 않았다. 하지만 제안한 최적화 해법은 시나리오 수가 증가함에 따른 계산 부담이 각 부문제로 배분되기 때문에 계산시간의 상승세가 완만하였다. 즉, 본 연구에서 제안한 발전원 분해기법은 매 반복단계별 상한 및 하한을 도출할 수 있으며 각 반복단계의 계산 부담이 크지 않아 시나리오의 개수가 많을 경우 특히 효과적이다.

Figure 6.

Computation Times of the Proposed Solution Approach with Regard to Various numbers of Scenarios

5. 결론

본 연구는 불확실한 전력 수요의 시나리오 하에서 기대 비용을 최소화하는 확률적 발전계획문제를 탐구하였다. 다수의 시나리오 하의 모형을 효과적으로 해결하기 위하여, 발전원간 연결 제약을 완화한 라그랑지안 완화를 상한 생성 방법과 결합하여 매 반복단계에서 하한과 상한을 도출하는 발전원 분해기법을 제안하였다. 또한, 발전원 분해기법의 매 반복단계의 부문제인, 하나의 발전원의 발전상태와 발전량을 결정하는 확률적 단일발전원 계획문제에 대해 효율적인 동적계획 알고리듬을 제안하였다. 다양한 수치 실험을 통해 제안한 동적계획 알고리듬이 다수의 시나리오 하의 확률적 단일발전원 계획문제를 기존 해법과 대비하여 적은 시간 내 효과적으로 해결할 수 있음을 확인하였다. 또한, 2단계 확률적 발전계획모형에 대해, 확장모형을 상용 solver를 통하여 해결하는 것이 어려운 다수의 시나리오 상황에서도 제안한 발전원 분해기법이 안정적으로 우수한 성능의 상/하한을 도출함을 확인하였다. 본 연구에서 제안된 최적화 해법들은 다수의 발전원을 고려하거나, 수요의 불확실성에 대응하기 위하여 다수의 시나리오를 고려하여 발전계획모형의 규모가 증가하는 상황에서 효과적으로 적용 가능함을 시사한다.

추후 연구 과제로, 상한을 구하는 방법을 정교화하여 상한의 성능을 개선하는 것을 고려할 수 있다. 또한, 수요 충족 제약뿐만 아니라 추가적인 제약을 완화하는 발전원 분해기법을 탐구할 수 있다. 마지막으로, 라그랑지안 완화 외에도 열 생성 방법 등 다양한 분해기법에 기반한 최적화 해법을 개발할 수 있다.

Acknowledgments

이 논문은 2021년도 정부(과학기술정보통신부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임(No. 2021R1A2C2005531).

References

• Carpentier, P., Gohen, G., Culioli, J. C., and Renaud, A. (1996), Stochastic Optimization of Unit Commitment: A New Decomposition Framework, IEEE Transactions on Power Systems, 11(2), 1067-1073. [https://doi.org/10.1109/59.496196]
• Damcı-Kurt, P., Küçükyavuz, S., Rajan, D., and Atamtürk, A. (2016). A polyhedral study of production ramping. Mathematical Programming, 158, 175-205. [https://doi.org/10.1007/s10107-015-0919-9]
• Fan, W., Guan, X., and Zhai, Q. (2002), A new Method for Unit Commitment with Ramping Constraints, Electric Power Systems Research, 62(3), 215-224. [https://doi.org/10.1016/S0378-7796(02)00043-3]
• Frangioni, A. and Gentile, C. (2006), Solving Nonlinear Single-unit Commitment Problems with Ramping Constraints, Operations Research, 54(4), 767-775. [https://doi.org/10.1287/opre.1060.0309]
• Frangioni, A. and Gentile, C. (2015), New MIP Formulations for the Single-unit Commitment Problems with Ramping Constraints, IASI Annual Research Reports.
• Frangioni, A., Gentile, C., and Lacalandra, F. (2008), Solving Unit Commitment Problems with General Ramp Constraints, International Journal of Electrical Power & Energy Systems, 30(5), 316-326. [https://doi.org/10.1016/j.ijepes.2007.10.003]
• Guan, Y., Pan, K., and Zhou, K. (2018), Polynomial Time Algorithms and Extended Formulations for Unit Commitment Problems, IISE transactions, 50(8), 735-751. [https://doi.org/10.1080/24725854.2017.1397303]
• Kazarlis, S. A., Bakirtzis, A. G., and Petridis, V. (1996), A Genetic Algorithm Solution to the Unit Commitment Problem, IEEE Transactions on Power Systems, 11(1), 83-92. [https://doi.org/10.1109/59.485989]
• Knueven, B., Ostrowski, J., and Wang, J. (2018), The Ramping Polytope and cut Generation for the Unit Commitment Problem, INFORMS Journal on Computing, 30(4), 739-749. [https://doi.org/10.1287/ijoc.2017.0802]
• Lee, J., Leung, J., and Margot, F. (2004), Min-up/min-down Polytopes, Discrete Optimization, 1(1), 77-85. [https://doi.org/10.1016/j.disopt.2003.12.001]
• Nowak, M. P. and Römisch, W. (2000), Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-thermal System Under Uncertainty, Annals of Operations Research, 100, 251-272. [https://doi.org/10.1023/A:1019248506301]
• Ostrowski, J., Anjos, M. F., and Vannelli, A. (2011), Tight Mixed Integer Linear Programming Formulations for the Unit Commitment Problem, IEEE Transactions on Power Systems, 27(1), 39-46. [https://doi.org/10.1109/TPWRS.2011.2162008]
• Pan, K. and Guan, Y. (2016), Strong Formulations for Multistage Stochastic Self-scheduling Unit Commitment, Operations Research, 64(6), 1482-1498. [https://doi.org/10.1287/opre.2016.1520]
• Rajan, D. and Takriti, S. (2005), Minimum Up/down Polytopes of the Unit Commitment Problem with Start-up costs, IBM Res. Rep, 23628, 1-14.
• Shiina, T. and Birge, J. R. (2004), Stochastic Unit Commitment Problem, International Transactions in Operational Research, 11(1), 19-32. [https://doi.org/10.1111/j.1475-3995.2004.00437.x]
• Van Ackooij, W., Danti Lopez, I., Frangioni, A., Lacalandra, F., and Tahanan, M. (2018), Large-scale Unit Commitment Under Uncertainty: An Updated Literature Survey, Annals of Operations Research, 271(1), 11-85. [https://doi.org/10.1007/s10479-018-3003-z]
• Wolsey, L. A. (2020), Integer Programming, John Wiley & Sons. [https://doi.org/10.1002/9781119606475]
• Wuijts, R. H., van den Akker, M., and van den Broek, M. (2021), An Improved Algorithm for Single-unit Commitment with Ramping Limits, Electric Power Systems Research, 190, 106720. [https://doi.org/10.1016/j.epsr.2020.106720]
• Zimmerman, R. D., Murillo-Sánchez, C. E., and Thomas, R. J. (2010), MATPOWER: Steady-state Operations, Planning, and Analysis Tools for Power Systems Research and Education, IEEE Transactions on Power Systems, 26(1), 12-19. [https://doi.org/10.1109/TPWRS.2010.2051168]