ビハム・ミドルトン・レヴィン交通モデル（ビハム・ミドルトン・レヴィンこうつうモデル、Biham-Middleton-Levine Traffic Model, BML model）は自己組織化セル・オートマトンの交通モデルである。単純なルールでありながら、複雑な振る舞いにより、セルの流れがあたかも交通渋滞のように見える点に特徴がある。 このモデルは、1992年にオファー・ビハム
歴史
2004年、マイクロソフトリサーチのライサ・ド・ソウザ（英語版）は、ある条件では、渋滞と流動が周期的に繰り返される中間的な状態となることを発見した[3]。 このモデルでは、平面が細かい格子（セル）に分けられており、初期状態では「青い車」と「赤い車」がセルの中にランダムに配置されている。そして「青い車が動く順番」と「赤い車が動く順番」が交互に訪れる。「青い車が動く順番」では、全ての「青い車」が一斉に、一つ下のセルに移動する。ただし下のセルに「他の車」がいる場合は、そのままその位置に留まる。平面の下は平面の上に繋がっているので、下端の「青い車」は上端に移動する（上端に他の車がいなければ）。「赤い車が動く順番」では、全ての「赤い車」が一斉に、一つ右隣りのセルに移動する。多くの場合、「青の順番」と「赤の順番」をセットで「1回」と数える。図2. BMLモデルの説明図 5×5の格子の例で説明する。図2の左図の状態から始まり、次が「青の順番」だった場合、「青1」の下は空いているので、「青1」は下に移動する。「青2」の下には「赤1」がいるので、「青2」は移動しない。「青3」の下には「青4」がいるので移動できない[4]。（「青4」は下に移動できるので「青3」も移動できる、として計算されることもある。）「青5」「青6」も移動できない。「青7」は最下部だが、この下は最上部に繋がっているので、「青7」は一番上に移動する。結果として図2の中央図の状態となる。この次は「赤の順番」となり、「赤4」と「赤5」以外は1つ右に移動でき（「赤2」は一番左に移動する）、結果として図2の右図の状態となる。 モデルがシンプルであるにもかかわらず、この交通モデルでは、全ての車が停止することなく動く「自由流動段階」（free-flowing phase）と、全ての車が停止する「渋滞段階」（jammed phase）という、両極端な段階に到達する場合が多い[1]。正方格子の場合、車の密度が32%を下回ると自由流動段階に、32%を上回ると渋滞段階になりやすい[5]。 図3と図4は同じ200×200の格子であるが、図3は「車」の密度が30%、図4は36%に設定してある。図3は初期にはランダムであるが、だんだんと赤と青の層に分かれていき、やがて全ての車が停止することなく移動する段階、すなわち自由流動段階になる。一方で、図4も初期にはランダムだが、だんだんと渋滞がひどくなって、ついには全ての車が停止した段階、つまり渋滞段階となる。 図3: 最後に自由流動段階となる例。最終的には、全ての車が安定して動くことになるので、この縞模様が平行移動しているように見える。左上が初期状態で、右上が最終的な段階。下のグラフは車の移動度の経時変化であり、0が完全渋滞、1が無渋滞を意味する。繰り返し3000回弱で自由流動段階になっている。図4: 最後に完全な渋滞段階となる例。右上が最終状態であり、この状態で膠着状態となり、全ての車が停止する。繰り返し1500回弱で完全渋滞している。 次の図5と図6は、初期状態から自由流動段階、あるいは渋滞段階になるまでを表した動画である。図5: 最後に自由流動段階となる例。144×89の格子で交通密度28%図6: 最後に完全渋滞段階となる例。144×89の格子で交通密度60% 中間段階は、自由流動段階と渋滞段階が切り替わる密度に近いところで発生し、部分的に自由流動の部分と渋滞の部分とが混在する。 「中間状態」には2種類ある。1つは、移動する車同士に一定の車間（多くの場合3台分）ができて整然と移動する「周期的状態」(PeriodicIntermediate state, PI)である。もう一つは、車間が無秩序に変化する「無秩序状態」（Disordered Intermediate state, DI）である。それに加えて広範囲な渋滞（global jam, GJ）の部分があるので、中間状態はPI, DI, GJの3箇所を含む場合が多い[6]。正方格子が中間状態になる場合、一般には無秩序となりやすいが、2008年には正方格子でも周期的な中間状態となる条件が見つかっている[6]。周期的状態の部分が多い例。144×89の格子、密度38%。無秩序状態の部分が多い例。144×89の格子、密度39% このモデルでは、右から出た車が左に、下から出た車が上に移動するため、これが交通の流れに影響する。領域の2辺の格子数が「互いに素」の場合に中間状態となると、周期的部分が多く渋滞部分が少ない状態になりやすい。逆に、2辺の格子数が共通の約数を持つ場合、渋滞が生じやすく、結果として無秩序部分が多くなる[3]。 このモデルは、右辺と左辺、上辺と下辺がまっすぐ繋がった状態について解析されることが多いが、捩じって接続した場合についても研究されている。 2009年、セビリア大学のカンポーラらは、このモデルの境界条件を、 (a) 「トーラス構造」。つまり、本来のルール通り。 (b) 「クラインの壺構造」。青い車が下端の下に移動する場合、上端の左右が反対の位置に出現させる。例えば前記の図2の左図で説明するなら、「青7」の車は1行目5列目ではなく、1行目1列目の位置に出現させる。赤い車の動きは本来のルール通りとする。 (c) 「 実射影平面構造」。(b)に加えて、赤い車が右端から右に移動する場合に左端の上下が反対の位置に出現させる。 の3つで、横軸を密度、縦軸を車の移動度で表したグラフの減少速度について検討した。 その結果、「クラインの壺構造」では「トーラス構造」よりも移動度の減少速度がわずかに速く、「 実射影平面構造」では「トーラス構造」よりも移動度の減少速度がわずかに遅いことが明らかになった[7]。 2010年、中国科学技術大学の丁中俊らは、下辺と右辺から出ていく車はそのまま削除し、新しい車を上辺と左辺のランダムな位置に追加していく場合についての研究を行った[8]。このルール変更が与える影響は大きく、(a) 渋滞となる領域が右下の矩形部分に集中し、その外側は自由流動となる、(b) 渋滞部分が複雑な構造とならず、「青い車の領域」と「赤い車の領域」が、ほぼ1つに纏まってしまう、という特徴がある[8]。 このモデルは単純だが、厳密な解析は非常に困難である[5]。このモデルに対する数学的証明は、これまでのところ、パラメーターが極端な値の場合に限定されて行われている。 2005年4月、ブリティッシュコロンビア大学のエンジェルらは、密度が1に近い場合、常に渋滞が発生することを厳密に証明した[9]。 2006年、カリフォルニア大学ロサンゼルス校のティム・オースティンらは、N×Nの正方格子の場合、車の数がN/2以下であれば、常に全ての車が停止することなく移動できる状態になることを発見した[10]。
ルール
自由流動段階と渋滞段階
中間段階
512×512の格子で密度31%で64000回繰り返した例。「青い縞」と「赤い縞」の交点付近が無秩序になっている。512×512の格子で密度33%で64000回繰り返した例。縞の太さは異なるが、やはり交点付近が無秩序になっている。512×512の格子で密度37%で64000回繰り返した例。交点だけではなく、縞の中にも無秩序状態の部分が見られる。
2辺が互いに素の場合
境界条件の影響
乱数化
数学的証明
参考文献^ a b Biham, Ofer; Middleton, A. Alan; Levine, Dov (November 1992). “Self-organization and a dynamical transition in traffic-flow models”
