科学技術振興機構（JST）、北海道大学、早稲田大学は2012年2月23日、北海道大学大学院情報科学研究科の湊真一教授らのグループが、電力の配電網における送電ロスを最小化する技術を開発したと発表した。湊教授が考案した「ゼロサプレス型二分決定グラフ（ZDD）」というアルゴリズムを、配電網の最適化計算に適用した。モデル上の検証では、配電網における電力ロスを3％削減できたとしている。

　湊教授が1993年に考案したZDDは、米スタンフォード大学のドナルド・クヌース名誉教授の著書「The Art of Computer Programming」において、日本人が考案したアルゴリズムとしては初めて、独立項目として解説されたことで知られている。これまでZDDは、LSI設計において、回路の構成を最適化する計算などに使われていた。そのZDDを配電網の経路最適化に用いたのが、今回の発表のポイントである。

　電力の配電網は、数多くの変電所とスイッチからなる非常に分岐の多いネットワークである。例えば、30万人程度に電力を供給する標準的な配電網を模した仮想的な配電網では、変電所設備が72カ所、スイッチが468個存在する。配電網における経路の組み合わせの総数は「2の468乗（10の140乗）」にも達する。組み合わせの数があまりに多すぎるため、これまでの最適構成探索技術では、すべての組み合わせを調査することができなかった。つまり従来の配電網最適化は、厳密な計算に基づいて行われていなかった。

　湊教授が考案したZDDは、組み合わせの集合を圧縮して表現するデータ構造とアルゴリズムからなる技術である。ZDDを使うと、組み合わせが多すぎて計算できないようなグラフ構造のデータを圧縮し、さらに圧縮したまま超高速で計算できるようになる。ZDDを適用することで、配電網における完全な経路最適化が、現実的な時間で計算できるようになった。

　配電網の経路最適化では、「異なる変電所系統をつないではいけない」といった配電経路に関する幾何学的な制約と、「電線の各区間で許容電流を超えてはいけない」といった電力品質に関する制約の二つを考慮した上で、電力ロスを最小化する経路計算を行う必要がある。湊教授らが開発した技術ではまず、幾何学的な制約と電力上の制約を満たす経路の組み合わせを、ZDDを用いてすべて探し出した。探索にかかった時間は、標準的なパソコン上で1時間15分。組み合わせの総数は10の63乗個で、30万人規模の配電網における実現可能な経路の組み合わせを正確にすべて数えたのは、世界初の結果だという。

　さらに湊教授らは、10の63乗個の組み合わせの中から、電力需要シナリオに沿って、電力ロスを最小化する経路の組み合わせを見つけ出すアルゴリズムを開発。2時間20分の計算時間で、電力ロスが最小になる経路の組み合わせを見つけ出すことに成功した。

　JSTは今後、ZDDを適用した配電網の最適化を実現するために、電力会社などの技術者が扱いやすい実用的な設計・運営支援ツールの開発を目指す。