ＪＳＴ 課題達成型基礎研究の一環として、北海道大学 大学院情報科学研究科の湊 真一 教授らのグループは、早稲田大学 先進グリッド技術研究所の所長 林 泰弘 教授らと共同で、配電網の膨大なスイッチ構成（ＯＮ／ＯＦＦの組合せ）を調べる超高速アルゴリズム（計算手順）を開発しました。この技術を用いて、電力品質を満たしつつ、送電損失を最小化する最適構成を得ることに初めて成功しました。
近年、環境問題や東日本大震災の経験から、電力網制御の高度化、いわゆるスマートグリッド注１）の構築が喫緊の課題となっています。林教授らが調査し公表している日本における実用規模の標準的な配電網モデルでは、制御可能なスイッチは４６８個に及び、その構成の総数は１０進数で１４１桁の天文学的な数となります。最適な制御を実現するためには、この中から、幾何学的・電気的な制約条件を満たして、網内全域に正確かつ、効率的に給電できる構成を探索し、送電損失を最小にする構成を発見しなければなりません。しかし、従来は経験や実績に基づき比較的良いと思われる構成を得るにとどまっており、制約条件を満たす構成数や最適構成は分かっていませんでした。
本研究では、湊教授が独自に考案し、研究を進めている「ゼロサプレス型二分決定グラフ（ＺＤＤ）注２）」と呼ばれるデータ構造と、膨大な数の組合せをコンパクトに圧縮し超高速に演算するアルゴリズムによって、条件を満たす構成を全て探索し、索引化することに初めて成功しました。その結果、上記の配電網モデルにおいて条件を満たす構成の数は、正確に「２１３６８２０１３８３４８５３２９１１６８２６１２２１４８０４９０５６０９８１７８３９２４４３８５２３５３９８１８９５２１５４０通り（約１０の６３乗）」であることを示しました。さらに、この膨大な構成の中から送電損失を最小化する構成を見つけることにも成功しました。日本全体の配電網に単純換算した場合、想定した需要モデルにおける損失改善効果は最大で２７．９ＭＷ（一般家庭約１万軒分）、１時間あたりの二酸化炭素削減効果は１５．５トンと試算されました。
この成果により、これ以上は改善できない最適構成を正確に、短時間で得ることが初めて可能となりました。さらに本手法では制約条件を満たす構成を全て索引化しているため、配電網の運用上の都合や故障対応などの追加的な制約が発生したとしても柔軟に構成を絞り込むことができ、将来のスマートグリッドを支える基盤技術としての活用が期待されます。
本研究成果は、２０１２年電子情報通信学会 総合大会で開催される「ＥＲＡＴＯ湊離散構造処理系プロジェクトシンポジウム」（２０１２年３月２０日 岡山大学）で発表するとともに、その一部は電気学会 全国大会（２０１２年３月２３日 広島工業大学）でも発表されます。
本成果は、以下の事業・研究プロジェクトによって得られました。
戦略的創造研究推進事業 ＥＲＡＴＯ型研究
| 研究プロジェクト |
「湊離散構造処理系プロジェクト」 |
| 研究総括 |
湊 真一（北海道大学 大学院情報科学研究科 教授） |
| 研究期間 |
平成２１年～平成２６年 |
ＪＳＴはこのプロジェクトで、計算機が扱う大規模データをＢＤＤ／ＺＤＤと呼ばれるデータ圧縮手法を用いて、実問題を短時間に効率よく処理する技術基盤の構築を目指します。
＜研究の背景と経緯＞
近年、地球温暖化などの環境問題から太陽光や風力などの再生可能エネルギーに対する期待が高まっており、また、東日本大震災以降の電力不足も重なって、より効率的かつ安定した電力供給のために制御が高度化された電力網、いわゆる「スマートグリッド」を目指した研究に幅広い注目が集まっています。電力網は、数万ボルト以上の高電圧で発電所と変電所をつなぐ「送電網」と、一般家庭や事業所に低電圧の電力を供給する「配電網」に分けられ（図１）、各配電網は網内に多数のスイッチを備えており、その開閉状態を切り替えて、電力の供給路を決定しています（図２）。停電などを回避し、適正な品質の電力を供給するためには、複雑な制約条件を満たさなければなりません。しかし、林教授らが調査し公表している日本の実用規模の標準的な配電網モデルでは、制御可能なスイッチは４６８個に及び、その構成（組合せ）の総数は１０進数で１４１桁の天文学的な数にのぼり、この中から制約条件を満たす最適な構成を探索することは非常に難しい問題です。このため、従来は経験則（ヒューリスティック）に基づく手法によって、ごく一部の構成からなるべく良い構成を探索するにとどまっており、制約条件を満たす構成が全部で何通りあるか、またその中のどの構成が最適なのかは分かっていませんでした。このような従来手法では、探索漏れによってより良い構成を見逃すリスクがありますし、得られた構成が全体の中でどのくらい「良い」かが分かりません。さらに、最近では太陽光発電などの分散電源注３）が普及し、それらが接続される配電網は電力の流れが複雑化し、より高度な設計・制御が求められます。そこで本研究では、配電網を対象として制約条件を満たす構成数と最適構成を得る超高速探索アルゴリズムを開発しました。
＜研究の内容＞
（１）網羅的探索アルゴリズムの開発
本研究では、まずＺＤＤと呼ばれるデータ圧縮技法を用いて制約条件を満たす構成を網羅的に全て探索するアルゴリズムを開発しました。実際の配電網では、電気が行き渡るように放射状のネットワーク構成をとることや最大電流値・適正電圧値範囲などの幾何学的・電気的な制約条件が課せられるために問題が複雑になってしまい、このままでは効率的な探索は不可能です。そこで、条件を配電経路に関する（幾何学的）制約と、電力品質に関する（電気的）制約に分離し、前者には最新のグラフ探索アルゴリズムであるフロンティア法注４）を適用し、後者には電気回路の特性を計算するアルゴリズムを用いて、それぞれの結果をＺＤＤとしてコンパクトに出力しました。ＺＤＤは圧縮したまま操作（演算）できるため、両制約を満たすＺＤＤを効率的に求められます。このように、各アルゴリズムの特徴をうまく組合せることで、膨大な数の構成を圧縮しながら超高速で探索することを可能にしました。
（２）損失最小化手法への応用
次に（１）で得られた構成の中で、送電損失が最も小さい構成を抽出するアルゴリズムを開発しました。配電時に電線でジュール熱として失われる電力を「損失」と呼び、この損失を削減することは追加の設備投資なしに電力需給を改善し、化石燃料の節約につながります。そのため、損失削減効果は配電網構成の善し悪しを計る重要な指標となります。損失削減のためには、電線を流れる電流ができるだけ小さくなるような優れた配電構成を膨大な候補の中から選択する方法が効果的です。一般的な最適化手法は探索しながら制約条件を評価しますが、本研究チームが開発した手法は、まず（１）で制約条件を満たす構成を絞り込み、次のステップで送電損失が小さい構成を高速に探索する点に特徴があります。それでも条件を満たす構成は膨大ですが、ＺＤＤの構造を利用して共通部分ごとに損失を計算しながら絞り込みを行い、効率的に最適構成を探索します。
（３）ソフトウェアの開発
上記（１）、（２）を実装したソフトウェアを開発しました。このソフトウェアでは上記のアルゴリズムに加え、並列処理による高速化も行うことが可能です。
（４）標準解析モデルによる検証
（１）、（２）のアルゴリズムの有効性を検証しました。配電網として標準解析モデル注５）を用い、ランダムに選んだ１０％の地域に需要に見合う太陽光発電を導入しました。なお、電力需要は、夏のピーク時を想定しています。上記（３）のソフトウェアを用いて実際に計算したところ、制約条件を満たす構成の総数は、正確に「２１３６８２０１３８３４８５３２９１１６８２６１２２１４８０４９０５６０９８１７８３９２４４３８５２３５３９８１８９５２１５４０通り（約１０の６３乗）」であることを明らかにしました。この規模の配電網で構成数を正確に数え切れるのは世界初の結果です。市販の計算機を用いた計算時間は１時間１５分で、メモリ使用量は７７９ＭＢでした。構成数は膨大であるにも関わらず、効率的に探索を行い、高い圧縮率で表現できていると言えます。
さらに、２時間２０分の計算の結果、損失を最小にする構成を発見できました（図３）。今回のデータでは、一般的に用いられる標準的な構成に比べて、損失を約３％削減できました。これは全電力需要の約０．０２％に相当します。この数値を日本全国の６．６ｋＶ配電系に単純換算すると、９４９ＭＷから９２１ＭＷへ２７．９ＭＷの削減となり、追加の設備投資なしに構成変更のみによって一般家庭約１万軒分（火力発電一基の１／１０）相当の電力が削減されたことになります。二酸化炭素に換算すると、一時間あたり１５．５トンの削減です。
本研究は、ＪＳＴ 戦略的創造研究推進事業 ＥＲＡＴＯ「湊離散構造処理系プロジェクト」の離散構造処理基盤グループ（グループリーダー：湊 真一 北海道大学 大学院情報科学研究科 教授）、機械学習・制約充足応用グループ（グループリーダー：津田 宏治 産業技術総合研究所 生命情報工学研究センター 主任研究員）、および早稲田大学 先進グリッド技術研究所（所長：林 泰弘 教授）の協力により実施されました。さらに東京工業大学 大学院情報理工学研究科に所属する研究者とも連携して研究開発を進めました。
＜今後の展開＞
本研究では、配電網の制約条件を満たす全ての構成を探索するアルゴリズムを開発しました。また、損失最小化への応用によって、その有用性の一端を明らかにしました。この技術によって、追加の設備投資なしに送電損失を最小化し、化石燃料を節約することができます。また、ＺＤＤの索引構造としての特徴を利用すると、特定のスイッチ条件に合致する構成を高速に検索できるため、配電網の運用上の都合や故障対応などの追加的な制約が発生したとしても、柔軟に構成を絞り込むことが可能となります。本成果には、将来のスマートグリッドを支える基盤技術としての活用が期待されます。
今後は、電力系の技術者にとって扱いやすい実用的な設計・運用支援ツールとして提供できるように、本研究成果に基づいたソフトウェアの整備を進めていきます。さらには、本研究の発展的応用として、地震・津波に備えた避難所の配置問題や、道路網の設計・運用の問題など、社会的に重要なさまざまな問題にも取り組んで行く予定です。
＜発表課題名＞
発表課題（１）
| 課題名 | ：「フロンティア法の電力網構成制御への応用」 |
| 発表日 | ：平成２４年３月２０日（火・祝） |
| 会場 | ：電子情報通信学会 総合大会 ＥＲＡＴＯ「湊離散構造処理系プロジェクト」シンポジウム（岡山大学） |
発表課題（２）
| 課題名 | ：「ＺＤＤを用いた系統運用制約を満たす配電網構成の網羅的探索手法」 |
| 発表日 | ：平成２４年３月２３日（金） |
| 会場 | ：電気学会 全国大会（広島工業大学） |
＜参考図＞
図１ 電力網の概要
発電所で発電された電力は、送電網を経由して配電網へ送られます。配電網内は分散電源が存在するため電力の流れが複雑になります。
図２ 配電網のスイッチ構成の例
この例は、変電所から同色の家庭に正しく給電できる配電網構成（スイッチのＯＮ／ＯＦＦの組合せ）の１つを表しています。色のつかない（電気が届かない）家や、色の混ざった（異なる配電系統がつながれた）家が存在してはなりません。
図３ 標準解析モデルの最適構成
配電網の標準解析モデルは、４つの変電所を中心に、電線に接続された一般家庭や事業所（図では省略）に電力を供給します。電線には合計４６８のスイッチが備えられ、その構成（ＯＮ／ＯＦＦの組合せ）を変更して電力の流れを制御します。この図は、配電網全域に正しく給電でき、さらに電線で発生する送電損失を最小にする構成を表しています。
図４ ＺＤＤの例
図の３つのＺＤＤは、始点ａから終点Ｔへの経路を用いて、実線をたどる要素の組合せを表します。例えば、左のＺＤＤはａｃとｂｃという組合せを表します。本研究ではこの組合せを、スイッチａとｃを閉じた配電網構成と、スイッチｂとｃを閉じた構成に対応させています。さらにＺＤＤが備える演算アルゴリズムによって、左と中のＺＤＤから共通する組合せａｃを表す右のＺＤＤを得ています。このように、本研究では異なる制約を満たす構成を求めてから、ＺＤＤの演算によって両制約を満たす構成を得ています。
＜用語解説＞
- 注１） スマートグリッド
- 計算機や通信の技術を用いて電力網の状態を監視し、最適な状態を維持する制御を行う電力網のことです。例えば、需要予測に合わせて配電網の構成を自動制御することが期待されています。日本では、早稲田大学 先進グリッド技術研究所などを中心に研究が進められています。本研究で開発したアルゴリズムを適用することで、電力網で発生する送電損失をより大きく削減できる可能性があります。
- 注２） ゼロサプレス型二分決定グラフ（ＺＤＤ：Ｚｅｒｏ－ｓｕｐｐｒｅｓｓｅｄ ｂｉｎａｒｙ Ｄｅｃｉｓｉｏｎ Ｄｉａｇｒａｍ）
- 北海道大学の湊教授が考案したデータ構造とアルゴリズム体系で、膨大な数の組合せをコンパクトに圧縮し、圧縮したまま超高速に演算できます（図４）。配電網の構成は、閉じているスイッチの「組合せ」として表現できるため、ＺＤＤが適しています。また、ＺＤＤは一種の索引構造とみることもできるため、特定の条件に合致する構成を高速で検索することが可能です。スタンフォード大学のクヌース教授の名著『Ｔｈｅ Ａｒｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｐｒｏｇｒａｍｍｉｎｇ』にも掲載された注目度の高い技術です。
- 注３） 分散電源
- 一般家庭や事業所に設置される小規模な発電装置のことです。太陽光や風力などの自然エネルギーのほか、コジェネレーションのようにガスを用いた発電機もあります。これらの導入により、従来の電力消費者が同時に供給者にもなるため、配電網の電力の流れが複雑になり、高度な制御技術が求められます。分散電源を適切に制御することがスマートグリッドの重要な課題の１つです。
- 注４） フロンティア法
- 配電網のようなネットワーク構造から、条件を満たす部分的な構造を網羅的に探索し、ＺＤＤとして出力するアルゴリズムです。配電網では、幾何学的制約を満たす経路によって電力を供給しますが、可能な全ての経路を得るためにフロンティア法を利用しています。フロンティア法は配電網以外にも幅広い応用可能性を持っており、北海道大学の湊教授によって集中的に研究が進められています。
- 注５） 標準解析モデル
- 早稲田大学の林教授によって提唱された、日本の実際の配電網に基づく標準的な配電網モデルです（図３）。スイッチ数４６８、フィーダ数７２、総需要２８７ＭＷ、線路容量３００Ａ、送り出し電圧６．６ｋＶ、電圧許容範囲６．３－６．９ｋＶとなっています。
＜お問い合わせ先＞
＜探索アルゴリズムに関すること＞
井上 武（イノウエ タケル）
科学技術振興機構 ＥＲＡＴＯ「湊離散構造処理系プロジェクト」 研究員
〒060-0814 北海道札幌市北区北１４条西９丁目
北海道大学 大学院情報科学研究科 工学系Ｃ３０６
Tel：011-728-8270 Fax：011-728-8277
E-mail：
湊 真一（ミナト シンイチ）
北海道大学 大学院情報科学研究科 教授／科学技術振興機構 ＥＲＡＴＯ「湊離散構造処理系プロジェクト」 研究総括
〒060-0814 北海道札幌市北区北１４条西９丁目
Tel：011-728-8270 Fax：011-728-8277
E-mail：
＜電力網に関すること＞
林 泰弘（ハヤシ ヤスヒロ）
早稲田大学 先進理工学部 教授／同大学 先進グリッド技術研究所 所長
〒169-8555 東京都新宿区大久保３－４－１－６３－６－６Ｂ
Tel／Fax：03-5286-8122
E-mail：
＜ＪＳＴの事業に関すること＞
金子 博之（カネコ ヒロユキ）
科学技術振興機構 イノベーション推進本部 研究プロジェクト推進部
〒102-0076 東京都千代田区五番町７ Ｋ’ｓ五番町ビル
Tel：03-3512-3528 Fax：03-3222-2068
E-mail：
