引言

現(xiàn)代社會(huì)普遍面臨嚴(yán)重的交通問(wèn)題，對(duì)交通流理論的研究可以建立能描述實(shí)際交通一般特性的交通流模型，以揭示控制交通流動(dòng)的基本規(guī)律，從而有效地進(jìn)行交通規(guī)劃、交通管理與控制以及交通能源節(jié)約等方面的研究。

傳統(tǒng)的交通流模型主要有車(chē)輛跟馳模型、流體動(dòng)力學(xué)模型、車(chē)輛排隊(duì)模型等。元胞自動(dòng)機(jī)(CA)模型是近年來(lái)發(fā)展起來(lái)的一種時(shí)間和空間都離散的動(dòng)力學(xué)系統(tǒng)模型。散布在柵格(latticegrid)中的每一個(gè)元胞都有有限個(gè)狀態(tài)，它們遵循同樣的規(guī)則作同步更新，大量元胞通過(guò)簡(jiǎn)單的相互作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的演化。

交通流元胞自動(dòng)機(jī)模型簡(jiǎn)單，易于在計(jì)算機(jī)上實(shí)現(xiàn)，并且能夠再現(xiàn)各種復(fù)雜的交通現(xiàn)象，以反映交通流特性，如平均速度、密度、流量等參數(shù)。

1交通流元胞自動(dòng)機(jī)的歷史起源

元胞自動(dòng)機(jī)的創(chuàng)始人是著名的計(jì)算機(jī)科學(xué)家VonNeumann。他在1948年模擬生命的自我復(fù)制功能時(shí)，構(gòu)造了一個(gè)由二維方形網(wǎng)格組成，由數(shù)千個(gè)基本元胞構(gòu)成的自繁殖結(jié)構(gòu)，每個(gè)元胞有29個(gè)可能的狀態(tài)［1］，演化規(guī)則依賴(lài)于每個(gè)元胞的狀態(tài)及其四個(gè)最近鄰元胞(即東南西北四個(gè)鄰居元胞)的狀態(tài)的自動(dòng)機(jī)。但限于當(dāng)時(shí)的計(jì)算機(jī)水平，沒(méi)有得到足夠的重視。隨后，到20世紀(jì)60年代，以Langton為首的一批科學(xué)家，以元胞自動(dòng)機(jī)為工具展開(kāi)了對(duì)人工生命的深入研究，通過(guò)計(jì)算機(jī)模擬來(lái)更加充分地認(rèn)識(shí)真實(shí)生命和生命形式的特性。1970年，數(shù)學(xué)家Conway提出了著名的生命游戲機(jī)(GameofLife)的概念，使元胞自動(dòng)機(jī)受到了多方面的關(guān)注。20世紀(jì)80年代，Wolfram對(duì)初等元胞自動(dòng)機(jī)進(jìn)行了廣泛深入的研究，直到今天，仍然是元胞自動(dòng)機(jī)領(lǐng)域最為重要的工作之一。

2元胞自動(dòng)機(jī)的構(gòu)成

所謂元胞自動(dòng)機(jī)是一個(gè)無(wú)窮維的離散的動(dòng)力學(xué)系統(tǒng)，主要由四部分構(gòu)成，分別是元胞、元胞空間、鄰居和演化規(guī)則［2］。其數(shù)學(xué)表達(dá)形式為：

CA=(Ld,RN,d)

Ld表示元胞空間，元胞是元胞自動(dòng)機(jī)的最基本的組成部分，元胞所分布在空間上的網(wǎng)格點(diǎn)的集合就是我們所說(shuō)的元胞空間。

d表示元胞空間的維數(shù)，目前的研究工作多集中在一維和二維元胞自動(dòng)機(jī)上，本文討論的是一維元胞自動(dòng)機(jī)。

E表示元胞的有限狀態(tài)集，某一時(shí)刻，每一個(gè)元胞都有自己的狀態(tài)，元胞的狀態(tài)根據(jù)所研究的問(wèn)題而不同，可以是(0,1)二進(jìn)制形式，也可以是(0,1，2,…)整數(shù)形式的離散集。

N表示所有元胞的鄰居的狀態(tài)集合，為包含n個(gè)不同元胞的空間矢量，表示為N=(21,???,9；,???,9?)，n是鄰居元胞個(gè)數(shù)，2,!R。

8表示元胞自動(dòng)機(jī)的演化規(guī)則，是根據(jù)元胞當(dāng)前狀態(tài)及其鄰居狀態(tài)確定下一時(shí)刻該元胞狀態(tài)的一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)。

由以上可知，元胞自動(dòng)機(jī)是由一個(gè)元胞空間和定義于該空間的狀態(tài)轉(zhuǎn)換函數(shù)所組成的。

3交通流元胞自動(dòng)機(jī)的產(chǎn)生

交通問(wèn)題中的研究對(duì)象，都是不連續(xù)的，車(chē)輛運(yùn)動(dòng)有很大的隨機(jī)性和不確定性。元胞自動(dòng)機(jī)在模擬各種具有離散性和隨機(jī)性的自然現(xiàn)象方面的應(yīng)用非常廣泛，由此啟發(fā)人們用它來(lái)模擬交通問(wèn)題叫

將元胞自動(dòng)機(jī)應(yīng)用于交通流仿真最早是受到了Wolfram184號(hào)初等元胞自動(dòng)機(jī)的啟發(fā)。隨后元胞自動(dòng)機(jī)模型在車(chē)輛交通中的應(yīng)用演化出了兩個(gè)分支:以NS模型為代表的研究高速公路交通流的模型和以BML為代表的研究城市交通網(wǎng)絡(luò)的模型。這兩個(gè)代表模型分別由Nagel和Schreckenberg在同一年提出，并且都是以Wolfram命名的184號(hào)模型為基礎(chǔ)發(fā)展而來(lái)的。

4一維單車(chē)道元胞自動(dòng)機(jī)模型

根據(jù)所研究交通特性的不同或研究角度的不同，可以提出不同的假設(shè)條件，采用不同的元胞狀態(tài)更新原則，由此形成了不同的交通元胞自動(dòng)機(jī)。本文主要介紹一維單車(chē)道元胞自動(dòng)機(jī)模型。

一維單車(chē)道模型研究車(chē)輛在一條車(chē)道上運(yùn)動(dòng)形成的交通流。其基本結(jié)構(gòu)是：將一條車(chē)道劃分為等尺寸的格點(diǎn)，每個(gè)格點(diǎn)看作一個(gè)元胞，其最多僅能有一輛車(chē)占據(jù)，每個(gè)元胞有兩種狀態(tài)——空、被車(chē)占據(jù)；對(duì)時(shí)間進(jìn)行離散化，并且等步長(zhǎng)推進(jìn)；取車(chē)輛位置、速度作為狀態(tài)變量，為有限、離散變量。在每個(gè)時(shí)刻，根據(jù)定義的規(guī)則進(jìn)行狀態(tài)更新。各模型的區(qū)別主要在于狀態(tài)更新規(guī)則，按是否包含隨機(jī)因素可分為確定性模型和隨機(jī)性模型叫整個(gè)系統(tǒng)采用周期邊界條件，以保持車(chē)輛數(shù)守恒。

4.1確定性元胞自動(dòng)機(jī)交通模型

這類(lèi)系統(tǒng)不含隨機(jī)項(xiàng)，其初始狀態(tài)給定后，系統(tǒng)的演化是完全確定的，即呈現(xiàn)一定的規(guī)律性。由Wolfram命名的184號(hào)模型就是一個(gè)確定性模型。

184號(hào)模型

該模型是最簡(jiǎn)單的元胞自動(dòng)機(jī)模型，也被稱(chēng)為初等元胞自動(dòng)機(jī)，其是狀態(tài)集只有兩個(gè)元素，鄰居半徑為1的一維元胞自動(dòng)機(jī)。此模型將道路分為L(zhǎng)個(gè)元胞，每個(gè)元胞長(zhǎng)度為1，其只有兩個(gè)狀態(tài)(0和1):0表示無(wú)車(chē)，1表示被一輛最大車(chē)速為1的車(chē)輛占據(jù)。某一元胞下一時(shí)刻的狀態(tài)是由其本身加上前后兩個(gè)元胞共三個(gè)元胞的狀態(tài)所決定的(在每一時(shí)步上，若車(chē)輛前方元胞為空，則車(chē)輛向前移動(dòng)一個(gè)元胞，否則靜止)。

根據(jù)以上規(guī)則，給出184號(hào)元胞自動(dòng)機(jī)交通流模型的速度和位置更新規(guī)則：

速度更新規(guī)則：

Vi(t)—min{ga(t-1),1}

位置更新規(guī)則：

Xi(t)—Xi(t—1)+Vi(t)

其中,Vi(t)表示第i輛車(chē)從t-1時(shí)刻到t時(shí)刻車(chē)輛運(yùn)行的速度,gs.(t—1)表示第i輛車(chē)和其前方車(chē)的距離?Xi(t)表示t時(shí)刻第i輛車(chē)的位置。速度更新規(guī)則說(shuō)明車(chē)輛速度取其前方車(chē)輛距離gs.(t—1)與1之間的最小值。位置更新規(guī)則說(shuō)明從t-1時(shí)刻到t時(shí)刻，車(chē)輛的位置從Xi(t-1)變化到Xi(tT)+Vi(t)。

從184號(hào)元胞自動(dòng)機(jī)的時(shí)空仿真圖可以看出，圖像具有十分嚴(yán)格的規(guī)律性，時(shí)空斑圖呈現(xiàn)不斷重復(fù)的形狀，這是因?yàn)?84號(hào)規(guī)則過(guò)于簡(jiǎn)單[5],整個(gè)系統(tǒng)不受隨機(jī)因素的影響。但在實(shí)際交通流中，車(chē)輛的行駛總會(huì)受到其他因素的干擾，這在184號(hào)元胞自動(dòng)機(jī)中沒(méi)有體現(xiàn)。

DFI元胞自動(dòng)機(jī)模型

FI模型出現(xiàn)了高速車(chē)(即最大車(chē)速不再是1),如果車(chē)輛與前面車(chē)的距離-1)大于最大速度Vmax，車(chē)輛將以最大速度Vmax行駛；如果小于最大速度Vmax，則車(chē)的行駛速度為—1)。

在t到t+1的過(guò)程中，DFI模型按如下規(guī)則進(jìn)行演化：速度更新規(guī)則：

Vi(t)—min{g，,(t-1),Vmax}

位置更新規(guī)則：

Xi(t)—Xi(t—1)+Vi(t)

在模型中，所有車(chē)輛都可以突然加速到最高速度。

通過(guò)改變速度更新規(guī)則,還可讓車(chē)輛逐步加速，規(guī)則改為:速度更新規(guī)則：

Vi(t)—min{Vi(t-1)+1,g“(t-1),Vmax)

位置更新規(guī)則：

Xi(t)—Xi(t—1)+Vi(t)

其中,W)表示第i輛車(chē)從t-1時(shí)刻到t時(shí)刻車(chē)輛運(yùn)行的速度,gs.(t—1)表示第i輛車(chē)和其前方車(chē)的距離?Xi(t)表示t時(shí)刻第i輛車(chē)的位置。該系統(tǒng)能再現(xiàn)自由流模式和擁擠模式。

4.2隨機(jī)性元胞自動(dòng)機(jī)交通模型

作為對(duì)184號(hào)模型和DFI模型的推廣，1992年Nagel和Schreckenberg提出了著名的NS模型。這是一個(gè)最重要的單車(chē)道模型，Nagel在確定性模型的基礎(chǔ)上加入隨機(jī)項(xiàng)。NS模型思想為：人們?cè)隈{車(chē)過(guò)程中總希望汽車(chē)能以它的最大速度行駛，并且不會(huì)與其他車(chē)輛發(fā)生碰撞，但不是所有車(chē)輛都可以以最大速度行駛，因而引入隨機(jī)慢化概率P，來(lái)模擬車(chē)輛行駛時(shí)受到干擾的情況。

在t到t+1的過(guò)程中，具體NS模型的演化規(guī)則表示為：

速度更新規(guī)則：

Vi(t)—min(v,-(t-1)+1,g“(t-1),Vmax)

隨機(jī)慢化規(guī)則：

f(t)<p&Vi(t)—max{0,Vi(t)-1}

位置更新規(guī)則：

Xi(t)—Xi(t—1)+Vi(t)其中,Vi(t)表示第i輛車(chē)從/-1時(shí)刻到t時(shí)刻車(chē)輛運(yùn)行的速度,gs.(t—1)表示第i輛車(chē)和其前方車(chē)的距離?Xi(t)表示t時(shí)刻第i輛車(chē)的位置。每一輛車(chē)將按照上述的演化步驟運(yùn)動(dòng)更新，車(chē)輛的速度和位置在一個(gè)時(shí)步內(nèi)同時(shí)更新。速度更新規(guī)則表示司機(jī)在行駛過(guò)程中的速度會(huì)盡可能大，但要保證與前車(chē)不產(chǎn)生碰撞。隨機(jī)慢化規(guī)則表示司機(jī)的差異駕駛行為[6]，這是堵塞自發(fā)形成的重要因素。

由NS模型的時(shí)空仿真圖可以看出，NS模型雖然簡(jiǎn)單,但卻能較真實(shí)地反應(yīng)出高速公路的交通流特性，如NS模型可以模擬出自發(fā)產(chǎn)生的堵塞現(xiàn)象以及擁擠交通情況下產(chǎn)生的時(shí)走時(shí)停波。但是，NS模擬的最大交通流量小于實(shí)測(cè)數(shù)據(jù)，且不能描述交通流具有亞穩(wěn)態(tài)、回滯以及同步流等復(fù)雜的交通現(xiàn)象和特征。

NS模型考慮了車(chē)輛的加速和隨機(jī)慢化情況，同時(shí)模型出現(xiàn)了高速車(chē)輛。當(dāng)Vmax=1，P=0時(shí),NS模型退化為184號(hào)模型。

5結(jié)語(yǔ)

一維單車(chē)道交通流元胞自動(dòng)機(jī)模型忽略了十字路口、交通燈和交叉口方向上車(chē)輛的影響，只考慮同一路段上同方向車(chē)輛的相互作用。這種模型適合于模擬高速公路上的交通流。交通流元胞自動(dòng)機(jī)模型具有規(guī)則簡(jiǎn)單、計(jì)算速度快的特點(diǎn),目前已成為交通微觀模擬研究的重要工具。其在描述交通流特性方面的獨(dú)特優(yōu)勢(shì)，必將會(huì)使它有非常廣闊的發(fā)展前景。

20211020_616ef68e8af4c__一維單車(chē)道交通流元胞自動(dòng)機(jī)模型綜述