11－4

実験数理研究分野

実験数理研究分野
山岡雅直（2016 年 6 月〜現在）（日立製作所研究開発グループ基礎研究センタ）
客員教授

竹本享史 (2019 年～現在)（日立製作所研究開発グループ基礎研究センタ）
客員教授

湊真一

（京都大学大学院情報科学研究科）
民間等共同研究員

Norman Meting(日立製作所研究開発グループ基礎研究センタ、〜2020.8.31、日立ヨーロッパ LTD.へ)

１．研究目標2016年に日立製作所が北海道大学キャンパス内に開設した日立北大ラボでは、北海道における少子高齢化や人口減少などの社会課題を解決し、地域創生につながる共同研
究を自治体と連携した実証実験や探索的活動を通じて進めている。新型コロナウィルス感染拡大によって、テレワークによる在宅勤務が普及するなど、働く場所が住む場所に依存しなくなることから、豊かな自然環境を持つ地域での生活が見直されている。今後、都市から地域への移住による分散化が進むことが予想され、地域におけるエネルギー需要の増加に対応する安定した供給力の確保と、安心・安全な生活基盤の構築が重要となる。
豊かな自然と広大な大地を持つ北海道は、様々な自然エネルギーに恵まれ、太陽光、陸上風力の将来に向けた導入ポテンシャルは、それぞれ、全国３位、１位となっている。
また、全国の約4分の１の耕地面積を活かした農業など、１次産業が盛んな北海道は、国内の食料自給率向上に大きく貢献すると共に、道内には多数の未利用・廃棄物資源が賦存している。これに対して、北海道は寒冷・広大であるため、暖房、移動にエネルギーを多く利用しており、一人当たりのCO2排出量は全国より多くなっていることから、今後の持続的な発展のためには、これらの再生可能エネルギーの活用が不可欠となる。
しかしながら、太陽光発電や風力発電は供給量の変動が大きく、北海道全体で火力発電も含めた調整を行いながら使うため、安定・安価な供給量確保の観点から利用範囲が限定されてきた。さらに、需要地・再エネ適地が分散している北海道では、送電線の容量を増加するためには多額の費用と工期が必要とされている。このため、新たな再生可能エネルギーの系統への接続が難しく、再生可能エネルギーを十分に活用するには、長距離の送配電網に頼らないエネルギーシステムの構築が必要となる。
既存配電網(AC)

遠隔地

加⼯場
エネルギー
価値循環
畑
温泉
災害時 DC/AC
避難所

直流⼩型グリッド
農薬

地域データ
発電量
気象データ
⽣産計画
新サービス
域内交通
防災
農作業⽀援

最適制御
数理システム
多⽬的最適化

時空間最適化✔ ロバスト✔ 順応性✔ 将来予測

図１：分散型直流小型グリッドから成る地産地消地域エネ
ルギーシステム。直流小型グリッドを EV 等でネットワー
ク化、地域産業、防災に寄与する共に域内コミュータ等の新たな価値を創出

本システムを実現するには、気象変動、需要変動等の不確実な環境変化を考慮し、環境問題や経済効果等の様々な価値に対して最良な解を提供する次世代最適化技術（多目的時空間最適化技術）の開発が重要となる。従来の最適化
ソルバーは、周囲環境の時間軸上の変化も考慮した最適化問題を解くことは困難であり、コスト関数を予測する技術や、環境変化に対して順応性とロバスト性を有するアルゴリズムを新たに開発する必要がある。日立北大ラボは北海道大学と共に、情報科学・数学理論・ハードウェアアーキテクチャといった多岐に渡る産学連携の研究基盤を構築し、異分野連携の強みを生かして、社会課題解決に寄与する次世代最適化技術の構築をめざす。

２．研究成果図２に示すように、気象の変化、災害など、ある時刻を境に状況が急激もしくは大きく変化する問題については、状態空間が膨大となり、また、最適になりそうな部分空間を探索することが困難となるため、強化学習等の既存手法では良い近似解を見つけることができず、新たなアルゴリズム開発（時空間最適化技術）が必要となる。このため、地域の買物支援サービスを例に時空間最適化技術を具体的な最適化問題として数学的に定義した。さらに、課題共有を通じた人的ネットワークの拡大とオープンイノベーションによる研究加速を目的に、産学連携マラソン型プログラミングコンテストを企画・開催した。コンテストの参加登録者数は千名を超え、時空間最適化技術構築に向けた新たな知見を得た。

⼤
状態空間の規模

客員教授

このような背景の下、図1に示すように、日立北大ラボと北海道大学は地産地消地域エネルギーシステムの研究開発を推進している。本システムでは、再生可能エネルギーを活用した直流小型グリッドを地域に複数設けて、グリッド間を電気自動車（ＥＶ）等でネットワーク化することで、需給一体型可動式グリッドを実現する。本システム構築により、電力の地域間格差解消と災害による大規模停電発生の際も利用できる自立型の電力システムの提供に加えて、地域にとって必要不可欠なヒト・モノのコミュータ等、単独の小型グリッドでは創出できない新しいサービスの提供をめざす。さらに、各小型グリッドは小規模な構成のため、導入コストが低く、既存の電力網と親和性が高いシステム技術を構築することで、本エネルギーシステムの様々な地域への展開が期待できる。

⼩アルゴリズム少ない
⼤規模計算困難
CMOS
アニーリング
マシン

メタ
ヒューリス
ティック

厳密解法
ソルバ

強化
学習

⼩・遅

【本開発】
時空間最適化
アルゴリズム⼤・早環境時間変化

図２：時空間最適化アルゴリズムの位置付け。ある時刻を境に状況が急激もしくは大きく変化する動的最適化問題。
将来に対するコスト関数の予測技術、状況変化に対してロバスト・順応性を有するアルゴリズムの開発が必要プログラミングコンテストでは、買物支援サービスにおける配送待ち時間最適化をテーマに出題した。店舗・顧客の位置とそれらを結ぶ道を辺とした平面グラフで表現し、グラフの頂点のうち1つは店舗で他は商品を注文をする顧客とした。顧客から注文された商品を、店舗で1台の車に積み、各顧客の待ち時間を可能な限り、小さくなるように配送する。ここで、配送中に渋滞、注文キャンセル、車の故障、信号待ちの4つの環境変化を確率的に発生させることで、時空間最適化アルゴリズムの技術構築を図った。
本コンテストを通じて開発した時空間最適化アルゴリ
ズムを図３(a)に示す。本アルゴリズムは、配送経路を事前に分割し、分割した各径路に対し、(i)(ii)の最適化を行うことで配送の効率化を実現する。
(i) 注文状況や信号待ちに応じた巡回前の経路最適化(ii) 注文キャンセル、車の故障、及び渋滞に対するオンライン最適化
経路分割では、配送経路を店舗から店舗までの4つの閉路（Route A～D）に分割し、4つの閉路を巡回することで、全ての顧客を訪問することになる。本分割処理により、顧客の配送待ち時間を全顧客の巡回時間の5/4倍以下（分割しない場合は2倍以下）に抑えることができ、平均的な顧客の待ち時間の短縮が期待できる。また、注文キャンセル等の環境変動については、キャンセルした顧客(頂点)をスキップして経路を再構築し、さらに、再構築後の経路長の増分に応じて、寄り道して顧客に商品を届ける(オンライン最適化)ことで対応した。開発アルゴリズムの性能評価を実施した結果、従来技術(LKH：巡回セールスマン問題に有効な近似解法)に対して、顧客の平均待ち時間を30％以下に低減できることを確認した。
(a)

(b)

経路最適分割的時空間最適化技術の構築をめざす。
また、地域における環境(低炭素化社会)と経済の両立をめざして、北海道岩見沢市において、マルチ燃料エンジンや太陽光パネルから成る、小型グリッドを構築中である。
マルチ燃料エンジンは従来のバイオエタノール系の発電機と異なり、低濃度(10%以上)エタノールでも発電でき、地域における様々な廃棄農作物や未利用の温泉付随ガス(メタンガス)を燃料として活用できる。また、得られるエネルギー(電気・熱)を、電力源、農作物の加工・乾燥等への活用でき、地域経済を活性化することができる。本実証実験
を通じて、燃料のコスト、電力量、発生熱量を確認することで、地域産業への応用を検証する。また、地域内の様々な利用シーンについて、エネルギー価値を数理・情報科学技術により定量化し、これを活用した循環取引モデル構築をめざす。さらに、エネルギー価値の定量化のために、ブロックチェーン技術（トークン等）を実証、検証する。合わせて、地域コミュータ、物流、サービス等と連携することで、地域の循環型経済モデルを開発、検証する。

４．資料
4.1

学術論文（査読あり）

1)

Y. Sugie, Y. Yoshida, N. Mertig, T. Takemoto,
H.Teramoto, A. Nakamura, I. Takigawa, S. Minato,
M. Yamaoka, and T. Komatsuzaki: "Minor-embedding
heuristics for large-scale annealing processors
with sparse hardware graphs of up to 102, 400
nodes," Soft Computing, Accepted (2020). 【電子研内共著】

2)

K. Yamamoto, K. Kawamura, K. Ando, N. Mertig, T.
Takemoto, M. Yamaoka, H. Teramoto, A. Sakai, S.
Takamaeda-Yamazaki, and M. Motomura: "STATICA:
A 512-Spin 0.25M-Weight Annealing Processor Withan All-Spin-Updates-at-Once Architecture for
Combinatorial Optimization With Complete Spin–Spin Interactions," IEEE Journal of Solid-State
Circuits, Vol. 56, No. 1, pp. 165-178, Jan. 2021.
【電子研内共著】

3)

T. Takemoto, M. Hayashi, C. Yoshimura, and M.
Yamaoka: "A 2 × 30k-Spin Multi-Chip Scalable
CMOS Annealing Processor Based on a Processingin-Memory Approach for Solving Large-Scale Combinatorial Optimization Problems," IEEE Journalof Solid-State Circuits, Vol. 55, No. 1, pp.
145-156, Jan. 2020.

分割

オンライン最適化
最初の配送計画 注⽂キャンセル(B)

注⽂発⽣(D)

顧客の平均待ち時間

従来アルゴリズム(LKH)

提案⽅式

LKH: Lin-Kernighan-Helsgaun

頂点数

図３：買物支援サービスをテーマに開発した(a)時空間最適化アルゴリズムの概要と(b)顧客の待ち時間に関する従来アルゴリズムとの性能比較結果

３．今後の研究の展望
地域エネルギーシステム実現に向けて、互いにトレードオフの関係にある複数の目的関数が存在し、時間的な環境変化を含む最適化問題(多目的時空間最適化)に対して、最良解を求めるアルゴリズム開発が必要となる。そこで、2020年度に、地域に点在する小型グリッド(発電、蓄電、消費が行われるにおける電力が不足しないよう、複数台のEV(を用いて蓄電量のバランスを保ちつつ、人やモノをある地点から別の地点まで効率よく運搬することをテーマとした、マラソン型プログラミングコンテストを開催(日立北大ラボ×北大コンテスト2020「未来の自律分散型まちづくり」)した。ここで、各小型グリッドでは太陽光や小型燃料エンジンによる発電、電力の消費およびEVとの充放電が行われており、それらにより時間変動する電力需給を考慮しながら、電力と運搬のバランスを調整する必要がある。
本コンテストの参加登録者は1,600名を超え、当初想定した以上の性能の解答が集まり、非常にレベルが高いコンテストとなった。今後、コンテストの成績優秀者とも連携しながら、解答コードの実応用に向けた解析を実施し、多目

4.2

学術論文（査読なし）

該当なし
4.3

総説・解説・評論等

該当なし
4.4 著書

該当なし
4.5 講演a.

招待講演（国際学会）
該当なし

b.

招待講演（国内学会）d.

一般講演（国内学会）

該当なし
c.

一般講演（国際学会）

1)

T. Takemoto, K. Yamamoto, C. Yoshimura, M.
Hayashi, M. Tada, H. Saito, M. Mashimo, M.
Yamaoka: "A 144Kb Annealing System Composed of
9×16Kb Annealing Processor Chips with Scalable
Chip-to-Chip Connections for Large-Scale Combinatorial Optimization Problems," IEEE International Solid-State Circuits Conference (ISSCC),Online, Feb. 2021.

2)

3)

4)

5)

6)

7)

H. Uchigaito, T. Shirai, Y. Iwata, N. Mertig, Y.
Sugie, T. Oizumi, H. Teramoto, A. Nakamura,Shin-ichi Minato, T. Komatsuzaki, and T. Takemoto: "Minimizing customer waiting time with a
new delivery-tour planning algorithm based ontour division and dynamic route optimization,"International Symposium on Nonlinear Theory andIts Applications (NOLTA), Online, Nov., 2020.
【電子研内共著】
K. Yamamoto, K. Ando, N. Mertig, T. Takemoto, M.
Yamaoka, H. Teramoto, A. Sakai, S. TakamaedaYamazaki, and M. Motomura: "STATICA: A 512-Spin
0.25M-Weight Full-Digital Annealing Processor
with a Near-Memory All-Spin-Updates-at-Once Architecture for Combinatorial Optimization with
Complete Spin-Spin Interactions," IEEE International Solid-State Circuits Conference (ISSCC),San Francisco, USA, Feb. 2020. 【電子研内共著】
Y. Sugie, N. Mertig, Y. Iwata, H. Teramoto, A.
Nakamura, I. Takigawa, Shin-ichi Minato, T. Komatsuzaki, and T. Takemoto: "Compiling higherorder binary optimization problems into annealing processors," Proc. of 25th International
Symposium on Artificial Life and Robotics (AROB25th), Beppu, Jan., 2020. 【電子研内共著】
T. Takemoto, M. Hayashi, C. Yoshimura, and M.
Yamaoka: "A 2´30k-Spin Multichip Scalable Annealing Processor Based on a Processing-inMemory Approach for Solving Large-Scale Combinatorial Optimization Problems," IEEE International Solid-State Circuits Conference (ISSCC),San Francisco, USA, Feb. 2019.
T. Takemoto, N. Mertig, M. Hayashi, S. SusaTanaka, H. Teramoto, A. Nakamura, I. Takigawa,S. Minato, T. Komatsuzaki, and M. Yamaoka:"FPGA-Based QBoost with Large-Scale Annealing
Processor
andAccelerated
Hyperparameter
Search," In Proc. of IEEE CAS 2018 International
Conference on Reconfigurable Computing and FPGAs(ReConFig), Dec. 2018. 【電子研内共著】
Y. Sugie, Y. Yoshida, N. Mertig, T. Takemoto, H.
Teramoto, A. Nakamura, I. Takigawa, S. Minato,M. Yamaoka, and T. Komatsuzaki: "Graph Minorsfrom Simulated Annealing for Annealing Machineswith Sparse Connectivity," In Proc. of 7th International Conference on the Theory and Practice of Natural Computing (TPNC), (LNCS 11324,Springer), pp. 111-123, Dec. 2018.

該当なし
e.

研究会・シンポジウム・ワークショップなど（学会以外）

1)

北大・日立新概念コンピューティングコンテスト2018(2019/2)

2)

日立北大ラボ×北大「社会創造数学コンテスト2020」(2019/11-12)

3)2020 北 海 道 大 学 × 日 立 北 大 ラ ボ フ ォ ー ラ ム「Society5.0 北海道の地方創生と未来」

4)

日立北大ラボ×北海道大学コンテスト2020「未来の自律分散型まちづくり」(2020/12-2021/1)

4.6

シンポジウムの開催

該当なし
4.7

共同研究

a.

所内共同研究
該当なし

b.

民間等との共同研究

1)

株式会社 日立製作所との新概念コンピューティン
グに関する共同研究。

a.

委託研究該当なし

b.

国際共同研究
該当なし

4.8

予算獲得状況（研究代表者、分類、研究課題、期間）a.

科学研究費補助金
該当なしb.

大型プロジェクト・受託研究
該当なし

4.9

受賞

該当なし
4.10

アウトリーチ活動該当なし