T-QARD Harbor

               

量子アニーリングを用いた交通最適化

2025年11月17日

文献情報

概要

この論文では、交差点で待機する車両数と隣接する交差点の信号状況をもとに、適切な信号を選択するという交通信号最適化問題を解く方法について考えます。

その問題を解くためにこの論文では効率の良い信号制御のため、「より多くの車を流す」点と、「より隣接交差点からスムーズに流れるようにする」という2点に着目し、量子アニーリング用に定式化しました。
その結果、定式化した式と量子アニーリングを用いて、より効率の良い信号の組み合わせを得ることができました.

交通状況に応じてQUBO定式化をし、得られた解をもとに信号状況を割り当てる

図1 概要図

背景

交通信号最適化問題を従来の古典的なコンピュータで古典的なアルゴリズムで解こうとすると、計算時間が指数関数的にかかってしまう問題があります。 しかし量子アニーリングを用いることで、その問題を高速に解くことが可能になると考えられます。

量子アニーリング

ここで、量子アニーリングについて軽く説明します。

量子アニーリングは、門脇・西森によって提案された[1]物理的な量子効果を用いて組み合わせ最適化問題を解く手法です。 式(1) のような コスト関数\(E(x)\)が最も小さくなるようなベクトル$x$、つまり、$x_i$の組み合わせを求める、2次制約なし二値最適化問題(QUBO)を解くのを得意とします。

$$
\tag{1}
\begin{aligned}
E(\bm x) = \sum_i \sum_j Q_{i j} x_i x_j
\end{aligned}
$$
ここで、$x_i$は求める対象である、0か1を持つバイナリ(二値)変数です。 $Q_{ij}$は求める最適化問題によって異なる実数の行列の要素で、$Q_{ij}$を並べた行列をQUBO行列といいます。

交通最適化

なぜ交通最適化が求められているのでしょうか。

平成18年の国土交通省の報告によれば、全国に年間で発生する渋滞損失は貨幣価値換算で約12億円であり、環境問題や経済効率の低下を引き起こしているとされています[2]。 特に渋滞によるCO2の排出量増加は気候変動対策の観点からも深刻な問題です。
そのため信号最適化の導入は交通最適化に対し効果的であると考えられています。 1984年には当時のオリンピックのためにロサンゼルス市交通局(LADOT)がATSACと呼ばれる信号制御を導入しました。 その結果移動速度の13%の増加、32%の交通遅延(移動にかかる時間)の削減、3%の排出量の削減をもたらしたと報告されています[3][4]。

このように交通最適化は現状大きな課題であり、これに対しての信号最適化の導入は大きな利点をもつものと考えられます。

手法

この問題では図2のような道路網を考えます。 ここには十字の形をした各交差点に信号機が設置されています。

それぞれの交差点にある信号は 図3 に示す6つのパターンで動作します。 この6つのパターンを論文では「モード」と表現しています。 なお今回は信号の状態にかかわらず、常に左折できるものとします。

方針

今回は信号に次のような動作をさせることで交通信号最適化を行います。

  1. 停車中の車をできる限り減らす
    それぞれの交差点で停車する車ができる限り減るようにします。
  2. 信号が連続する交差点で連続的に車が通れるようにする
    前の交差点から来た車が現在の交差点で極力止まらずに進めるようにします。

定式化

先ほど示した方針をもとに、交通信号最適化問題をQUBO形式で定式化します。

目的関数

まず求める対象の二値変数$x_{i j}$は信号$i$のモードが$j$であるとき1、それ以外の時0とします。 たとえば、通し番号3の交差点のモードが4であることは、
$$
\tag{2}
\begin{aligned}
x_{31}=0, x_{32}=0, x_{33}=0, x_{34}=1, x_{35}=0, x_{36}=0
\end{aligned}
$$
と表されます。

そして目的関数の全体を、方針1を達成させる項$Q_1$、方針2を達成させる項$Q_2$、そして変数の制約を満たさせるための制約項$Q_3$の和である、
$$
\tag{3}
\begin{aligned}
E(x)=Q_1 + Q_2 + Q_3
\end{aligned}
$$
とします。 この$E(x)$を最小化する$x$が最適な信号の組み合わせを表します。

次に各項の詳しい説明をします。

方針1の項

まずは、方針1を定式化します。 方針1は、「信号が停車中の車をできる限り減らすように機能する」です。 この方針を達成させるための項は式4のように示すことができます。
$$
\tag{4}
\begin{aligned}
Q_1 = -\lambda_1 \sum_i \sum_{j=1}^6 C_{ij} x_{ij}
\end{aligned}
$$

ここで、$C_{ij}$は$x_{ij}=1$の時(交差点$i$のモードが$j$の時)にどれくらいの車を動かすことができるか(待機車を減らすことができるか)を示す値です。

具体的に$C_{ij}$がどのようにあらわされるかを説明します。 交差点四方の待機場所に添え字$k$を図4のように割り振ります(これをポジションと呼びます)

交差点の4方位にポジションが与えられている. 北, 南, 東, 西の待機場所にk=1, 2, 3, 4のポジションを示す数字が割り振られている

図4 ポジション図
https://doi.org/10.1007/s11128-020-02815-1をもとに再作成

そして、交差点のそれぞれの場所に待機している車の数を$a_i^k$、その中で直進(右折ではなく)したい車の割合を$f_i^k$と表現します。

たとえば、交差点$i$の北側($k=1$)に待機している車の数が16、右折か直進をする車のうち75%が直進を希望しているとするならば、$a_3^1=16, f_3^1=0.75$と表現できます。 このように定義したとき、$C_{ij}$は次のように表現できます。
$$
\tag{5}
\begin{aligned}
C_{i1}=f_i^1 a_i^1 + f_i^2 a_i^2
\end{aligned}
$$
$$
\tag{6}
\begin{aligned}
C_{i2}=a_i^2
\end{aligned}
$$
$$
\tag{7}
\begin{aligned}
C_{i3}=a_i^1
\end{aligned}
$$
$$
\tag{8}
\begin{aligned}
C_{i4}=f_i^3 a_i^3 + f_i^4 a_i^4
\end{aligned}
$$
$$
\tag{9}
\begin{aligned}
C_{i5}=a_i^4
\end{aligned}
$$
$$
\tag{10}
\begin{aligned}
C_{i6}=a_i^3
\end{aligned}
$$

例えば信号モード1では、北から南と南から北の直進行動が許されるので、$C_{i1}$は北から南に直進する$f_i^1 a_i^1$台と南から北に直進する$f_i^2 a_i^2$台の和だといえます。 また信号モード2では、南から右折と直進の両方の行動が許されるので、南に待機するすべての車を動かすことができます。 $C_{i2}=a_i^2$だと表現できます。

方針2の項

方針2の「信号が連続する交差点で、連続的に車が通れるように機能する。」は次のように表します。
$$
\tag{11}
\begin{aligned}
Q_2 = -\lambda_2 \sum_{i=1}^n \sum_{j=1}^6 C_{ij} x_{ij} \left[\tau_{i,a’} \lambda_3 C_{a’ a} x_{a’ a} + \tau_{i,b’} \lambda’_3 C_{b’b}x_{b’, b}+ \tau_{i, c’} \lambda_3 C_{c’ c}x_{c’,c} + \tau_{i, d’} \lambda’_3 C_{d’d} x_{d’,d}\right]
\end{aligned}
$$
ここで, $\{a’, b’, c’, d’\}$は着目している交差点に隣接している交差点の番号を、$\{a,b,c,d\}$はその隣接交差点のモードを表します。 また、$C_{ij}$は$Q_1$と同様に交差点$i$がモード$j$の時に移動できる車の台数を表します. 隣接交差点の番号 $\{a’, b’, c’, d’\}$ や、$\{a,b,c,d\}$ がとる値は注目する交差点$i$のモード$j$によって異なります。 図5はその対応表を示しています。

図5 $\{a, b, c, d\}$と$\{a’, b’, c’, d’\}$の対応表
https://doi.org/10.1007/s11128-020-02815-1

図5をもとに具体的にどのような値をとるかを見てみましょう。 図6のようなグリッド状マップにおいて、着目している交差点$i=5$、モード$j=1$の場合を考えます。

図6 交差点

まず隣接交差点$\{a’, b’, c’, d’\}$を考えましょう。 モード$j=1$の場合は南から北、北から南に進行が可能なので、隣接交差点$\{a’, b’, c’, d’\}$は、北か南を考えればよいはずです。 実際図4では、モード$j=1$のときは、それぞれ北、北、南、南に隣接する交差点を指していますので、図5 で$i=5$ならば、(a’,b’,c’,d’)=(2,2,8,8)$となります。

次に$\{a,b,c,d\}$の具体値についてです。 図5 に従えば$j=1$のとき、$\{a, b, c, d\}$はそれぞれ、$\{1,2,1,3\}$が代入されます. 実際に、交差点$\{2,2,8,8\}$のモードが$\{1,2,1,3\}$の時の通行可能方向を示す矢印を図示してみると、それぞれ図7a、図7b、図7c、図7d のようになります。 さらに図5では$a’, c’$より, $b’, d’$の方が車が流れやすくなるようになっています。 実際に図7a-7dの4パターンをよく見ると、図7b、7dの場合の方が図7a、7cの場合よりも多くの車が流せそうなことがわかります。 したがって、$b’. d’$のほうが, $a’, c’$よりも選ばれやすくなるように、$a’, c’$の係数$\lambda_3$よりも、$b’, d’$の係数$\lambda’_3$のほうが、値が大きくなるように設定します。

図7a
図7a
図7b
図7b
図7c
図7c
図7d
図7d

交差点間を車が移動する時間も考えなくてはいけません。 そのため, 交差点から交差点への移動時間を考慮して、$\tau_{i i’}$という0か1の値を持つ変数を使います。
シミュレーション開始からの経過時間を$t$とし、交差点$i’$から$i$に移動するのにかかる時間を$T$とし、$ t \bmod T \approx 0 $のときに$\tau_{i i’}=1$として交差点間の信号同期をはかり、それ以外の時は$\tau_{i i’}=0$とします。

もっと具体的に考えてみましょう。
例えば交差点1から交差点2への道路長300m、速度制限は10m/sとしましょう。 すると、交差点1を出発した車は30s後に交差点2に達します。

  • $t=0$では車両はまだ交差点2に達さないので$\tau_{12}=0.$(交差点間信号同期なし)
  • $t=5$では車両はまだ交差点2に達さないので$\tau_{12}=0.$(交差点間信号同期なし)
  • $t=30$で車両は交差点2に達するので$\tau_{12}=1.$(交差点間信号同期をする)
  • $t=35$では周期を過ぎたので$\tau_{12}=0.$(交差点間信号同期なし)

制約項

最後に変数の制約を満たさせるために用意する制約項を紹介します。

交差点$i$では同時に1つのモードしか取れません。 したがって$ x_{31}=0, x_{32}=1, x_{33}=0, x_{34}=1, x_{35}=0, x_{36}=0 $というような結果を除外する必要があります。 そのため次のような項を導入します。
$$
\tag{12}
\begin{aligned}
Q_3 = \lambda_4 \sum_i \left[1-\sum_{j=1}^6 x_{i j}\right]^2
\end{aligned}
$$
$\lambda_4$をかなり大きな値に設定することで、$Q_3=0$が満たされるようにし、制約を満たすようにしています。

実験

以上の定式化を用いて、シミュレーターを用いた数値実験を行います。

方法

6×6の合計36交差点のあるグリッド状マップにランダムに車を配置し、シミュレーション内で時間経過をさせて車を移動させたり、アニーリングマシンの計算結果に沿って信号を変化させたりして、交通信号最適化のシミュレーションを行います。

次のようなフローでシミュレーションを行います。

  1. 車密度データとどの信号を同期させるかに関する情報処理
  2. シミュレーション5反復ごとにQUBO定式化
  3. 2. で定式化したものをもとに交通の流れがスムーズになる信号の組み合わせを求める
  4. 計算結果をもとに信号を更新
  5. シミュレーションを1進める (車の位置を更新する)

実験条件は以下の通りです。

    • 交差点は6×6の36個
    • 道路制限速度[m/s] = 11, 17, 22, 28(ランダム)
    • 交差点から交差点まで1km
    • すべての交差点で$f_i^k=0.7$(70%が直進, 30%が右折); ただし、シミュレーション上には左折車は「存在しない」
    • マップの端から外に出た車はシミュレーションから除外する。 つまりシミュレーション上で車は減少していく
    • シミュレーションは150反復。 5反復ごとにQUBO定式化とアニーリングマシンでの最適化。 つまりシミュレーション中30回信号更新のタイミングがある。
    • $\lambda_1=1, \lambda_2=60, \lambda_3=0.3, \lambda’_3=0.7, \lambda_4=60$

結果

交通信号最適化の評価指標として、”Time Wasted”(時間損失)という指標を用います。 この “Time Wasted” がより小さいほど、交通信号最適化がより良く機能しているといえます。
$$
\tag{12}
\begin{aligned}
\text{Time Wasted} = \frac{\text{Speed limit of next road segment}}{\text{maximum speed limit}} \times N
\end{aligned}
$$
ただし、

  • Speed limit of next road segment [m/sec]: 交差点の先の道路の制限速度
  • Maximum speed limit [m/sec]: マップに存在する制限速度で最大のもの
  • $N$ [sec]: 単位時間あたりにそれぞれの交差点に待機している次に進みたい車の数

図8は、これらのシミュレーションを様々な手法で行った時の Time Wasted の比較です。

図8 各信号最適化方法でのTime Wastedの比較
https://doi.org/10.1007/s11128-020-02815-1

ここで、Fixed Cycle というのは交通データに依存せず純粋に時間経過のみで信号を変更するサイクルであり、その方法より式$Q_1 + Q_3$を用いて流動的な交通量を考慮して計算したパターンのほうが Time Wasted が小さくなっています。
さらに、$Q_1 + Q_3$を用いたパターンよりも、隣接交差点との関連も含めて最適化を行っている$Q_1 + Q_2 + Q_3$のパターンのほうが多少ではありますがさらに Time Wasted が小さくなっており、より効果的に交通信号最適化できているといえます。

まとめ

今回紹介した論文では効率の良い信号制御のため、「より多くの車を次の交差点へ移動させる」と、 「より隣接交差点からスムーズに通過できるようにする」という2つの観点で定式化を行いました。 そのうえで量子アニーリングを用いることによって、より車移動での時間の無駄が小さくなるような、効率の良い信号の組み合わせを得ることができました。

あとがき

交通信号最適化などの身近な課題を簡単な形に定式化し、最適化できるということに大変魅力を感じます。 今回の論文では格子状の道路で考えましたが、複雑な道路でも実践できたらなと感じます。

参考文献

[1] Kadowaki, T. & Nishimori, H. (1998) “Quantum annealing in the transverse Ising model.” https://doi.org/10.1103/PhysRevE.58.5355
[2] 国土交通省 効果的な渋滞対策の推進 (2006) https://www.mlit.go.jp/road/ir/ir-perform/h18/07.pdf
[3] LADOT “ATSAC” https://ladot.lacity.gov/projects/transportation-technology/atsac
[4] LADOT “ATSAC Fact Sheet 2018 Rev 1124” https://ladot.lacity.gov/sites/default/files/documents/atsac-fact-sheet-2018-rev-1124.pdf

本記事の担当者

土屋徹雄

Post Views: 16

Table of Contents

← Table of Contents