技術的サマリー：答集合プログラミングによる長期電力網計画

問題定義

本論文は、配電システム事業者（DSO）にとって重要な課題である「長期電力網計画（LPP）」問題に取り組みます。このプロセスには、現在の電力網構成を長期（通常は最大 30 年）にわたって望ましい目標構成へと進化させるための物理的介入（送電線の追加、除去、およびスイッチ操作）のシーケンスを定義することが含まれます。

核心的な課題は、この進化の過程で生成されるすべての中間構成が運用上妥当であることを保証することにあります。静的な計画や短期間の再構成とは異なり、LPP は遷移の各段階において、複雑なトポロジー的および組合せ的な不変条件のセットを満たさなければなりません。これらの制約には以下が含まれます：

• 放射状性（ラジアル性）： 閉回路網は非巡回でなければならず、各二次変電所は exactly 1 つの一次変電所から供給されなければなりません。
• 再構成可能性（耐故障性）： 任意の一次ノードの故障が発生した場合、スイッチ操作を通じて放射状性を回復できる必要があります。
• 次数適合性： 二次変電所は、特定の数の接続（通常は 2 または 3）を維持しなければなりません。
• 不可逆性と実現可能性： 目標網に存在する線のみを追加でき、目標網に存在しない線のみを除去できます。これらの操作は不可逆です。

現在の慣行は、専門家の知識と反復的な調整に大きく依存しており、再現性、スケーラビリティ、および代替投資軌道の体系的な探索を制限しています。混合整数線形計画（MILP）などの既存の手法は、放射状性のような純粋に組合せ的な性質に苦しんでおり、標準的な計画言語ではグラフ不変条件の表現が煩雑です。

手法

著者らは、知識集約的な組合せ問題に適した宣言的論理プログラミングパラダイムである**答集合プログラミング（ASP）**を用いて LPP を解決する初の自動化アプローチを提案します。

定式化

電力網は、ノードが一次および二次変電所を表し、エッジが「開放」または「閉鎖」とラベル付けされた線を表す、無向の辺ラベル付きグラフ $G(V, E, \lambda)$ としてモデル化されます。この問題は、初期グラフ $G$ を目標グラフ $G_T$ に変換する動作セットのシーケンス $(A_0, \dots, A_n)$ を計算することとして定義され、各中間状態 $G_i$ が DSO の規則を満たすようにします。

著者らは 3 種類の動作を定義します：

1. エッジ追加： 開放ネットワークに新しいエッジを追加する。
2. エッジ除去： 既存の開放エッジを除去する。
3. エッジ切り替え： 同じ二次変電所に隣接する 2 つのエッジの状態を交換する（開放線を閉鎖し、閉鎖線を開放する）。

重要なのは、このフレームワークが並列計画をサポートしており、互いに干渉しない動作（互いに排他的なエッジ集合に影響を与える動作）を単一の時間ステップ内で同時に実行できることです。

ASP エンコーディング

この解法にはCLINGOソルバーが使用されます。エンコーディングは、離散的な時間ステップ $t$ におけるネットワークの進化をモデル化します。主要なコンポーネントには以下が含まれます：

• 状態表現： 述語が各時間ステップにおけるエッジの状態（開放/閉鎖）を追跡します。
• 動作生成： 構築可能なエッジ集合と除去可能なエッジ集合によって制約された、有効な追加、除去、切り替えのシーケンスを生成する選択ルール。
• 制約強制：
  • 放射状性： 閉回路網が一次ノードを根とする森（一次間でのサイクルなし、すべての二次が exactly 1 つの一次に接続）であることを保証することで強制されます。
  • 再構成可能性： 開放ネットワークを介して、すべての二次ノードが異なる一次ノードへの冗長パスを持っていることを検証することで強制されます。
  • 次数適合性： 二次ノードの次数を集計し、範囲 $[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 つの一次ノード、変動する二次ノード）からの匿名化データを使用して、システムは最大 42 ノードのインスタンスを解決しました。

  • 実行時間： 実行時間は、同程度のサイズの合成インスタンスと同等でした。
  • 最適性： 解決されたいくつかのインスタンスにおいて、システムは並列計画の最適性を証明しました。
  • 検証： 解は自動化ツールによって検証され、ドメイン専門家によって視覚的にレビューされました。専門家は、DSO 計画規則との整合性と、専門家によって生成された解とのトポロジー的な比較可能性を確認しました。

意義と主張

本論文は、提案された ASP ベースのアプローチが、現在の手動かつ専門家主導である長期電力網計画プロセスに対する実行可能な自動化の代替案を提供すると主張しています。人間のエージェントが管理するものと同程度のサイズのインスタンスを正常に解決することで、この手法は複雑なインフラ制約のモデリングにおける ASP の表現力を実証しています。

著者らは、自らの解決策が、大規模な組合せ空間における実行可能な進化戦略の特定という「主要なボトルネック」に対処していると強調しています。この研究は、人間の専門知識を補完し、再現性を向上させ、投資軌道を体系的に探索するインテリジェントな意思決定支援ツールへの基礎的な一歩として位置づけられています。本論文は、即座の産業展開については控えめな見解を示しており、ドメイン固有のヒューリスティックによるスケーラビリティのさらなる向上と、予算制限やコンポーネントの不変性などの追加のインフラ固有の要件への適応には、今後の研究が必要であると指摘しています。