初始化對交通元胞自動機模型穩(wěn)定性的影響

鄧建華 馮煥煥 葛婷

摘要： 針對現(xiàn)有交通元胞自動機模型運行初始不穩(wěn)定，數(shù)據(jù)輸出存在較長時間的初始波動問題，基于Fisher-Yates算法原理，設(shè)計出一種新的交通流初始化方法。該方法可以確保車輛從進入元胞空間到隨后的演化更新，其位置及更新時機的隨機性。通過對采用新交通流初始化方法的模型進行演化實驗，結(jié)果表明：任意空間占有率條件下交通流的初始波動區(qū)間都在50步以內(nèi)；當演化更新總步數(shù)達到3 600步時，模型剔除初始波動區(qū)間的輸出數(shù)據(jù)已充分收斂，這時模型運行已足夠穩(wěn)定。

關(guān)鍵詞： 元胞自動機；交通流初始化；Fisher-Yates算法；初始波動區(qū)間

中圖分類號： U491.1文獻標識碼： A

收稿日期： 2021-12-01；修回日期：2022-03-18

基金項目： 國家自然科學基金（51808370）；蘇州科技大學基金項目（341311108;XKQ201305）

第一作者： 鄧建華（1972-），男，湖南永興人，碩士，副教授，主要研究方向為交通復雜系統(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 引言

元胞自動機是一類時空離散的網(wǎng)格動力學模型［12］，是交通流建模的主要工具之一。交通元胞自動機模型的元胞單元、鄰域結(jié)構(gòu)、元胞空間及演化規(guī)則一旦確定，作為人工設(shè)計的方法，交通流初始化是否合理就可能是影響模型穩(wěn)定性的主要因素。現(xiàn)有的交通流初始化方法源自于Nagel和Schreckenberg［3］1992年提出的NaSch模型。NaSch模型用一個單維的元胞單元數(shù)組構(gòu)成的元胞空間來表示一段單車道公路，并為它設(shè)計了開放性、周期性兩種邊界條件。開放性邊界設(shè)計有兩個開放端：一端為車輛駛?cè)攵耍硪欢藶轳傠x端；周期性邊界使元胞空間構(gòu)成一個兩端首尾相連的環(huán)。在此基礎(chǔ)上，NaSch模型對這兩種邊界條件提出了相應的交通流初始化方法：對于開放性邊界條件，模型首先生成一個隨機數(shù)列，該數(shù)列元素值與車輛輸入時刻相關(guān)聯(lián)，數(shù)列的大小等于輸入的車輛總數(shù)。模型演化時，車輛按照該數(shù)列的元素值所示的時刻進入元胞空間，如果駛?cè)攵说氖讉€元胞單元為空，則把車輛布置到該元胞單元，如此反復，直到所有車輛進入元胞空間，則完成了模型的交通流初始化過程。該初始化方法實現(xiàn)了車輛進入元胞空間在時間上的隨機性；對于周期性邊界條件，模型首先按照待輸入車輛總數(shù)生成一個與每輛車輸入位置相關(guān)聯(lián)的隨機數(shù)列，然后，根據(jù)該數(shù)列每位元素值所標示位置把車輛一次性布置到元胞空間，從而完成模型的交通流初始化。這時，車輛的初始位置是隨機的。NaSch模型的交通流初始化方法的原理清晰，實現(xiàn)過程簡單，是現(xiàn)有交通流元胞自動機模型交通流初始化的通用方法［4］。但是，按照上述兩種方法完成交通流初始化以后，模型還需要通過遍歷元胞空間來對所有的車輛進行狀態(tài)更新，越靠近車流下游的車輛越會優(yōu)先得到更新［45］。這種僅能確保車輛初始時刻或初始位置隨機分布的交通流初始化方法，也帶來了其它相關(guān)問題，如：元胞空間內(nèi)前導車的更新時機總會優(yōu)先于跟馳車輛，導致跟馳效應的削弱［6］。為改善這些缺陷則需增加額外的演化規(guī)則，如：隨機減速規(guī)則、隨機慢啟動規(guī)則等，才能再現(xiàn)車輛跟馳過程中的時走時停、遲滯等交通現(xiàn)象［710］。20世紀末，RICKERT等［11］提出了著名的STCA雙車道模型，隨后DAOUDIA等［12］提出了三車道模型，他們都沿用了NaSch模型的交通流初始化方法，隨后也被其它多車道元胞自動機模型沿用至今［1316］。如前述，交通流經(jīng)初始化后，車輛的演化更新需通過遍歷元胞空間來實現(xiàn)，該過程也對多車道模型中的換道行為描述產(chǎn)生不利影響，如，換道沖突事件會被忽略掉，而這種因換道產(chǎn)生的車輛沖突在現(xiàn)實多車道交通流中卻很常見［17］。綜上所述，僅能使車輛初始時刻或初始位置隨機分布的交通流初始化方法，會導致模型對車輛個體行為描述的偏差，這種偏差既會影響車輛運行狀態(tài)數(shù)據(jù)的準確性也會延緩交通流的自組織過程［18］。

基于Fisher-Yates算法［19］的基本原理，本文提出了一種新的交通流初始化方法，該方法可以確保車輛從進入元胞空間到隨后的演化更新，其位置及更新時機的隨機性，基本還原現(xiàn)實交通流中車輛運動行為的時空隨機特性，理論上也可加快交通流的自組織過程，提高模型運行的穩(wěn)定性。為進一步驗證該觀點，本文對新提出的交通流初始化方法進行較為詳細的實驗研究，并結(jié)合實驗研究所得到的初始波動區(qū)間值對模型演化更新總步數(shù)提出了建議。

1 模型的元胞空間及演化規(guī)則

1.1 模型的元胞空間

為表示本文提出的交通流初始方法具有通用性，這里選擇構(gòu)建一個多車道元胞自動機模型的元胞空間。該空間由一個二維Moore型鄰域的單位元胞數(shù)組來描述，以表示一段多車道路段。如圖1所示，假設(shè)該元胞空間由n×m元胞單元構(gòu)成，則它可表示為CA［n，m］，其中x軸表示道路縱向；y軸表示道路橫向。單位元胞橫向?qū)挾扰c車道同寬，單位元胞長度根據(jù)車輛的最大加（減）速度來設(shè)置（參見后續(xù)的實驗設(shè)計）。一輛車可能占據(jù)多個元胞單元，車輛所處的位置用其前保險杠所處的元胞單元來標識，如車輛Q［k］的位置在元胞單元CA［i，j］。這里的Q［k］為待輸入系統(tǒng)的車輛隊列Q［w］中的一個元素，k=0，…，w-1，其中w為車輛總數(shù)。

為控制設(shè)定的演化更新步數(shù)內(nèi)元胞空間中的車輛數(shù)恒定，以觀察、分析系統(tǒng)的穩(wěn)定情況，本文的元胞空間采用周期性邊界條件。

1.2 模型的演化規(guī)則

該多車道元胞自動機模型的跟馳規(guī)則采用NaSch模型的基本規(guī)則，以盡可能減少規(guī)則冗余對模型的穩(wěn)定性產(chǎn)生影響；換道規(guī)則采用文獻［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）隨機慢化，當概率p，vk（t+1）→min（vk（t）－1，0）；4）換道決策，確定換道目標；5）目標位置更新，xk（t+1）→xk+vk（t+1）。其中，dk為跟車間距；隨機慢化概率p=0.01；加（減）速度值為1單位元胞長/步2，可以表示為1cell/s2。單位“步”用“s”表示，下同。車輛更新后的速度為vk（t+1），位置為xk（t+1）。

2 基于Fisher-Yates算法原理的交通流初始化方法

模型演化更新前需要進行交通流初始化。Fisher-Yates算法［19］是一種復雜度不高的亂序算法，它可快速生成一個無偏、無重復元素的隨機數(shù)列?；贔isher-Yates算法原理，本文提出了新的交通流初始化算法，其具體描述為：

1）開始。這時模型的元胞空間CA［n，m］，邊界條件與規(guī)則已確定。

2）初始化CA［n，m］與車輛隊列Q［w］。設(shè)兩個數(shù)組的元素初始值為零。

3）創(chuàng)建臨時一維數(shù)組A［n×m］。它有n×m個元素，元素值依次為0到n×m-1。

4）把A看作一副有n×m張的撲克牌，對A進行亂序洗牌，然后開始抓牌。第k次抓到的牌值Q［x］正是車輛Q［k］將要布置在元胞空間的位置。如此反復，直到w張牌抓完、車輛布置完，表示該初始化過程結(jié)束。完整的算法流程如圖2所示。

以上以周期性邊界條件為例進行了算法描述，但該算法也適用于開放性邊界條件的交通流初始化。當元胞空間為開放性邊界條件時，算法僅需把數(shù)組A的大小設(shè)置為完成所有車輛輸入需花費的演化更新步數(shù)，其余保持不變。

按照該算法流程進行交通流初始化以后，車輛隊列Q［w］中的車輛Q［k］被隨機布置在元胞單元CA［i，j］，并設(shè)CA［i，j］=1表示有車占據(jù)。同時CA［i，j］的位置信息也被回傳給車輛Q［k］。這樣，Q［k］始終與當前所處的元胞單元形成一一映射關(guān)系。由于Q［w］的每輛車一直保留著它們在元胞空間中的當前位置信息，交通流初始化以后的車輛演化更新可通過遍歷Q［w］來實現(xiàn)，該過程使元胞空間中車輛的狀態(tài)更新與現(xiàn)實交通流中車輛的運動行為改變具有基本一致的隨機時空分布特性。這從根本上解決了遍歷元胞空間需按一定時空順序更新車輛的問題。

3 實驗設(shè)計

3.1 實驗目的與任務

模型演化更新時，車輛從交通流初始化設(shè)定的狀態(tài)瞬間改為由規(guī)則驅(qū)動，該過程必然會造成車輛行駛狀態(tài)的明顯波動?？紤]到這種波動會對研究成果產(chǎn)生潛在的影響，大多數(shù)學者采用了盡可能延長演化更新步數(shù)且僅截取演化尾端數(shù)據(jù)的做法來解決這個問題。但是，因為初始波動區(qū)間未知，學者們在設(shè)置演化更新總步數(shù)及尾端截取區(qū)間上不統(tǒng)一，常見設(shè)置的演化更新總步數(shù)為104～106 s、尾端數(shù)據(jù)截取區(qū)間為103～104 s［2123］。演化更新步數(shù)和截取區(qū)間設(shè)置不合理會造成計算資源的浪費，結(jié)合本文研究目的，把確定初始波動區(qū)間及合適的演化更新總步數(shù)作為本實驗任務。

3.2 實驗參數(shù)設(shè)置

為排除小尺度元胞空間對實驗結(jié)果產(chǎn)生潛在干擾，設(shè)元胞空間周長L=20 000個元胞，單位元胞長度設(shè)置為0.98 m，則L的實際長度為19.6 km。單位元胞橫寬為3.75 m，等于車道寬。實驗場景假設(shè)為一段三車道的城市主干路，其設(shè)計計算速度為60 km/h。道路上的車輛為單一類型的小汽車，車身長為4.9 m，相當于5個單位元胞長。

設(shè)空間占有率D表示為

D=∑wk=1lkLanes×L0

其中，lk為第k輛車的長度，Lanes為車道數(shù)。

3.3 實驗過程

某D值條件下，完成設(shè)定演化更新步數(shù)的演化過程稱為一次實驗。將D值區(qū)間劃分為20等份，同一演化更新步數(shù)的20等份的D值所對應的20次實驗構(gòu)成一組實驗。實驗過程總體上按組進行，第1組演化更新步數(shù)最短，設(shè)為600 s。必要時可按每600 s遞增重新做一組實驗，如第2組實驗可設(shè)演化更新步數(shù)為1 200 s重新進行實驗。每做一組實驗，都可進行初始波動區(qū)間的觀察和輸出數(shù)據(jù)的收斂情況分析。

輸出數(shù)據(jù)的收斂判定，采用公式（2）：

1－ε

其中，ε為收斂閾值，設(shè)ε=5%。f、f+1分別表示前一組、當前組實驗； i為各空間占有率等分值所對應的序號，即i=0，…，19；則afi、af+1i分別為前一組、當前組相應D值點對應的數(shù)據(jù)值。

按照上述實驗設(shè)計，先確定初始波動區(qū)間，再確定合適的演化更新步數(shù)。在確定合適的演化更新步數(shù)時，把初始波動區(qū)間輸出的數(shù)據(jù)剔除，這樣的研究分析結(jié)果會更準確，數(shù)據(jù)收斂更快。

4 實驗結(jié)果與討論

4.1 初始波動區(qū)間分析

按照實驗設(shè)計，首先需要通過觀察20個不同D值下輸出的時斑圖，分析確定初始波動的區(qū)間范圍。限于篇幅，在不影響觀察規(guī)律的情況下，這里僅等距列出了5個D值的時斑圖，如圖3所示。時斑圖中：豎軸t表示演化更新步數(shù)，輸出范圍t=0～100 s；橫軸x表示車輛行駛的距離，輸出范圍x=0～200 cells。圖3中間部分黑色斜線表示車輛的行駛軌跡，處于波動區(qū)間的車輛軌跡會交叉形成局部聚集不均勻黑斑和空出的白斑，在圖3的右上角用EI標識了能觀察到的波動區(qū)間范圍。從圖3中可看出：D≤0.1或D≥0.9時車輛的初始波動很難觀察到，這應該與低占有率情況下的車輛處于不受其它車輛干擾的自由行駛狀態(tài)及高占有率情況下的車輛處于其它車輛嚴格約束的全阻塞狀態(tài)有關(guān)；波動較明顯的D值區(qū)間在D=0.3～0.7，且EI范圍都不超過50 s，遠小于目前大部分研究所設(shè)定的剔除范圍［2123］。

4.2 模型穩(wěn)定性分析與合適的演化更新總步數(shù)

按照前述的實驗設(shè)計，重新從600 s開始進行分組實驗，每次數(shù)據(jù)統(tǒng)計先剔除EI=50 s區(qū)間的輸出數(shù)據(jù)，并繪制“速度-D圖”與“流率-D圖”，分別見圖4和圖5。從圖4，5可以看出：曲線在D=0.4～0.8區(qū)間仍存在一些波動，當初始波動排除之后，該部分波動可以理解為模型演化過程中車輛受模型規(guī)則驅(qū)動的自組織過程。當演化更新總步數(shù)達到3 600 s時，曲線與前一組（2 400 s）曲線已基本重合。把這兩組曲線的數(shù)據(jù)按照公式（2）列于表1中進行判定，發(fā)現(xiàn)：流率曲線最大實際ε=2.99%，速度曲線最大實際ε=3.63%，都在5%以內(nèi)，說明這時的模型輸出已充分收斂，模型運行已相當穩(wěn)定。

5 結(jié)論

本文提出了一種交通元胞自動機模型交通流初始化的新方法，該方法可以確保車輛從進入元胞空間到隨后的演化更新，其位置及更新時機的隨機性，較已有交通流初始化方法能更好地還原現(xiàn)實交通流中車輛行進過程中行為的隨機時空分布特性。對模型進行反復演化實驗，發(fā)現(xiàn)新方法的初始化過程加快了交通流的自組織過程：交通流的初始波動區(qū)間都在50 s以內(nèi)；當演化更新總步數(shù)達3 600 s時，模型輸出的數(shù)據(jù)已充分收斂，表明這時模型的演化更新已相當穩(wěn)定。本文實驗研究所獲得的初始波動區(qū)間及模型演化更新總步數(shù)可供相關(guā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］賈斌， 高自友， 李克平， 等. 基于元胞自動機的交通系統(tǒng)建模與模擬 ［M］. 北京： 科學出版社， 2007：70-97.

［5］譚惠麗， 劉慕仁， 孔令江. 開放邊界條件下改進的Nagel-Schreckenberg交通流模型的研究 ［J］. 物理學報， 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］. 物理學報， 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］. 交通運輸系統(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］. 交通運輸系統(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］. 物理學報， 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］ 馮煥煥， 鄧建華， 葛婷. 引入駕駛風格的熵權(quán)法多屬性換道決策模型 ［J］. 交通運輸系統(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.

（責任編輯 耿金花）