量子コンピュータにより大規模信号機群を制御する最適化技術の開発に成功

1. 発表者:

井上 大輔(株式会社豊田中央研究所)
岡田 明久(株式会社豊田中央研究所)
松森 唯益(株式会社豊田中央研究所)
合原 一幸(東京大学 特別教授/連携研究機構 次世代知能科学研究センター 特任教授/国際高等研究所ニューロインテリジェンス国際研究機構(WPI-IRCN)副機構長)
吉田 広顕(株式会社豊田中央研究所)

2. 発表のポイント:

◆大都市の信号機群の制御を、量子コンピュータの一種である量子アニーリングマシンを用いて全体として最適化する技術を開発した。
◆D-Wave 社の量子アニーリングマシンを用いたモデル都市に対する数値実験により、交通状態(車両の流れやすさ)が従来制御手法に比べ約 10%向上することを示した。
◆今後量子コンピュータ開発の進展が見込まれることから、実際の都市の信号機群を都市全体の交通状態に応じて高速かつ効率的に制御するため基盤技術として期待される。

3.発表概要:

大都市の渋滞を緩和するために、交通状態に応じて適応的に信号機を制御することは重要な課題です。従来の適応的な信号機の制御は、各交差点の周辺の局所情報のみを考慮したもので、都市全体の交通状況を同時に最適化する手法ではありませんでした。そこで、株式会社豊田中央研究所数理工学研究領域の井上大輔、岡田明久、松森唯益、吉田広顕各研究員と東京大学ニューロインテリジェンス国際研究機構の合原一幸特別教授は、次世代計算機として期待されている量子コンピュータの一種である量子アニーリングマシンを用いて、大都市の信号機群を協調制御する手法を開発しました。

本研究の一部は、豊田中央研究所と東京大学・次世代知能科学研究センターとの社会連携研究部門『モビリティ社会知能デザイン』の助成を受け実施されました。

4.発表内容:

背 景
都市全体の状況に応じて一斉に最適化する大域的な制御問題は、大規模な組合せ最適化問題に帰着されるため、最適解の探索が困難であることが知られています。一方で近年、特定の組合せ最適化問題を扱う専用マシンの開発がさかんで、特にイジングモデル(注1) と呼ばれる形式で表されるものが多く見られます。なかでも、量子アニーリングマシン(注2)は、量子ゆらぎと言われる自然現象を利用して、最適化問題の解の候補を同時探索することができるため、高速な求解をもたらすと期待されています。量子アニーリングマシンは、量子現象を利用するため量子コンピュータの一種とされており、D-Wave 社が商品化していますが、大規模で複雑な実問題に適用するためには、近似や変数変換などの工夫が必要です。

内 容
都市全体の交通状況を考慮した信号機群の最適化問題を、量子アニーリングマシンを用いて求解する手法を開発しました。ここでは、道路網は縦横に直交する格子状であるとし、道路網上の交通は一定の確率で右左折する車両群によりモデル化しました(図1)。問題を定式化して解析した結果、交通流の偏りを最小化する信号の色の組合せを決める最適化問題が、イジングモデルのエネルギー最小化問題に帰着されることが示されました。これにより、量子アニーリングマシンにより信号制御問題を解くことが可能になりました。

効 果
50×50 の道路からなる都市の信号機を一斉に制御する数値実験を行い、交通流の偏りの大きさを表す評価関数の値を従来手法と比較しました。その結果、量子アニーリングマシンを用いた提案手法が、よく知られた従来制御手法に比べて評価関数の値を約 10%小さくできることがわかりました(図2)。提案手法のエネルギー最小化問題は、焼きなまし法な どのヒューリスティックな最適化手法を用いても求解できますが、量子アニーリングマシンを用いると焼きなまし法を用いた場合に比べ高速かつ高性能であることもわかりました。
本手法は、量子アニーリングマシンに限らず、他の組合せ最適化問題の専用マシンを用いても実施可能であり、将来の交通流制御の基盤技術のひとつになると期待できます。

5.発表雑誌:

雑誌名:Scientific Reports
論文タイトル:Traffic Signal Optimization on a Square Lattice with Quantum Annealing
著者:Daisuke Inoue, Akihisa Okada, Tadayoshi Matsumori, Kazuyuki Aihara, Hiroaki Yoshida
DOI番号:10.1038/s41598-021-82740-0

6.問い合わせ先:

株式会社豊田中央研究所 数理工学研究領域
研究員 井上 大輔
研究員 吉田 広顕

東京大学 特別教授/名誉教授
東京大学国際高等研究所ニューロインテリジェンス国際研究機構(WPI-IRCN)
副機構長 合原 一幸(あいはら かずゆき)

株式会社豊田中央研究所
総合企画・推進部 広報室

東京大学 大学院情報理工学系研究科
広報室 森松

7.用語解説:

(注1) イジングモデル
統計力学において、強磁性体のスピンの振る舞いを記述するモデル。単純なモデルであるが相転移現象を記述可能であり、多くの物理学者によって研究されてきた。

(注2) 量子アニーリングマシン
1990 年代に西森・門脇らによって考案された、量子力学を使用した組合せ最適化向けのアルゴリズムである“量子アニーリングアルゴリズム”を、超伝導体を用いたハードウェアで実装した専用機械。

8.添付資料:


図1:提案する交通流制御手法の概念図。交通流の偏りを最小化するように各交差点の信号機の状態を決める最適化問題を、各時刻で量子アニーリングマシンにより求解する。これにより、大規模な最適化問題を解くことができる。


図2:交通流の偏りの大きさを表す評価関数の値(小さい=スムーズな交通流)を、走行車両の直進率をさまざまに変更して計算した図。