元胞自動(dòng)機(jī)模型在交通流中的應(yīng)用研究

姚層林++左傳

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

關(guān)鍵詞：元胞自動(dòng)機(jī)模型 交通流理論 應(yīng)用研究

中圖分類號(hào)：TP23.U491 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）10-0080-03

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

1 CA基礎(chǔ)理論

1.1 構(gòu)成

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

1.2 元胞

CA最基本的組成部分就是元胞，又稱為單元、細(xì)胞或基元，離散地分布于一維、二維或多維歐幾里得空間的晶格點(diǎn)上。某一時(shí)刻，每個(gè)元胞都有自己的狀態(tài)。

1.3 元胞空間

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

1.4 鄰居

在元胞自動(dòng)機(jī)中，一個(gè)元胞下一時(shí)刻的狀態(tài)決定于本身狀態(tài)和它的鄰居元胞的狀態(tài)。通常以半徑來確定鄰居，距離一個(gè)元胞內(nèi)的所有元胞均被認(rèn)為是該元胞的鄰居。二維元胞自動(dòng)機(jī)通常有以下幾種鄰居：Von Neumann型、Moore型和擴(kuò)展的Moore型，如圖4所示的結(jié)構(gòu)。

1.5 邊界條件

理論上，元胞空間通常是在各個(gè)維度上無限延展的，但是在實(shí)際應(yīng)用中，理論條件無法在計(jì)算機(jī)上實(shí)現(xiàn)，所以需要定義不同的邊界條件。

1.6 演化規(guī)則

演化規(guī)則是根據(jù)元胞當(dāng)前狀態(tài)及其鄰居狀況確定下一時(shí)刻該元胞狀態(tài)的動(dòng)力學(xué)函數(shù)，簡單來說，就是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)。記為+1=f（，），我們稱f為元胞自動(dòng)機(jī)的局部映射，為t時(shí)刻i元胞的鄰居元胞狀態(tài)[3]。

2 元胞自動(dòng)機(jī)的一般特征

從元胞自動(dòng)機(jī)的定義及構(gòu)成分析，元胞自動(dòng)機(jī)具有如下特征[4]：同質(zhì)性、齊性；時(shí)間離散；空間離散；狀態(tài)離散有限；同步計(jì)算；時(shí)空局域性；維數(shù)高。元胞自動(dòng)機(jī)的價(jià)值取決于其演化規(guī)則，體現(xiàn)在元胞的動(dòng)力學(xué)系統(tǒng)的內(nèi)涵。

3 交通流理論

3.1 交通流基本參數(shù)的關(guān)系

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

3.2 交通實(shí)測(cè)現(xiàn)象

3.2.1 交通堵塞

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

3.2.2 自組織現(xiàn)象

自組織現(xiàn)象是指系統(tǒng)通過系統(tǒng)內(nèi)部各子系統(tǒng)之間的非線性相互作用，在一定的條件下，自發(fā)產(chǎn)生在時(shí)間、空間和功能上穩(wěn)定的結(jié)構(gòu)。在真實(shí)的交通中，存在著一定的密度區(qū)域，在該區(qū)域內(nèi)交通流的狀態(tài)是亞穩(wěn)定的，由于車輛之間的相互作用，一些交通流的狀態(tài)會(huì)自發(fā)形成[6]。比較典型的是向后傳播的堵塞波的形成，這種堵塞的特點(diǎn)有：（1）產(chǎn)生堵塞的隨機(jī)性；（2）堵塞幅度的不斷變化；（3）堵塞會(huì)消失。一般來說，這種現(xiàn)象易發(fā)生在入口、出口匝道等瓶頸處。

4 交通應(yīng)用

車輛組成的交通流實(shí)質(zhì)是一個(gè)離散系統(tǒng)，而又緊密相互聯(lián)系，導(dǎo)致復(fù)雜的交通現(xiàn)象。元胞自動(dòng)機(jī)模型是交通流模型的理論基礎(chǔ)，能夠從微觀層面分析復(fù)雜交通系統(tǒng)的研究工具。184號(hào)模型是以Wolfram命名的最基本的一維元胞自動(dòng)機(jī)模型，其中包含的基本要素能夠?qū)崿F(xiàn)一些交通現(xiàn)象的模擬，但是不能完全適應(yīng)復(fù)雜的實(shí)際交通狀況。目前交通流的元胞自動(dòng)機(jī)大致可分為兩大類：以NS模型為代表的研究高速公路的模型，以BML模型為代表的研究城市網(wǎng)絡(luò)交通的模型，這兩類模型是對(duì)184號(hào)模型的進(jìn)一步完善和發(fā)展。

4.1 NS模型

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

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

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

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

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

（4）運(yùn)動(dòng)，Xn（t+1）→Xn（t）+Vn（t+1），車輛位置更新，速度調(diào)整，繼續(xù)向前運(yùn)動(dòng)。

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

4.2 BML模型

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

4.3 NS和BML耦合模型

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

在該組合模型中，堵塞產(chǎn)生的內(nèi)因與NS模型相近，系統(tǒng)自發(fā)的堵塞現(xiàn)象與BML模型十分類似。

5 結(jié)語

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

參考文獻(xiàn)

[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，//祝玉學(xué)，趙學(xué)龍（譯）.物理系統(tǒng)的元胞自動(dòng)機(jī)模擬.北京：清華大學(xué)出版社，（2003）.

[4]謝惠民.非線性科學(xué)從書：復(fù)雜性與動(dòng)力系統(tǒng).上海：上海科技教育出版社，（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

基金項(xiàng)目：武漢市社科基金項(xiàng)目《大規(guī)模建設(shè)背景下的武漢道路擁堵區(qū)域疏散管理研究》（項(xiàng)目編號(hào)：14021）研究成果。

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