デジタルアニーラによる配電応需計画の最適化

公開日 2021年7月15日
コンピューティング,データ福島 弘章, 前島 萌, 三輪 嶺花

富士通は,これまでデジタルアニーラの実用化に向けて取り組んできた。お客様業務へ適用するためには,実社会の問題で検証し,既存手法に対する優位性や技術課題を見極めることが重要である。

本稿では,電力会社の配電応需計画のスケジューリングを,組合せ最適化問題として解くアプローチの検討を行った。実データを用いた検証では,作業計画の最適化においてデジタルアニーラの有効性が示唆される結果が得られたので報告する。

1.まえがき

近年,量子コンピューターの実用化へ向けた取り組みが世界中で急速に進んでいる。中でも,組合せ最適化問題を解くことに特化したアニーリング方式は,実用化に向けた取り組みが始まっている。様々な企業が研究開発を進める中で,富士通はFUJITSU Quantum-Inspired Computing Digital Annealer(以下,デジタルアニーラ)を開発した[1]。デジタルアニーラとは,量子現象に着想を得たデジタル回路で,組合せ最適化問題を高速に説く新たな計算機アーキテクチャーである。量子コンピューターは,量子状態の維持が困難,接続と拡張に制約がある,といった問題があり,現状はまだ研究段階である[2]。

一方で,デジタルアニーラは,デジタル回路で動作するため安定動作し,小型化も容易である。また,全結合アーキテクチャーによって複雑な問題を簡単にマップ可能であり,実問題への適用が容易であるという特徴がある。

本稿では,中部電力株式会社 先端技術応用研究所様が検討している配電応需計画への量子アニーリング技術の適用について,デジタルアニーラを用いたスケジューリング最適化を試行した事例を紹介する。

2.組合せ最適化問題に対するデジタルアニーラの優位性

グラフ彩色問題などに代表されるいくつかの組合せ最適化問題について,既存アーキテクチャーに対するデジタルアニーラの優位性が示されている。グラフ彩色問題とは,辺でつながっている頂点同士が同じ色にならないように,全ての頂点を色分けする問題である。また,商用ソルバとは,組合せ最適化問題を解くためのアルゴリズムが搭載されたソフトウェアのことである。

グラフ彩色問題におけるデジタルアニーラの優位性を表-1に示す。頂点同士の辺でつながっている比率(辺密度)に関わらず,8~50 kbitの問題に対しては,商用ソルバでは規定計算時間内(最大10分)で解を出すことができていない。一方,デジタルアニーラでは100%解を出すことができている。また求解速度について,商用ソルバが唯一求解できた辺密度が50%以上・8 kbit未満の問題との比較で30倍の速度を出すことができている。

表-1 グラフ彩色問題における優位性

辺密度bit規模正答率
求解速度
商用ソルバDA
50%以上8~50 k0%100%
8 k未満33%100%30倍
50%未満8~50 k0%100%
8 k未満100%100%0.9倍

辺密度   :頂点同士の辺でつながっている比率
正答率   :規定計算時間内(最大10分)で解を得られた割合
求解速度  :商用ソルバを1としたときのDAの倍率
bit規模   :“頂点の数×色分けする色の種類数”の規模
データセット:以下のURLのランダム/疑似ランダムグラフ(DSJ/CUL)を10個使用
https://mat.tepper.cmu.edu/COLOR/instances.html
DA     :デジタルアニーラ

3.配電応需計画における有効性検証

中部電力パワーグリッド株式会社様(以下,中電PG)の配電部門では,顧客宅へ電気を届けるための電柱や電線などの建設,保守運用を行っている。日々の保守運用業務においては,各営業所の作業担当者(サービスエンジニア,以下SE)が担当エリアの顧客から電気の供給・停止・増設などの申し込みや,故障による停電情報が入ると,現地に出向して必要に応じた工事,点検,復旧作業を行っている。

このような作業計画(応需計画)においては,営業所の運営管理者が日々の作業と要員数を勘案してスケジュールを作成している。しかし,訪問順序やジョブの分担の組合せは必ずしも自明ではなく,スケジューリングの最適化が自動で実現できれば有用性が高い。また,作業中に発生する突発的案件(停電対応や感電などにつながる緊急を要する事象)が発生した場合,各現場での作業状況や各SEの位置情報から臨機応変にリスケジューリングを行う必要がある。

本対象問題においては,顧客宅などの巡回順序やSEの作業スキル,作業可能,移動時間などの制約を考慮に入れると,考えられる作業計画の組合せ数は膨大な数になる。このような組合せ最適化問題に対し,デジタルアニーラの有効性を検証することが今回の目的である。

3.1 最適化基準と制約条件

デジタルアニーラの検証にあたり,対象業務を分析し,以下の最適化基準(目的関数)を定義した。

  • 業務時間短縮
  • SE人数最適化
  • SE間の業務量の負荷平準化

本検証では,SE全体での「業務時間短縮」のみを対象とした。

また,最適化における制約条件を以下のように定義した。

  • 各作業は1度だけ実行される。
  • 各SEは作業の開始から完了まで他の作業を実行できない。
  • 各SEは移動中に他の作業を実行できない。
  • 実行可能時間が設定されている作業がある。
  • 最初の作業を出社と定義し,各作業者は所定時刻に業務を開始する。
  • 最後の作業を帰社と定義し,各作業者はどこかの時刻で帰社し,その後作業を実行できない。

図-1に応需計画の最適化のイメージを示す。応需計画のスケジューリングでは,全体として業務時間が長くならないように考慮する必要がある。例えば,作業員Aの作業A2と作業員Bの作業B2を入れ替えることで作業員Aの移動時間が短縮され,全体として業務時間を短縮できる。

図-1 応需計画の最適化による業務時間の短縮

図-1 応需計画の最適化による業務時間の短縮

3.2 評価検証結果

本検証では中電PGの営業所1箇所からご提供いただいた1日分の作業実績の一部(電子データで抽出できた作業40個)をテストデータとして用い,前節で述べた最適化基準および制約条件の下で作業計画の自動作成を試みた。

なお,実際の業務においては,付随的な条件として以下の点を考慮する必要がある。

  • SEは全員12時に事務所に戻り,13時まで休憩時間とする。
  • 時間帯によって,車での移動時間が変わる。
  • 突発的な作業が発生する場合がある。発生時はその時点から応需計画をリスケジューリングする。

本検証では,前述のテストデータを用いて,デジタルアニーラと既存の商用ソルバ(Gurobi Optimizer[3])による最適化結果の比較を行った。なお,Gurobi Optimizerを動作させているサーバーの諸元は,CPUはIntel® Xeon® CPU E5-2680 2.7 GHz×32コア,メモリーは200 GBであった。

以下の4パターンによる検証結果を表-2に示す。なお,パターン③では,午後の作業開始時に突発的な作業の割り込みを設定し,発生時点での計画のリスケジューリングを実行した。

  • ①SE数が4名
  • ②SE数が5名
  • ③SE数が5名で午後に突発的な作業が発生
  • ④SE数が6名

表-2 検証結果

パターン検証結果
業務完了時刻デジタルアニーラ
求解時間(秒)
Gurobi Optimizer
求解時間(秒)
① 作業担当者数:4人17:40857
(17:40の解得られず)
② 作業担当者数:5人17:0035120
③ 作業担当者数:5人+突発的な作業17:0035+16120+19
④ 作業担当者数:6人17:00512
※+の後の数値は,突発的な作業発生時の再計算に要した時間。

まず,求解時間(応需計画の計算に要する時間)に着目すると,いずれの検証パターンにおいてもデジタルアニーラが優位であるという結果が得られた。SE数4名のパターン①では,デジタルアニーラでは17:40に業務を完了できるという解が得られたのに対し,Gurobiでは時間をかけても有効な最適解が得られなかった。また,パターン③の突発的な作業発生時においても,デジタルアニーラはパターン②よりも1.5倍程度の時間増(35+16)で求解できており,Gurobiよりも高速に対応できた。このことから,業務途上のリスケジューリングの実現性が確認された。

次に,業務完了時間に着目すると,SE数5人以上の場合において17:00で全てのジョブが完了という結果が得られた。なお,実際の応需計画では今回テストデータに反映できなかった紙帳票のジョブがあり,人間系による作業実績(業務完了時間)を同一条件で計測できなかった。このため,人間系実績との直接的な比較はできないが,デジタルアニーラによる効率的なスケジューリングの実現性が確認された。

以上のことから,今回の応需計画の最適化検証において,デジタルアニーラの有効性が示唆される結果が得られた。

3.3 今後の課題と方向性

本検証では,一部実運用に即した改善が必要な点がある。具体的には,突発的な作業の発生時刻が固定されている,SEごとの作業スキルが一定である,SE間の業務量の負荷平準化が考慮されていない,といった点である。デジタルアニーラを応需計画の最適化に活用するためには,これらの点を加味したモデルを作成し,更に詳細な検証を行う必要がある。

今後は,本検証で得られた知見を活かして,より大規模なデータによる実用性評価を進めていく予定である。

4.むすび

本稿では,組合せ最適化問題を高速に解くことに特化した計算機アーキテクチャーであるデジタルアニーラを紹介し,電力の配電分野の応需計画への適用について検討した結果を述べた。

我々の社会には様々な分野に組合せ最適化問題が存在している。今後も,富士通はデジタルアニーラを活用して社会的な課題の解決を目指し,持続可能な世界へ貢献していきたい。


本稿に掲載されている会社名・製品名は,各社所有の商標もしくは登録商標を含みます。

著者紹介

福島 弘章(ふくしま ひろあき)富士通株式会社
ソフトウェアテクノロジー事業本部
デジタルアニーラサービスに従事。
前島 萌(まえじま めぐむ)富士通株式会社
ソフトウェアテクノロジー事業本部
デジタルアニーラサービスに従事。
三輪 嶺花(みわ れいか)富士通株式会社
社会システム事業本部
中部電力株式会社様および中部電力パワーグリッド様向けのシステム開発の担当営業として従事。

おすすめ記事

富士通テクニカルレビューに関するお問い合わせ・ご相談

  • Webでのお問い合わせ

    入力フォーム

    当社はセキュリティ保護の観点からSSL技術を使用しております。

  • お電話でのお問い合わせ

    0120-933-200
    (通話無料)

    富士通コンタクトライン(総合窓口)
    受付時間 9時~17時30分(土曜・日曜・祝日・当社指定の休業日を除く)

ページの先頭へ