渋滞解消のための信号制御最適化
概要
易しく学ぶ最適化フローでは、説明しやすい問題を取り上げて、アニーリングマシンで組合せ最適化処理を行う場合の要件定義、定式化、入力データ作成、実行と、工程ごとに紐解いて解説してきました。CMOSアニーリングマシンを用いた組合せ最適化システムの開発フローを、課題定義から実装までの一連の流れを通して体験することにより学びを一歩先に進めてみましょう。
本記事では、渋滞解消のための信号制御を組合せ最適化問題としてCMOSアニーリングマシンによる処理を行い、信号制御システムとして実現する演習を行います。
現状においては信号機は組合せ最適化問題として処理されて制御されているわけではありませんが、渋滞による経済的損失は膨大な金額にのぼると言われており、社会課題の一つといえます。渋滞を解消することで経済的損失の抑制およびエネルギー削減にも効果が期待されます。
このページのコンテンツは、豊田中央研究所と東京大学による論文[1]およびそれをもとにした株式会社Jijのブログ記事[2]をもとに、CMOSアニーリングマシン向けの演習として「易しく学ぶ最適化フロー」で学んだ内容を実践できるように再構成したものです。CMOSアニーリングで実行する前段階の、上記の論文やブログで定義している要件定義、制約設定、定式化等の解説に「易しく学ぶ最適化フロー」で解説した知識を追加し、復習と応用を兼ねて学習いただけることをめざしています。
参考文献
- [1]豊田中央研究所, 東京大学, “Traffic Signal Optimization on a Square Lattice with Quantum Annealing”
https://arxiv.org/abs/2003.07527 - [2]同論文を詳しく解説した株式会社Jijのブログ
D-Waveを用いた正方格子状の交差点群における信号制御最適化
要件定義
目的
現実的な課題である「渋滞解消」のために、どのような最適化問題が成立するでしょうか。ここで取り上げる最適化問題の目的は、車を極力スムーズに流すことで渋滞を減らすことです。言い換えると、実現したいのは各交差点で待機している垂直方向や水平方向の車の台数を信号制御によって均一化することです。この問題に対し、要件定義、つまり、やりたいことをコンピュータに伝えるための言語化を行っていきましょう。
道路と信号の定義
- 道路は格子として与えられる。
- すべての交差点は上下左右4つの交差点と隣接している。
- 垂直方向と水平方向に信号が設置されている。
車の動きの定義
- 車は交差点で直進、左折、右折のいずれかをとる。
- 交差点で車が直進する割合を$a$とする。
- 車が左右に曲がる割合は同じと考え、それぞれ$(1-a)/2$と表す。
定式化には時間的変化を考慮する
この問題の難しさとして、ある交差点で車の台数の偏りを解消しようとすると、隣の交差点の台数に良い影響がある場合と、悪い影響がある場合とがあり、時間的な変化と共に最適化の条件が変わりゆくということが挙げられます。この複雑な前提をどうモデル化するのでしょうか。
まずは、ひとつひとつの交差点について「状態をよくする」ための定義を行います。ひとつひとつの交差点の状態をよくするということは、ある信号を青にし、その交わる方向の信号を赤にするという変化を起こすことです。
しかし、交差点1か所を操作しただけで、エリア全体の渋滞が解消する方向に向かうかどうかは運に任せる、というわけにはいきません。もし水平方向の信号を青にしてそのまま放置していれば、当然垂直方向の車は滞ります。そこで、次に、時間的変化を考慮して、"交差点$i$と交差点$j$の関係"および、"時刻 ($t$) と時刻 ($t+1$) の関係"を定義しなければなりません。
定式化
次に信号制御をイジングモデルとして定式化を行っていきましょう。このとき、前の節で説明した「時間的変化の考慮」を入れて時間方向の変化を取り入れるようにします。
信号にイジング変数を割り当てる
まず１つ１つの交差点について「状態をよくする」ための最も小さな要素である信号制御に、イジング変数の$+1$と$-1$を割り当てます。
- 交差点$i$において垂直方向の車両が水平方向の車両より多い場合は、垂直方向の信号を青に割りあてたい。つまり$\sigma_i=+1$
- 交差点$i$において水平方向の車両が垂直方向の車両より多い場合は、水平方向の信号を青に割りあてたい。つまり$\sigma_i=-1$
青にする信号の方向（垂直もしくは水平）をイジング変数として設定することができました。
次に、渋滞解消という最適化の最終的な目標のため、時間の流れとその都度の状態を与えることに配慮してモデル化を検討します。
車の量をモデル化する
最適化したい対象すなわち信号の状態は、次の時刻における車の量から与えられます。次の時刻における車の量は、その直前の時刻$t$における信号の割り当て$\sigma$と、車の進行方向の割合$a$を使って表すことができます。
車の量$q_{ij}, x_i$
車の量は$q_{ij}$と$x_i$の2種類の変数を定義します。$q_{ij}$は交差点$j$から交差点$i$へと移動していく車の量を表す変数としています。一方$x_i$はある交差点で待つ車の量を表す変数です。まず$q_{ij}$の定義を詳しく見ていきましょう。
- 時刻$t$における交差点$j$から交差点$i$をつなぐ道にある車の量を$q_{ij}(t)(≠q_{ji})$とする
- 時刻$t$における交差点$i$と$j$の信号機のパラメータをそれぞれ$\sigma_i(t)、\sigma_j(t)$とする
- すると時刻$t+1$での道路$j$→$i$の車の量は
$$\tag*{式(1)} q_{ij} (t+1) = q_{ij} + \frac{s_{ij}}{2} ( - \sigma_i (t) + \alpha \sigma_j (t))$$
ここで、$s_{ij}$は道路の方向パラメータで、道路$j→i$が垂直方向なら$s_{ij}=+1$、道路$j→i$が水平方向なら$s_{ij}=-1$です。
$q_{ij}$は前の時刻の車の量、$-s_{ij}\sigma_{i}(t)/2$は出ていく車の量、$s_{ij} \alpha_{\sigma_j}(t)/2$は入ってくる車の量を表します。つまり、式(1)は、時刻($t+1$)の車の量は、前の時刻の車の量に、入ってきた車の量と出ていく車の量を足したものを表しています。なお、式を簡単にするため$\alpha=2a-1$を用いて置き換えています。
次に、変数$x_i$についてどのように定義されているのかを見ていきましょう。
- 交差点$i$で待つ車の量の平均値$x_i$を$q_{ij}$で表すと
$$\tag*{式(2)} x_{i} (t) = \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} (t)$$
つまり、式(2)は、交差点$j$から交差点$i$へ向かい交差点$i$で待つ車の量を表しています。
式(2)を構成する$s_{ij}$は道路の方向パラメータ、$q_{ij}$は交差点$j$から交差点$i$へ入る車の量でした。つまり垂直方向が赤で車が待っている場合と、水平方向が赤で車が待っている場合とを足し合わせています。
交差点$i$に隣接した四方向で、$\sigma_i=+1$のときと$\sigma_i=-1$の時にそれぞれどこから車が入ってくるか、どこへ出ていくか、をイメージしてみましょう。交差点$i$に対して交差点$j$は4つ考えられます。それぞれからの車の量を考慮するため$\sum$の式になっています。
交差点$i$の垂直方向で待っている車は、北方向からくる車と南方向からくる車があります。また水平方向で待っている車は東方向からくる車と西方向からくる車があります。
垂直方向と水平方向で待っている車の量が偏っていなければ$x_i(t)=0$に近づいていきます。
- 式(1),(2)より時刻$t+1$における交差点$i$に接する道路の車量$x_i(t+1)$は
$$ \begin{align*} \tag*{式(3)} x_{i} (t+1) &= \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} (t+1) \\ &= \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} + \frac{1}{2} ( - \sigma_i (t) + \alpha \sigma_j (t) ) \\ &= x_i (t) + \frac{1}{4} \sum_{j \in N(i)} ( - \sigma_i (t) + \alpha \sigma_j (t) ) \end{align*} $$
これである交差点での信号機の色と、車の量についての関係を式で表すことができました。
コスト関数
車の量と信号の色の関係をモデリングすることができました。あとは、CMOSアニーリングマシンで最適化するための作業を進めていきましょう。立てた関係式について、目的達成のために「良くする」のはどういう操作なのかを考慮すると、以下のように評価することができます。
- $x_i(t+1) > 0$の時は垂直方向の車量が多いので垂直方向の信号を青にする
- $x_i(t+1) < 0$の時は水平方向の車量が多いので水平方向の信号を青にする
これをすべての交差点に対して行列形式で書き直すと以下式になります。
$$\tag*{式(4)} \boldsymbol{x}(t+1) = \boldsymbol{x} (t) + (- \boldsymbol{I} + \frac{\alpha}{4} \boldsymbol{A} ) \boldsymbol{\sigma} (t)$$
この最適化はある交差点において水平方向と垂直方向に待っている車を均等にすることです。
すなわち$\boldsymbol{x}(t+1)$を$0$に近づけるような信号の割り当て$\boldsymbol{\sigma}(t)$を決定する問題といえます。これを二乗の形にすることで$0$が最小値となります。よって目的関数は以下のように設定できます。
$$\tag*{式(5)} H= \boldsymbol{x}(t+1) ^T \boldsymbol{x}(t+1)$$
これが行列表現の2乗の書き方です。$^T$という記号は転置と呼ばれ、行列の行と列を入れ替えるという意味があります。$\boldsymbol{x}_i(t+1)$のベクトルを2乗するために、転置にする$\boldsymbol{x}(t+1)$を行方向の成分にし、そこに列方向の$\boldsymbol{x}(t+1)$を掛け合わせる操作を示しています。参考リンク[4]にわかりやすく記載されています。
繰り返しのある計算を表現しやすくする「行列」の活用
(3)の関係式を行列形式で書き直すと(4)になるということについて説明します。行列とは、” 「同様の性質を持つ数や数式を、行列という形で一つにまとめて記述することで、 計算を簡単に行う事ができる」”[4]というものです。
式(3)ではある交差点$i$のある時刻$t+1$とその前の時刻tにおける、その交差点とその隣4方向の交差点（信号の色および車の量）の関係を立てることができましたが、エリア全体の交差点で車の量を均一にするという目的を表現できていません。さらに、最適解において最もエネルギーが小さくなるエネルギー関数の形にもなっていません。これらの問題を一気に解決し、すべての交差点の状態を計算する式を作り、それを簡単に表現するために、ここでは「行列」を使います。
理解のため、水平3列、垂直3列の格子状に並んだ9つの交差点を定義し、行列表現で表してみましょう。
$$ \tag*{(3)} x_i(t+1) =x_i (t) + \frac{1}{4} \sum_{j \in N(i)} ( - \sigma_i (t) + \alpha \sigma_j (t) ) $$
$$ \tag*{(4)} \boldsymbol{x} (t+1) = \boldsymbol{x} (t) + (- \boldsymbol{I} + \frac{\alpha}{4} \boldsymbol{A} ) \boldsymbol{\sigma} (t) $$
$$ \tag*{(4')} \boldsymbol{x}(t+1) =\boldsymbol{x}(t) -\boldsymbol{I_\sigma}(t)+\frac{1}{4}a\boldsymbol{A}\boldsymbol{\sigma}(t) $$
$$ \tag*{(4'')} \begin{pmatrix} x_0(t+1) \\ x_1(t+1) \\ x_2(t+1) \\ x_3(t+1) \\ x_4(t+1) \\ x_5(t+1) \\ x_6(t+1) \\ x_7(t+1) \\ x_8(t+1) \end{pmatrix} = \begin{pmatrix} x_0(t) \\ x_1(t)\\ x_2(t)\\ x_3(t)\\ x_4(t)\\ x_5(t) \\ x_6(t) \\ x_7(t) \\ x_8(t) \end{pmatrix} - \begin{pmatrix} \sigma_0(t) \\ \sigma_1(t)\\ \sigma_2(t)\\ \sigma_3(t)\\ \sigma_4(t)\\ \sigma_5(t)\\ \sigma_6(t)\\ \sigma_7(t)\\ \sigma_8(t) \end{pmatrix} + \frac{1}{4}a \overset{\boldsymbol{A}}{\overset{\text{\textbardbl}}{ \begin{pmatrix} 0 1 0 1 0 0 0 0 0 \\ 1 0 1 0 1 0 0 0 0 \\ 0 1 0 0 0 1 0 0 0 \\ 1 0 0 0 1 0 1 0 0 \\ 0 1 0 1 0 1 0 1 0 \\ 0 0 1 0 1 0 0 0 1 \\ 0 0 0 1 0 0 0 1 0 \\ 0 0 0 0 1 0 1 0 1 \\0 0 0 0 0 1 0 1 0 \end{pmatrix}}} \begin{pmatrix} \sigma_0(t) \\ \sigma_1(t) \\ \sigma_2(t) \\ \sigma_3(t) \\ \sigma_4(t) \\ \sigma_5(t) \\ \sigma_6(t) \\ \sigma_7(t) \\ \sigma_8(t) \end{pmatrix} $$
9つの交差点の行列表現
(3)式における$x_i(t)$や$x_i(t+1)$はある1つの交差点の状態を表すための変数ですが、行列表記である(4)式における$x(t)$や$x(t+1)$はベクトル表記となっていてすべての交差点を同時に表しており、意味が違うのです。iが取れるのに加え見た目においても書体を区別して表現することが多いです。
※ベクトルとは行列の中でも成分が1列もしくは1行のものを指します。
(4'')は(4)の( )内を分配したものです。$I$とは単位行列と呼ばれており、(3)では$\Sigma$の中にあった$\sigma_i(t)$を$\Sigma$の外に出した上で行列表現したものです。$\Sigma$は各交差点$i$に対して4方向ある道路$j$の項を足し合わせることを表しているため$i$の項を$\Sigma$の外に出しても計算できるのです。
(4'')はさらに成分の行列表現に書き直したもので(4')と各項同士が対応しています。右辺の最後の項は$\Sigma$で足し合わせる$j$の成分です。$A$は交差点$i$に対し4方向の交差点を指定するための成分行列を表しています。今回は以下のような9つの交差点を行列形式にしています。0番の交差点に対して、$j$として指定されるのは隣接している1番と3番です。(4'')では$i=1$の関係式は1行目の要素を計算します。この時、右辺第3項の$\sigma$にかかる$j$を成分で示しているのも1行目の9つの数字です。左から順に0番の交差点、1番、2番、...8番です。このうち$j$として指定される1番目と3番目が$1$になっており、他は$0$です。このようにして$j$の交差点を指定できるというわけです。
行列表現の処理の中身がわかったところで、次の項からコスト関数として成型する処理をしていきます。
制約条件の整理
制約といえば、ある交差点の車両が増えれば隣接した交差点が混雑するといった事象は制約といえますが、これらの制約はここまでのモデル化において考慮が済んでいるため、新たに考慮する必要はありません。
この問題で考慮すべきことが他にあります。この問題では信号が変わることで車の滞りを減らしていくのですが、信号があまりに頻繁に変わりすぎるとかえって車の流れを阻害することになります。そこで隣り合う時間で信号が変わる場合に対してペナルティ（重みづけ）を設定することが必要です。これにより好ましい状態＝最適解をめざします。
$$\tag*{式(6)} ペナルティ = \eta (\boldsymbol{\sigma}(t)-\boldsymbol{\sigma}(t-1))^T(\boldsymbol{\sigma}(t)-\boldsymbol{\sigma}(t-1))$$
これは$\boldsymbol{\sigma}$の行列表現つまりエリア全体の$\boldsymbol{\sigma}$について時刻$t$とその前の時刻$t-1$における差をとり、さらに2乗したものです。
$\boldsymbol{\sigma}(t)-\boldsymbol{\sigma}(t-1)$の値は、時間$t$と$t-1$で同じになれば$0$、違う値だと$+2$(または$-2$)になるので、極力同じ値になるように計算を行います。
コスト関数の最終形
導いたコスト関数とペナルティ関数により、最適解を得るためのイジングモデルのエネルギー関数は以下のようになります。
$$ \tag*{式(7)} H = { \boldsymbol{x} (t+1) ^T \boldsymbol{x} (t+1) } + \eta ( \boldsymbol{\sigma}(t) - \boldsymbol{\sigma}(t-1) ) ^T ( \boldsymbol{\sigma}(t) - \boldsymbol{\sigma}(t-1) ) $$
これを全て$\boldsymbol{\sigma}(t)$で書きくだすと、
$$ \tag*{式(8)} H(\boldsymbol{\sigma} (t) ) = \boldsymbol{\sigma}(t) ^T \boldsymbol{J} \boldsymbol{\sigma} (t) + \boldsymbol{h} \boldsymbol{\sigma} (t) + c(t) $$
$J,h$は以下のようになります。$c(t)$は定数項です。
$$ \begin{align*} \tag*{式(9)} \boldsymbol{J} &= (-\boldsymbol{I} + \frac{\alpha}{4} \boldsymbol{A}) ^T (-\boldsymbol{I} + \frac{\alpha}{4} \boldsymbol{A}) + \eta \boldsymbol{I} \\ \boldsymbol{h} &= 2x(t) ^T (-\boldsymbol{I} + \frac{\alpha}{4} \boldsymbol{A}) - 2\eta \boldsymbol{\sigma}(t-1) ^T \end{align*} $$
これでアニーリングマシンが最適解を導き得る形に整えることができました。
入力データ作成とCMOSアニーリングマシンの実行
さあ、ここまで要件定義、定式化（モデル化、目的関数の設定、制約条件の整理）を行ってきました。
これ以降は、道路の範囲を狭めて$3 \times 3=9$個の交差点を考え、CMOSアニーリングマシンへ入力するデータの作成と実行を実際にやっていきましょう。
いかがでしたでしょうか。さらに大規模な道路を用いて信号制御を最適化した場合の動画がこちらです。このデモは、日立製作所の協創棟に展示する大規模CMOSアニーリングシステムを用いて64個x64個=4096個の交差点を最適化することで渋滞が解消されるシミュレーション結果を示しています。