初始化對交通元胞自動機模型穩定性的影響

鄧建華 馮煥煥 葛婷

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

關鍵詞： 元胞自動機；交通流初始化；Fisher-Yates算法；初始波動區間

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

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

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

第一作者： 鄧建華（1972-），男，湖南永興人，碩士，副教授，主要研究方向為交通復雜系統仿真。

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 引言

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

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

1 模型的元胞空間及演化規則

1.1 模型的元胞空間

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

為控制設定的演化更新步數內元胞空間中的車輛數恒定，以觀察、分析系統的穩定情況，本文的元胞空間采用周期性邊界條件。

1.2 模型的演化規則

該多車道元胞自動機模型的跟馳規則采用NaSch模型的基本規則，以盡可能減少規則冗余對模型的穩定性產生影響；換道規則采用文獻［20］提出的可以處理換道沖突的換道決策模型。設元胞空間CA［i，j］單元上的車輛Q［k］從t→t+1演化更新一步的具體演化規則為：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］是一種復雜度不高的亂序算法，它可快速生成一個無偏、無重復元素的隨機數列?；贔isher-Yates算法原理，本文提出了新的交通流初始化算法，其具體描述為：

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

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

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

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

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

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

3 實驗設計

3.1 實驗目的與任務

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

3.2 實驗參數設置

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

設空間占有率D表示為

D=∑wk=1lkLanes×L0

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

3.3 實驗過程

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

輸出數據的收斂判定，采用公式（2）：

1－ε

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

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

4 實驗結果與討論

4.1 初始波動區間分析

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

4.2 模型穩定性分析與合適的演化更新總步數

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

5 結論

本文提出了一種交通元胞自動機模型交通流初始化的新方法，該方法可以確保車輛從進入元胞空間到隨后的演化更新，其位置及更新時機的隨機性，較已有交通流初始化方法能更好地還原現實交通流中車輛行進過程中行為的隨機時空分布特性。對模型進行反復演化實驗，發現新方法的初始化過程加快了交通流的自組織過程：交通流的初始波動區間都在50 s以內；當演化更新總步數達3 600 s時，模型輸出的數據已充分收斂，表明這時模型的演化更新已相當穩定。本文實驗研究所獲得的初始波動區間及模型演化更新總步數可供相關研究參考。

參考文獻：

［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］賈斌， 高自友， 李克平， 等. 基于元胞自動機的交通系統建模與模擬 ［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］ 敬明， 鄧衛， 王昊， 等. 基于跟車行為的雙車道交通流元胞自動機模型 ［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］. 交通運輸系統工程與信息， 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］. 交通運輸系統工程與信息， 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］. 物理學報， 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］ 馮煥煥， 鄧建華， 葛婷. 引入駕駛風格的熵權法多屬性換道決策模型 ［J］. 交通運輸系統工程與信息， 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.

（責任編輯 耿金花）