元胞自動機模型在交通流中的應用研究

姚層林++左傳

摘要：由于目前交通狀況帶來的諸多問題，通過科學理論的指導增進對交通系統的管理和控制，充分利用其資源，減輕環境污染并解決其他問題，達到安全與便捷的較好統一。元胞自動機模型已廣泛應用于交通領域的研究，它的建立是描述和模擬復雜交通系統的最好方法。根據不同道路的交通情況，構建交通流模型，以定量的視角理解交通擁堵的成因。交通狀況隨著社會發展而不斷變化，元胞自動機在交通系統的應用，對于推動元胞自動機模型的改進和完善交通運輸情況具有重要意義。

關鍵詞：元胞自動機模型 交通流理論 應用研究

中圖分類號：TP23.U491 文獻標識碼：A 文章編號：1007-9416（2016）10-0080-03

元胞自動機（Cellular Automata，簡稱CA）實質上是定義在一個具有離散、有限狀態的元胞組成的元胞空間上，并按照一定的局部規則，在離散的時間維度上演化的動力學系統。實際上，著名計算機科學家Von Neumann早在1968年就提出元胞自動機基本思想[1]。他提出模仿人腦的行為，人腦包含自控制和自維護機理，這個元胞系統按照離散時間進行演化。Wolfram提出了元胞自動機的動力學分類方法，1986年，M.Cremer和J.Ludwig將CA最早應用于交通系統[2]的研究。元胞自動機從產生以來，被廣泛地應用到生物學、生態學、物理學、化學、交通科學等多個領域。交通系統是一個十分復雜、具有不確定性的系統，CA的特點與交通流的特點極其相似，決定了CA在交通領域應用的合理性。用CA對交通系統進行模擬，體現交通流的變化特征，尋找交通流的規律，揭示交通擁堵產生的機理，進而有效地改良交通運輸狀況。

1 CA基礎理論

1.1 構成

CA最基本的組成單元是元胞、元胞空間、鄰居及規則四部分，另外還應包括元胞的狀態和時間，如圖1所示?？梢詫A視為一個元胞空間和定義于該空間的變換函數所組成。

1.2 元胞

CA最基本的組成部分就是元胞，又稱為單元、細胞或基元，離散地分布于一維、二維或多維歐幾里得空間的晶格點上。某一時刻，每個元胞都有自己的狀態。

1.3 元胞空間

元胞在空間中分布的網格點的集合就是元胞空間。目前研究多集中在一維和二維元胞自動機上。一維元胞自動機的元胞空間只有一種劃分，二維元胞自動機通常有三種劃分方式：三角形、正方形和正六邊形，如圖2、圖3所示。對于高維的元胞自動機，元胞空間的劃分則可能有多種形式。

1.4 鄰居

在元胞自動機中，一個元胞下一時刻的狀態決定于本身狀態和它的鄰居元胞的狀態。通常以半徑來確定鄰居，距離一個元胞內的所有元胞均被認為是該元胞的鄰居。二維元胞自動機通常有以下幾種鄰居：Von Neumann型、Moore型和擴展的Moore型，如圖4所示的結構。

1.5 邊界條件

理論上，元胞空間通常是在各個維度上無限延展的，但是在實際應用中，理論條件無法在計算機上實現，所以需要定義不同的邊界條件。

1.6 演化規則

演化規則是根據元胞當前狀態及其鄰居狀況確定下一時刻該元胞狀態的動力學函數，簡單來說，就是一個狀態轉移函數。記為+1=f（，），我們稱f為元胞自動機的局部映射，為t時刻i元胞的鄰居元胞狀態[3]。

2 元胞自動機的一般特征

從元胞自動機的定義及構成分析，元胞自動機具有如下特征[4]：同質性、齊性；時間離散；空間離散；狀態離散有限；同步計算；時空局域性；維數高。元胞自動機的價值取決于其演化規則，體現在元胞的動力學系統的內涵。

3 交通流理論

3.1 交通流基本參數的關系

交通流基本參數有交通流量、車輛速度、車輛密度、車頭間距和車頭時距等，在實際的研究領域中，最重要的三個基本參數是交通流量、行車速度和交通密度。交通流量，即單位時間內通過交通道路某斷面的車輛數，用符號q表示；行車速度為道路上車輛行駛速度的平均值，用符號v表示；交通密度，即某一瞬間單位長度的車道上行駛的車輛總數，用符號k表示。三者之間的關系可表示為：q=v×k（q、v、k的單位分別是輛/小時、公里/小時和輛/公里，這一關系式稱為交通流基本模型）。

3.2 交通實測現象

3.2.1 交通堵塞

交通堵塞是一種常見的、研究廣泛的交通現象。日常生活中人們理解的堵塞和交通流理論中的堵塞有一定的區別：通常人們理解的車速遠遠低于最大車速、車流量非常低時才是堵塞；而在交通流理論中，只要車輛以低于最大值的速度行駛且車道出現集簇現象，就稱之為堵塞。實測的交通堵塞，大多發生在交通瓶頸的上游；比如道路縮減和交叉路口的上游[5]。交通瓶頸處，主干道的車輛密度增大，道路的局部通行能力降低，使得瓶頸的上游易處于交通擁堵狀態；一段時間的交通疏導使得車輛逐漸恢復正常行駛，所以瓶頸的下游多為典型的自由流狀態。此外，交通事故易導致車輛聚集，也是產生堵塞的一個原因。

3.2.2 自組織現象

自組織現象是指系統通過系統內部各子系統之間的非線性相互作用，在一定的條件下，自發產生在時間、空間和功能上穩定的結構。在真實的交通中，存在著一定的密度區域，在該區域內交通流的狀態是亞穩定的，由于車輛之間的相互作用，一些交通流的狀態會自發形成[6]。比較典型的是向后傳播的堵塞波的形成，這種堵塞的特點有：（1）產生堵塞的隨機性；（2）堵塞幅度的不斷變化；（3）堵塞會消失。一般來說，這種現象易發生在入口、出口匝道等瓶頸處。

4 交通應用

車輛組成的交通流實質是一個離散系統，而又緊密相互聯系，導致復雜的交通現象。元胞自動機模型是交通流模型的理論基礎，能夠從微觀層面分析復雜交通系統的研究工具。184號模型是以Wolfram命名的最基本的一維元胞自動機模型，其中包含的基本要素能夠實現一些交通現象的模擬，但是不能完全適應復雜的實際交通狀況。目前交通流的元胞自動機大致可分為兩大類：以NS模型為代表的研究高速公路的模型，以BML模型為代表的研究城市網絡交通的模型，這兩類模型是對184號模型的進一步完善和發展。

4.1 NS模型

NS模型，由一維CA模型簡化而來，于1992年由德國學者Nagel和Schreckenberg提出[7]。

在NS模型中，時間、空間和車輛速度都被整數離散化，道路被劃分為等距離的離散的格子，即元胞，并且每個元胞或者是空的，或者被一輛車所占據，車輛n行駛的速度為Vn（t），速度可以取0，1，2，……，Vmax，Vmax是行駛車輛在道路上的最大行駛速度。車輛n和其前車n-1在時間步t的位置用Xn-1（t）和Xn-1（t）表示，dn（t）代表車輛n與其前車的車間距，即dn（t）=Xn-1（t）-Xn-1（t）-1。Pn（t）為車輛n在時間步t時隨機慢化過程中的減速概率。ΔVn（t）是車輛n與其前車n-1的行駛速度之差，即ΔVn（t）=Vn（t）-Vn-1（t）。該模型以如下規則演化：

（1）加速，Vn（t+1）→min（Vn（t）+1，Vmax），表示駕駛員期望以最大速度駕駛車輛；

（2）減速，Vn（t+1）→min（Vn（t+1），dn（t）），表示避免與前車發生事故；

（3）隨機慢化，以減速概率P使車輛的行駛速度Vn（t+1）→max（Vn（t+1）-1，0），表示實際的交通情況下各種不確定的因素使得減速行駛；

（4）運動，Xn（t+1）→Xn（t）+Vn（t+1），車輛位置更新，速度調整，繼續向前運動。

NS模型具有簡單的形式，僅用4條演化規則就表達出車輛行駛的不同情況。為了能夠描述更多復雜的交通現象，在NS模型的基礎上衍生和發展了許多模型，比如通過改進慢化規則，提出慢啟動模型，巡航控制極限模型；通過改進加速規則，提出FI模型；以及考慮前車速度效應的模型，舒適駕駛模型等等。

4.2 BML模型

一維高速公路交通流模型很難模擬出二維城市交通系統的復雜的道路網結構，而BML模型實現了復雜路網結構的模擬。1992年，O.Biham，A.Middleton和D.Levine[8]三位學者提出一種元胞自動機模型（BML模型）用來模擬城市道路的交通現象，研究了交通堵塞的問題。簡單形象的BML模型定義在一個N×N的方形格點網絡中，點陣上分布著僅有東西方向和南北方向行駛的數目相等的兩種車輛，每個格點可以擁有一輛南北方向行駛的車輛，也可以有一輛東西方向行駛的車輛，還有一種可能就是沒有車輛占據。在每一個奇數時間步內，南北方向的車輛可以向前進一格；在每一個偶數時間步內，東西方向的車輛可以向前進一格；若車輛前方的格點以被其他車輛占據，因此這輛車只能保持靜止不動。在這種情況下，兩個方向的車輛分別在奇偶時間步內行駛，每個格點相當于信號控制的交叉路口，反映出交通信號燈的作用。

4.3 NS和BML耦合模型

BML模型不能完整地體現實際交通情況，表現在：（1）BML模型只有兩個車流運動方向，未考慮其它轉動方向；（2）BML模型中網絡沒有路段，只有交叉口。1999年，Chowdhury和Schadschneider等學者提出了一個更符合實際的W×W條道路組成的路網。基于BML模型，將兩個相鄰交叉口之間的路段（包括其中的一個交叉口）劃分為D個元胞。因此每一條道路有W×D個元胞。在任意時刻，每一個元胞或者保持靜止，或者被其他車輛占據。當D=1時，路網結構為BML模型。如圖5所示，其中N=5，D=8東西方向和南北方向車輛分別用符號→和↑表示。

在該組合模型中，堵塞產生的內因與NS模型相近，系統自發的堵塞現象與BML模型十分類似。

5 結語

以上對應用前景進行了分析，建立了符合交通實際情況的模型，結果體現出：（1）通過元胞自動機在交通中的研究，可以形象地模擬出交通路口車輛的通行情況。（2）構建的元胞自動機模型具有時間、空間的離散性，決定了它在交通領域的重要價值。（3）城市交通網絡受多種因素影響，交通擁堵的成因及分布十分復雜，還有許多問題未考慮?？梢詮母缶W絡規模、更符合實際的交通流量開展進一步研究。

參考文獻

[1]V.Neumann.Celluar automata[M].New York：Academic Press，1968.

[2]S.Wolfram.Statistical mechanics of celluar automata[J].Rev.Mod.Phys.1983，55：601-644.

[3]B.Chopard and M.Droz.Celluar Automata Modelling of physical systems，//祝玉學，趙學龍（譯）.物理系統的元胞自動機模擬.北京：清華大學出版社，（2003）.

[4]謝惠民.非線性科學從書：復雜性與動力系統.上海：上海科技教育出版社，（1994）.

[5]C.F.Daganzo，M.J.Cassidy，R.L.Bertini.Possible explanations of phase transitions in highway traffic [J].Transp.Res.A，1999，33：365-379.

[6]B.S.Kerner.Experimental features of self-organization in traffic flow [J].Phy.Rev.Lett，1998，81（17）：3797-3800.

[7]K.Nagel，M.Schreckenberg.A celluar automaton model for freeway traffic [J].J.Phys.I（France）1992，2：2221-2229.

[8]O.Biham，A.A.Middleton，D.A.Levine.Self-organization and a dynamical transition in traffic flow models[J].Phys.Rev.A 1992，46：R6124-R6127.

收稿日期：2016-08-26

基金項目：武漢市社科基金項目《大規模建設背景下的武漢道路擁堵區域疏散管理研究》（項目編號：14021）研究成果。

作者簡介：姚層林（1972—），男，山東日照人，教授，高級工程師，畢業于華中科技大學碩研，研究方向：交通運輸工程、高等教育管理等。