鄧建華 馮煥煥 葛婷
摘要: 針對現(xiàn)有交通元胞自動機(jī)模型運(yùn)行初始不穩(wěn)定,數(shù)據(jù)輸出存在較長時(shí)間的初始波動問題,基于Fisher-Yates算法原理,設(shè)計(jì)出一種新的交通流初始化方法。該方法可以確保車輛從進(jìn)入元胞空間到隨后的演化更新,其位置及更新時(shí)機(jī)的隨機(jī)性。通過對采用新交通流初始化方法的模型進(jìn)行演化實(shí)驗(yàn),結(jié)果表明:任意空間占有率條件下交通流的初始波動區(qū)間都在50步以內(nèi);當(dāng)演化更新總步數(shù)達(dá)到3 600步時(shí),模型剔除初始波動區(qū)間的輸出數(shù)據(jù)已充分收斂,這時(shí)模型運(yùn)行已足夠穩(wěn)定。
關(guān)鍵詞: 元胞自動機(jī);交通流初始化;Fisher-Yates算法;初始波動區(qū)間
中圖分類號: U491.1文獻(xiàn)標(biāo)識碼: A
收稿日期: 2021-12-01;修回日期:2022-03-18
基金項(xiàng)目: 國家自然科學(xué)基金(51808370);蘇州科技大學(xué)基金項(xiàng)目(341311108;XKQ201305)
第一作者: 鄧建華(1972-),男,湖南永興人,碩士,副教授,主要研究方向?yàn)榻煌◤?fù)雜系統(tǒng)仿真。
Influence of the Initialization Method on the Stability of Traffic Cellular Automata Model
DENG Jianhua, FENG Huanhuan, GE Ting
(College of Civil Engineering, Suzhou University of Science and Technology, Suzhou 215011,China)
Abstract:Aiming at the initial instability of the existing traffic cellular automata model and the initial fluctuation of data output for a long time, a new traffic flow initialization method is designed based on the principle of Fisher-Yates algorithm. This method can ensure the randomness of the location and update timing of the vehicle from entering the cell space to the subsequent evolution and update. Through the evolution experiment of the model using the new traffic flow initialization method, the results show that the initial fluctuation range is within 50 steps under the condition of arbitrary space occupancy; When the evolution update reaches 3600 steps, the output data of the model after excluding the output of the initial fluctuation interval has converged enough, and the operation of the model is stable enough.
Key words: cellular automata; traffic flow initialization; Fisher-Yates algorithm; initial fluctuation range
0 引言
元胞自動機(jī)是一類時(shí)空離散的網(wǎng)格動力學(xué)模型[12],是交通流建模的主要工具之一。交通元胞自動機(jī)模型的元胞單元、鄰域結(jié)構(gòu)、元胞空間及演化規(guī)則一旦確定,作為人工設(shè)計(jì)的方法,交通流初始化是否合理就可能是影響模型穩(wěn)定性的主要因素?,F(xiàn)有的交通流初始化方法源自于Nagel和Schreckenberg[3]1992年提出的NaSch模型。NaSch模型用一個(gè)單維的元胞單元數(shù)組構(gòu)成的元胞空間來表示一段單車道公路,并為它設(shè)計(jì)了開放性、周期性兩種邊界條件。開放性邊界設(shè)計(jì)有兩個(gè)開放端:一端為車輛駛?cè)攵耍硪欢藶轳傠x端;周期性邊界使元胞空間構(gòu)成一個(gè)兩端首尾相連的環(huán)。在此基礎(chǔ)上,NaSch模型對這兩種邊界條件提出了相應(yīng)的交通流初始化方法:對于開放性邊界條件,模型首先生成一個(gè)隨機(jī)數(shù)列,該數(shù)列元素值與車輛輸入時(shí)刻相關(guān)聯(lián),數(shù)列的大小等于輸入的車輛總數(shù)。模型演化時(shí),車輛按照該數(shù)列的元素值所示的時(shí)刻進(jìn)入元胞空間,如果駛?cè)攵说氖讉€(gè)元胞單元為空,則把車輛布置到該元胞單元,如此反復(fù),直到所有車輛進(jìn)入元胞空間,則完成了模型的交通流初始化過程。該初始化方法實(shí)現(xiàn)了車輛進(jìn)入元胞空間在時(shí)間上的隨機(jī)性;對于周期性邊界條件,模型首先按照待輸入車輛總數(shù)生成一個(gè)與每輛車輸入位置相關(guān)聯(lián)的隨機(jī)數(shù)列,然后,根據(jù)該數(shù)列每位元素值所標(biāo)示位置把車輛一次性布置到元胞空間,從而完成模型的交通流初始化。這時(shí),車輛的初始位置是隨機(jī)的。NaSch模型的交通流初始化方法的原理清晰,實(shí)現(xiàn)過程簡單,是現(xiàn)有交通流元胞自動機(jī)模型交通流初始化的通用方法[4]。但是,按照上述兩種方法完成交通流初始化以后,模型還需要通過遍歷元胞空間來對所有的車輛進(jìn)行狀態(tài)更新,越靠近車流下游的車輛越會優(yōu)先得到更新[45]。這種僅能確保車輛初始時(shí)刻或初始位置隨機(jī)分布的交通流初始化方法,也帶來了其它相關(guān)問題,如:元胞空間內(nèi)前導(dǎo)車的更新時(shí)機(jī)總會優(yōu)先于跟馳車輛,導(dǎo)致跟馳效應(yīng)的削弱[6]。為改善這些缺陷則需增加額外的演化規(guī)則,如:隨機(jī)減速規(guī)則、隨機(jī)慢啟動規(guī)則等,才能再現(xiàn)車輛跟馳過程中的時(shí)走時(shí)停、遲滯等交通現(xiàn)象[710]。20世紀(jì)末,RICKERT等[11]提出了著名的STCA雙車道模型,隨后DAOUDIA等[12]提出了三車道模型,他們都沿用了NaSch模型的交通流初始化方法,隨后也被其它多車道元胞自動機(jī)模型沿用至今[1316]。如前述,交通流經(jīng)初始化后,車輛的演化更新需通過遍歷元胞空間來實(shí)現(xiàn),該過程也對多車道模型中的換道行為描述產(chǎn)生不利影響,如,換道沖突事件會被忽略掉,而這種因換道產(chǎn)生的車輛沖突在現(xiàn)實(shí)多車道交通流中卻很常見[17]。綜上所述,僅能使車輛初始時(shí)刻或初始位置隨機(jī)分布的交通流初始化方法,會導(dǎo)致模型對車輛個(gè)體行為描述的偏差,這種偏差既會影響車輛運(yùn)行狀態(tài)數(shù)據(jù)的準(zhǔn)確性也會延緩交通流的自組織過程[18]。
基于Fisher-Yates算法[19]的基本原理,本文提出了一種新的交通流初始化方法,該方法可以確保車輛從進(jìn)入元胞空間到隨后的演化更新,其位置及更新時(shí)機(jī)的隨機(jī)性,基本還原現(xiàn)實(shí)交通流中車輛運(yùn)動行為的時(shí)空隨機(jī)特性,理論上也可加快交通流的自組織過程,提高模型運(yùn)行的穩(wěn)定性。為進(jìn)一步驗(yàn)證該觀點(diǎn),本文對新提出的交通流初始化方法進(jìn)行較為詳細(xì)的實(shí)驗(yàn)研究,并結(jié)合實(shí)驗(yàn)研究所得到的初始波動區(qū)間值對模型演化更新總步數(shù)提出了建議。
1 模型的元胞空間及演化規(guī)則
1.1 模型的元胞空間
為表示本文提出的交通流初始方法具有通用性,這里選擇構(gòu)建一個(gè)多車道元胞自動機(jī)模型的元胞空間。該空間由一個(gè)二維Moore型鄰域的單位元胞數(shù)組來描述,以表示一段多車道路段。如圖1所示,假設(shè)該元胞空間由n×m元胞單元構(gòu)成,則它可表示為CA[n,m],其中x軸表示道路縱向;y軸表示道路橫向。單位元胞橫向?qū)挾扰c車道同寬,單位元胞長度根據(jù)車輛的最大加(減)速度來設(shè)置(參見后續(xù)的實(shí)驗(yàn)設(shè)計(jì))。一輛車可能占據(jù)多個(gè)元胞單元,車輛所處的位置用其前保險(xiǎn)杠所處的元胞單元來標(biāo)識,如車輛Q[k]的位置在元胞單元CA[i,j]。這里的Q[k]為待輸入系統(tǒng)的車輛隊(duì)列Q[w]中的一個(gè)元素,k=0,…,w-1,其中w為車輛總數(shù)。
為控制設(shè)定的演化更新步數(shù)內(nèi)元胞空間中的車輛數(shù)恒定,以觀察、分析系統(tǒng)的穩(wěn)定情況,本文的元胞空間采用周期性邊界條件。
1.2 模型的演化規(guī)則
該多車道元胞自動機(jī)模型的跟馳規(guī)則采用NaSch模型的基本規(guī)則,以盡可能減少規(guī)則冗余對模型的穩(wěn)定性產(chǎn)生影響;換道規(guī)則采用文獻(xiàn)[20]提出的可以處理換道沖突的換道決策模型。設(shè)元胞空間CA[i,j]單元上的車輛Q[k]從t→t+1演化更新一步的具體演化規(guī)則為:1)加速,vk(t+1)→min(vk(t)+1,vmax);2)確定性減速,vk(t+1)→min(vk(t),dk);3)隨機(jī)慢化,當(dāng)概率p,vk(t+1)→min(vk(t)-1,0);4)換道決策,確定換道目標(biāo);5)目標(biāo)位置更新,xk(t+1)→xk+vk(t+1)。其中,dk為跟車間距;隨機(jī)慢化概率p=0.01;加(減)速度值為1單位元胞長/步2,可以表示為1cell/s2。單位“步”用“s”表示,下同。車輛更新后的速度為vk(t+1),位置為xk(t+1)。
2 基于Fisher-Yates算法原理的交通流初始化方法
模型演化更新前需要進(jìn)行交通流初始化。Fisher-Yates算法[19]是一種復(fù)雜度不高的亂序算法,它可快速生成一個(gè)無偏、無重復(fù)元素的隨機(jī)數(shù)列?;贔isher-Yates算法原理,本文提出了新的交通流初始化算法,其具體描述為:
1)開始。這時(shí)模型的元胞空間CA[n,m],邊界條件與規(guī)則已確定。
2)初始化CA[n,m]與車輛隊(duì)列Q[w]。設(shè)兩個(gè)數(shù)組的元素初始值為零。
3)創(chuàng)建臨時(shí)一維數(shù)組A[n×m]。它有n×m個(gè)元素,元素值依次為0到n×m-1。
4)把A看作一副有n×m張的撲克牌,對A進(jìn)行亂序洗牌,然后開始抓牌。第k次抓到的牌值Q[x]正是車輛Q[k]將要布置在元胞空間的位置。如此反復(fù),直到w張牌抓完、車輛布置完,表示該初始化過程結(jié)束。完整的算法流程如圖2所示。
以上以周期性邊界條件為例進(jìn)行了算法描述,但該算法也適用于開放性邊界條件的交通流初始化。當(dāng)元胞空間為開放性邊界條件時(shí),算法僅需把數(shù)組A的大小設(shè)置為完成所有車輛輸入需花費(fèi)的演化更新步數(shù),其余保持不變。
按照該算法流程進(jìn)行交通流初始化以后,車輛隊(duì)列Q[w]中的車輛Q[k]被隨機(jī)布置在元胞單元CA[i,j],并設(shè)CA[i,j]=1表示有車占據(jù)。同時(shí)CA[i,j]的位置信息也被回傳給車輛Q[k]。這樣,Q[k]始終與當(dāng)前所處的元胞單元形成一一映射關(guān)系。由于Q[w]的每輛車一直保留著它們在元胞空間中的當(dāng)前位置信息,交通流初始化以后的車輛演化更新可通過遍歷Q[w]來實(shí)現(xiàn),該過程使元胞空間中車輛的狀態(tài)更新與現(xiàn)實(shí)交通流中車輛的運(yùn)動行為改變具有基本一致的隨機(jī)時(shí)空分布特性。這從根本上解決了遍歷元胞空間需按一定時(shí)空順序更新車輛的問題。
3 實(shí)驗(yàn)設(shè)計(jì)
3.1 實(shí)驗(yàn)?zāi)康呐c任務(wù)
模型演化更新時(shí),車輛從交通流初始化設(shè)定的狀態(tài)瞬間改為由規(guī)則驅(qū)動,該過程必然會造成車輛行駛狀態(tài)的明顯波動??紤]到這種波動會對研究成果產(chǎn)生潛在的影響,大多數(shù)學(xué)者采用了盡可能延長演化更新步數(shù)且僅截取演化尾端數(shù)據(jù)的做法來解決這個(gè)問題。但是,因?yàn)槌跏疾▌訁^(qū)間未知,學(xué)者們在設(shè)置演化更新總步數(shù)及尾端截取區(qū)間上不統(tǒng)一,常見設(shè)置的演化更新總步數(shù)為104~106 s、尾端數(shù)據(jù)截取區(qū)間為103~104 s[2123]。演化更新步數(shù)和截取區(qū)間設(shè)置不合理會造成計(jì)算資源的浪費(fèi),結(jié)合本文研究目的,把確定初始波動區(qū)間及合適的演化更新總步數(shù)作為本實(shí)驗(yàn)任務(wù)。
3.2 實(shí)驗(yàn)參數(shù)設(shè)置
為排除小尺度元胞空間對實(shí)驗(yàn)結(jié)果產(chǎn)生潛在干擾,設(shè)元胞空間周長L=20 000個(gè)元胞,單位元胞長度設(shè)置為0.98 m,則L的實(shí)際長度為19.6 km。單位元胞橫寬為3.75 m,等于車道寬。實(shí)驗(yàn)場景假設(shè)為一段三車道的城市主干路,其設(shè)計(jì)計(jì)算速度為60 km/h。道路上的車輛為單一類型的小汽車,車身長為4.9 m,相當(dāng)于5個(gè)單位元胞長。
設(shè)空間占有率D表示為
D=∑wk=1lkLanes×L0 其中,lk為第k輛車的長度,Lanes為車道數(shù)。 3.3 實(shí)驗(yàn)過程 某D值條件下,完成設(shè)定演化更新步數(shù)的演化過程稱為一次實(shí)驗(yàn)。將D值區(qū)間劃分為20等份,同一演化更新步數(shù)的20等份的D值所對應(yīng)的20次實(shí)驗(yàn)構(gòu)成一組實(shí)驗(yàn)。實(shí)驗(yàn)過程總體上按組進(jìn)行,第1組演化更新步數(shù)最短,設(shè)為600 s。必要時(shí)可按每600 s遞增重新做一組實(shí)驗(yàn),如第2組實(shí)驗(yàn)可設(shè)演化更新步數(shù)為1 200 s重新進(jìn)行實(shí)驗(yàn)。每做一組實(shí)驗(yàn),都可進(jìn)行初始波動區(qū)間的觀察和輸出數(shù)據(jù)的收斂情況分析。 輸出數(shù)據(jù)的收斂判定,采用公式(2): 1-ε 其中,ε為收斂閾值,設(shè)ε=5%。f、f+1分別表示前一組、當(dāng)前組實(shí)驗(yàn); i為各空間占有率等分值所對應(yīng)的序號,即i=0,…,19;則afi、af+1i分別為前一組、當(dāng)前組相應(yīng)D值點(diǎn)對應(yīng)的數(shù)據(jù)值。 按照上述實(shí)驗(yàn)設(shè)計(jì),先確定初始波動區(qū)間,再確定合適的演化更新步數(shù)。在確定合適的演化更新步數(shù)時(shí),把初始波動區(qū)間輸出的數(shù)據(jù)剔除,這樣的研究分析結(jié)果會更準(zhǔn)確,數(shù)據(jù)收斂更快。 4 實(shí)驗(yàn)結(jié)果與討論 4.1 初始波動區(qū)間分析 按照實(shí)驗(yàn)設(shè)計(jì),首先需要通過觀察20個(gè)不同D值下輸出的時(shí)斑圖,分析確定初始波動的區(qū)間范圍。限于篇幅,在不影響觀察規(guī)律的情況下,這里僅等距列出了5個(gè)D值的時(shí)斑圖,如圖3所示。時(shí)斑圖中:豎軸t表示演化更新步數(shù),輸出范圍t=0~100 s;橫軸x表示車輛行駛的距離,輸出范圍x=0~200 cells。圖3中間部分黑色斜線表示車輛的行駛軌跡,處于波動區(qū)間的車輛軌跡會交叉形成局部聚集不均勻黑斑和空出的白斑,在圖3的右上角用EI標(biāo)識了能觀察到的波動區(qū)間范圍。從圖3中可看出:D≤0.1或D≥0.9時(shí)車輛的初始波動很難觀察到,這應(yīng)該與低占有率情況下的車輛處于不受其它車輛干擾的自由行駛狀態(tài)及高占有率情況下的車輛處于其它車輛嚴(yán)格約束的全阻塞狀態(tài)有關(guān);波動較明顯的D值區(qū)間在D=0.3~0.7,且EI范圍都不超過50 s,遠(yuǎn)小于目前大部分研究所設(shè)定的剔除范圍[2123]。 4.2 模型穩(wěn)定性分析與合適的演化更新總步數(shù) 按照前述的實(shí)驗(yàn)設(shè)計(jì),重新從600 s開始進(jìn)行分組實(shí)驗(yàn),每次數(shù)據(jù)統(tǒng)計(jì)先剔除EI=50 s區(qū)間的輸出數(shù)據(jù),并繪制“速度-D圖”與“流率-D圖”,分別見圖4和圖5。從圖4,5可以看出:曲線在D=0.4~0.8區(qū)間仍存在一些波動,當(dāng)初始波動排除之后,該部分波動可以理解為模型演化過程中車輛受模型規(guī)則驅(qū)動的自組織過程。當(dāng)演化更新總步數(shù)達(dá)到3 600 s時(shí),曲線與前一組(2 400 s)曲線已基本重合。把這兩組曲線的數(shù)據(jù)按照公式(2)列于表1中進(jìn)行判定,發(fā)現(xiàn):流率曲線最大實(shí)際ε=2.99%,速度曲線最大實(shí)際ε=3.63%,都在5%以內(nèi),說明這時(shí)的模型輸出已充分收斂,模型運(yùn)行已相當(dāng)穩(wěn)定。 5 結(jié)論 本文提出了一種交通元胞自動機(jī)模型交通流初始化的新方法,該方法可以確保車輛從進(jìn)入元胞空間到隨后的演化更新,其位置及更新時(shí)機(jī)的隨機(jī)性,較已有交通流初始化方法能更好地還原現(xiàn)實(shí)交通流中車輛行進(jìn)過程中行為的隨機(jī)時(shí)空分布特性。對模型進(jìn)行反復(fù)演化實(shí)驗(yàn),發(fā)現(xiàn)新方法的初始化過程加快了交通流的自組織過程:交通流的初始波動區(qū)間都在50 s以內(nèi);當(dāng)演化更新總步數(shù)達(dá)3 600 s時(shí),模型輸出的數(shù)據(jù)已充分收斂,表明這時(shí)模型的演化更新已相當(dāng)穩(wěn)定。本文實(shí)驗(yàn)研究所獲得的初始波動區(qū)間及模型演化更新總步數(shù)可供相關(guān)研究參考。 參考文獻(xiàn): [1]FOURRATE K, LOULIDI M. Disordered cellular automaton traffic flow model: phase separated state, density waves and self organized criticality [J]. Eur Phys J B, 2006, 49(2): 239-246. [2]NASHINARI K, FUKV M, SCHADSCHNEIDER A.? A stochastic cellular automaton model for traffic flow with multiple metastable states[J]. Journal of Physics A: Mathematical and General, 2004, 37(9): 3101-3110. [3]NAGEL K, SCHRECKENBERG M. A cellular automaton model for freeway traffic [J]. Journal De Physique I, 1992, 2(12): 2221-2229. [4]賈斌, 高自友, 李克平, 等. 基于元胞自動機(jī)的交通系統(tǒng)建模與模擬 [M]. 北京: 科學(xué)出版社, 2007:70-97. [5]譚惠麗, 劉慕仁, 孔令江. 開放邊界條件下改進(jìn)的Nagel-Schreckenberg交通流模型的研究 [J]. 物理學(xué)報(bào), 2002, 51(12): 2713-2718. TAN H L, LIU M R, KONG L J. A study on an improved nagel-schreckenberg traffic flow model with open boundary conditions [J]. Acta Phys Sin, 2002, 51(12): 2713-2718. [6]TIAN J F, JIA B, LI X G, et al. A new car-following model considering velocity anticipation [J]. Chinese Physics B, 2010, 19(1): 197-203. [7]NAGATANI T. Clustering of cars in cellular-automaton model of freeway traffic [J]. J Phys Soc Jpn, 1993, 62(11): 3837-3840. [8]EMMERICH H, RANK E. An improved cellular automaton model for traffic flow simulation [J]. Physica A, 1997, 234(3/4): 676-686. [9]DONG L Y, XUE Y, DAI S Q. One-dimensional cellular automaton model of traffic flow based on car-following idea [J]. Appl Math Mech-Engl, 2002, 23(4): 363-370. [10] LI L, YU X, DAI S Q. One-dimensional sensitive driving cellular automaton model for traffic flow [J]. Acta Physica Sinica, 2003, 52(9): 2121-2126. [11] RICKERT M, NAGEL K, SCHRECKENBERG M, et al. Two lane traffic simulations using cellular automata [J]. Physica A, 1996, 231(4): 534-550. [12] DAOUDIA A K, MOUSSA N. Numerical simulations of a three-lane traffic model using cellular automata [J]. Chinese J Phys, 2003, 41(6): 671-681. [13] KUKIDA S, TANIMOTO J, HAGISHIMA A. Analysis of the influence of lane changing on traffic-flow dynamics based on the cellular automaton model [J]. International Journal of Modern Physics C, 2011, 22(3): 271-281. [14] 敬明, 鄧衛(wèi), 王昊, 等. 基于跟車行為的雙車道交通流元胞自動機(jī)模型 [J]. 物理學(xué)報(bào), 2012, 61(24): 244502. JING M, DENG W, WANG H, et al. Two-lane cellular automaton traffic model based on car following behavior [J]. Acta Phys Sin, 2012, 61(24): 244502. [15] ZHENG Z D. Recent developments and research needs in modeling lane changing [J]. Transportation Research Part B-Methodological, 2014, 60(13): 16-32. [16] LI H X, SHAO C F, WU H L, et al. Cellular automata approach for modeling lane changing execution [J]. J Cell Autom, 2016, 11(4): 339-350. [17] 鄧建華, 馮煥煥, 葛婷. 多車道元胞自動機(jī)換道決策模型的沖突處理策略 [J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2019, 19(4): 50-54. DENG J H, FENG H H, GE T. Conflict handling strategies of lane-changing decision model of multi-lane cellular automata [J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(4): 50-54. [18] WOLFRAM S. Universality and complexity in cellular automata [J]. Physica D: Nonlinear Phenomena, 1984, 10(1): 1-35. [19] PRODINGER H. On the analysis of an algorithm to generate a random cyclic permutation [J]. Ars Combinatoria, 2002, 65(1): 75-78. [20] DENG J H, FENG H H. A multilane cellular automaton multi-attribute lane-changing decision model [J]. Physica A: Statistical Mechanics and its Applications, 2019, 529: 121545. [21] 邱小平, 于丹, 孫若曉, 等. 基于安全距離的元胞自動機(jī)交通流模型研究 [J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2015, 15(2): 54-60. QIU X P, YU D, SUN R X, et al. Cellular automata model based on safety distance [J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(2): 54-60. [22] 梁經(jīng)韻, 張莉莉, 欒悉道, 等. 多路段元胞自動機(jī)交通流模型 [J]. 物理學(xué)報(bào), 2017, 66(19): 194501. LIANG J Y, ZHANG L L, LUAN X D, et al. Multi-section cellular automata model of traffic flow [J]. Acta Phys Sin, 2017, 66(19): 194501. [23] 馮煥煥, 鄧建華, 葛婷. 引入駕駛風(fēng)格的熵權(quán)法多屬性換道決策模型 [J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2020, 20(2): 139-144. FENG H H, DENG J H, GE T. Multi-attributes lane-changing decision model based on entropy weight with driving styles [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(2): 139-144. (責(zé)任編輯 耿金花)