기술 요약: 답변 집합 프로그래밍을 통한 장기 전력망 계획

문제 정의

본 논문은 배전 시스템 운영자 (DSO) 에게 중요한 과업인 장기 전력망 계획 (LPP) 문제를 다룹니다. 이 과정은 현재 전력망 구성을 장기적 시간 범위 (일반적으로 최대 30 년) 에 걸쳐 원하는 목표 구성으로 진화시키기 위해 선 추가, 제거, 스위치 조작과 같은 물리적 개입의 순서를 정의하는 것을 포함합니다.

핵심적인 과제는 이러한 진화 과정에서 생성되는 모든 중간 구성이 운영상 유효하도록 보장하는 데 있습니다. 정적 계획이나 단기 재구성과는 달리, LPP 는 전환의 각 단계에서 복잡한 일련의 위상적 및 조합적 불변 조건을 충족해야 합니다. 이러한 제약 조건에는 다음이 포함됩니다:

• 방사형 (Radiality): 폐회로 네트워크는 비순환적이어야 하며, 각 2 차 변전소는 정확히 하나의 1 차 변전소에서 전력을 공급받아야 합니다.
• 재구성 가능성 (고장 내성): 네트워크는 임의의 1 차 노드의 고장 발생 시 스위칭 조작을 통해 방사형 상태를 복원할 수 있어야 합니다.
• 차수 준수: 2 차 변전소는 특정 수의 연결 (일반적으로 2 개 또는 3 개) 을 유지해야 합니다.
• 비가역성과 실현 가능성: 목표 네트워크에 존재하는 선로만 추가할 수 있고, 목표 네트워크에 부재하는 선로만 제거할 수 있습니다. 이러한 조작은 비가역적입니다.

현재의 관행은 수동 전문가 지식과 반복적 조정에 크게 의존하여 재현성, 확장성, 그리고 대안 투자 경로의 체계적 탐색을 제한합니다. 혼합 정수 선형 계획법 (MILP) 과 같은 기존 방법들은 방사형성과 같은 순수 조합적 속성을 처리하는 데 어려움을 겪는 반면, 표준 계획 언어는 그래프 불변 조건을 표현하는 데 번거로움을 느낍니다.

방법론

저자들은 답변 집합 프로그래밍 (ASP) 을 사용하여 LPP 를 해결하는 최초의 자동화 접근법을 제안합니다. ASP 는 지식 집약적 조합 문제에 적합한 선언적 논리 프로그래밍 패러다임입니다.

형식화

전력망은 무방향 엣지 라벨 그래프 $G(V, E, \lambda)$로 모델링되며, 여기서 노드는 1 차 및 2 차 역을 나타내고 엣지는 "개방" 또는 "폐쇄"로 라벨링된 선로를 나타냅니다. 이 문제는 초기 그래프 $G$를 목표 그래프 $G_T$로 변환하는 행동 집합의 순서 $(A_0, \dots, A_n)$를 계산하는 것으로 정의되며, 이때 모든 중간 상태 $G_i$가 DSO 규칙을 만족해야 합니다.

저자들은 세 가지 유형의 행동을 정의합니다:

1. 엣지 추가: 개방된 네트워크에 새로운 엣지를 추가합니다.
2. 엣지 제거: 기존에 개방된 엣지를 제거합니다.
3. 엣지 스위칭: 동일한 2 차 역에 인접한 두 엣지의 상태를 교환합니다 (개방된 선로를 폐쇄하고 폐쇄된 선로를 개방).

중요하게도, 이 프레임워크는 병렬 계획을 지원하여 상호 간섭하지 않는 행동 (서로소인 엣지 집합에 영향을 미치는 행동) 을 단일 시간 단계 내에서 동시에 실행할 수 있게 합니다.

ASP 인코딩

해결책은 CLINGO 솔버를 활용합니다. 인코딩은 이산 시간 단계 $t$에 걸친 네트워크의 진화를 모델링합니다. 주요 구성 요소는 다음과 같습니다:

• 상태 표현: 술어는 각 시간 단계에서 엣지의 상태 (개방/폐쇄) 를 추적합니다.
• 행동 생성: 선택 규칙은 구축 가능하고 제거 가능한 엣지 집합에 의해 제약된 추가, 제거, 스위칭의 유효한 순서를 생성합니다.
• 제약 조건 강제:
  • 방사형: 폐회로 네트워크가 1 차 노드를 루트로 하는 숲 (포레스트) 이 되도록 강제합니다 (1 차 노드 간에 사이클이 없으며, 모든 2 차 노드가 정확히 하나의 1 차 노드에 연결됨).
  • 재구성 가능성: 개방된 네트워크를 통해 모든 2 차 노드가 다른 1 차 노드로 가는 중복 경로를 갖는지 확인함으로써 강제합니다.
  • 차수 준수: 2 차 노드의 차수를 집계하여 $[2, 3]$ 범위를 강제합니다.
• 최적화: 약한 제약 조건을 사용하여 행동의 총 수와 계획 길이 (사전적 순서) 를 최소화합니다.

이 접근법은 순차적 ($|A_i|=1$) 및 병렬 ($|A_i| \ge 1$) 실행 모드 모두를 지원합니다.

주요 기여

1. 최초의 ASP 기반 자동화: 이 연구는 필요한 모든 전력망 위상적 제약을 처리할 수 있는 장기 전력망 계획을 자동화하는 최초의 접근법을 제시합니다.
2. 표현력 있는 모델링: 저자들은 ASP 가 계획 언어나 MILP 에서 표현하기 어려운 복잡한 그래프 이론적 불변 조건 (방사형성, 재구성 가능성) 을 우아하게 인코딩할 수 있음을 입증했습니다.
3. 병렬 실행 프레임워크: 이 인코딩은 병렬 행동 실행을 지원하며, 저자들은 순차적 접근법에 비해 유효한 검색 공간과 계획 길이를 크게 단축시킨다고 밝혔습니다.
4. 실제 데이터에 대한 검증: 이 접근법은 합성 인스턴스와 프랑스 배전망에서 파생된 실제 데이터 모두에서 검증되었으며, 이는 일일 전문가 작업 규모와 비교 가능합니다.

실험 결과

저자들은 64 비트 Linux 머신에서 CLINGO 솔버를 사용하여 각 인스턴스당 30 분의 시간 제한으로 실험을 수행했습니다.

• 합성 인스턴스: 이 연구는 8 개에서 50 개 노드에 이르는 175 개의 합성 인스턴스를 평가했습니다.

  • 병렬 대 순차적: 병렬 계획은 일관되게 순차적 계획보다 더 많은 인스턴스를 해결했습니다. 상호 간섭하지 않는 행동을 통한 솔루션 길이의 "압축"은 더 작은 논리 프로그램과 더 빠른 해결 시간을 초래했습니다.
  • 검색 전략: 병렬 계획의 경우, 지수적 검색 전략 (시간 범위를 점진적으로 확장) 이 경계 검색보다 우수한 성과를 보이며 훨씬 더 많은 인스턴스를 해결했습니다. 반면, 순차적 계획의 경우 경계 검색이 더 효과적이었습니다.
  • 확장성: 이 접근법은 최대 50 개 노드의 인스턴스를 성공적으로 해결했으며, 가장 큰 실제 인스턴스 (약 40 개 노드) 는 인간 전문가가 처리하는 것과 비교 가능한 규모였습니다.

• 실제 인스턴스: 프랑스 도시 네트워크 (2 개의 1 차 노드, 다양한 2 차 노드) 에서의 익명화된 데이터를 사용하여, 시스템은 최대 42 개 노드의 인스턴스를 해결했습니다.

  • 실행 시간: 실행 시간은 유사한 크기의 합성 인스턴스와 비교 가능했습니다.
  • 최적성: 해결된 여러 인스턴스에 대해 시스템은 병렬 계획의 최적성을 증명했습니다.
  • 검증: 솔루션은 자동화된 도구에 의해 검증되었고 도메인 전문가에 의해 시각적으로 검토되었으며, 이들은 DSO 계획 규칙과의 일관성과 전문가가 생성한 솔루션과의 위상적 비교 가능성을 확인했습니다.

중요성과 주장

본 논문은 제안된 ASP 기반 접근법이 현재 수동적이고 전문가 주도적인 장기 전력망 계획 과정에 대한 실현 가능한 자동화 대안을 제공한다고 주장합니다. 인간 전문가가 관리하는 규모와 비교 가능한 인스턴스를 성공적으로 해결함으로써, 이 방법은 복잡한 인프라 제약을 모델링하기 위한 ASP 의 표현력을 입증합니다.

저자들은 그들의 솔루션이 대규모 조합 공간에서 실현 가능한 진화 전략을 식별하는 "주요 병목 현상"을 해결한다고 강조합니다. 그들은 이 작업을 인간 전문성을 보완하고 재현성을 개선하며 투자 경로를 체계적으로 탐색할 수 있는 지능형 의사결정 지원 도구를 향한 기초적인 단계로 위치시킵니다. 이 논문은 즉각적인 산업 배포에 대해서는 겸손하게 접근하며, 도메인 특화 휴리스틱을 통해 확장성을 더욱 개선하고 예산 한도, 구성 요소 불변성 등 추가적인 인프라 특정 요구 사항에 적응하기 위한 향후 작업이 필요하다고 언급합니다.