基于元胞自动机的动态路段走行时间计算模型＊

王红霖 焦朋朋 孙文博

（1.北京建筑大学北京市城市交通基础设施建设工程技术研究中心 北京100044；2.航天长征化学工程股份有限公司 北京101111）

0 引 言

作为系统解决城市交通问题的重要手段之一，智能交通系统（intelligent transportation system，ITS）是建立在正确分析交通流实时以及未来分布形态的基础之上，这一分析需要建立城市动态交通网络分析模型，而动态路段走行时间函数是其重要组成部分。

在动态交通网络中，由于引入了时间维度，动态OD、路段流量、路段走行时间等都是时间序列变量，在这种情况下，必须建立适用于动态交通网络分析的动态路段走行时间函数。然而，到目前为止，国内外的学者们还没有找到1种动态路段走行时间函数的合适形式。如果不讨论其细节，动态路段走行时间函数一般被认为是路段的自由流行程时间加上在路段的下游节点处由于交通拥挤而产生的延误时间之和。动态路段走行时间最早出现在动态交通分配模型中，Merchant和Nemhauser［1］在对动态系统最优化（DSO）问题建模时，认为路段驶出率是关于路段交通量的比例函数，进而提出了离散型的动态路段走行时间模型；Wie等［2］假设路段驶出率函数与路段交通量负荷有关，同M-N模型具有高度的一致性；Daganzo［3］根据前人对动态交通分配模型的研究，认为每个时刻进入路段的车辆行程时间与该路段的交通状态相关，而路段的交通状态与路段的驶入率、驶出率和交通量相关，据此建立了动态路段走行时间函数的一般形式；在一般形式的基础之上，Kuwahara和 Akamatsu［4］在 对 动 态 用 户 最 优（DUO）问题建模时，将路段中车辆看作点，认为路段中节点前方的车辆排队长度为0，采用了点排队模型建立了动态路段走形时间函数；袁振洲［5］根据车流波动理论，提出基于车流集散波理论确定交叉口前车辆长度的方法，可称为车流集散波法；而宋志勇［6］认为忽略路段中的车辆排队长度是不合理的，考虑了路段中车辆的长度建立了有度排队的车辆走行时间模型。Daganzo［7－8］提出了交通流元胞传输模型（cell transmission model，CTM），该模型重现了著名的LWR模型（Lighthill和 Whitham［9］以及 Richard［10］）的一些重要特征，可以清楚地描述排队的物理效应以及一些交通流动力学特性，对描述波动较大的交通流特性有相当优势。Ziliaskopoulos［11］提出的动态系统最优的动态交通分配模型中，在交通流的元胞传输模型基础上求解动态路段走形时间。

相比于以往成果，笔者研究的重点是利用元胞自动机NaSch模型来描述动态路段交通流，并在此基础上建立动态路段走行时间模型。在这一模型中，时间、空间、速度都被整数离散化，路段被划分为离散的元胞，随着元胞划分数量的增加，路段交通流的微观描述就更加细致［12］，模型求解精度就更加良好。

1 元胞自动机交通流模型

元胞自动机（cellular automata，CA）是1种时空离散的局部动力学模型，是研究复杂系统的1种典型方法，特别适合用于空间复杂系统的时空动态模拟研究［13］。Nagel和Schreckenberg在元胞自动机第184号规则的基础上提出了一维交通流 CA 模型［14］。

在NaSch模型中时间步长一般取1s，道路被划分为L个元胞，每辆车长度为l个元胞，速度取｛0，1，…，vmax｝ ，每个元胞的状态或者是空的，或者被车辆车占据。用车辆的速度vn和位置xn表示第n辆车的状态，令dn＝xn＋1－xn表示第n辆车与前车之间的空的元胞数。该模型在1个时间步长t→t＋1过程中，按照如下规则进行演化更新。

1）车辆加速过程。若vn＜vmax，则vn→min（vn＋1，vmax）。

2）车辆减速过程。若dn≤vn，则vn→min（vn，dn－1）。

3）车辆随机慢化过程（以随机概率p慢化）。vn→ max（vn－1，0）。

4）车辆位置更新。xn→xn＋vn。

除了更新方式外，要完成模型的数值模拟还必须确定边界条件，NaSch模型的边界条件为：

1）周期性边界条件。在每次更新结束后，我们要检测道路上头车的位置，那么这辆车将从道路的另一端进入系统，变为道路上的尾车。

2）开口边界条件。在t→t＋1时刻，在道路上的车辆更新完成后，检测道路上的头车和尾车的位置xlead和xlast。若果xlast＞vmax，则车速为vmax的车辆将以概率α进入元胞min［xlast－vmax，vmax］［15］。在道路的出口处，如果xlead＞Lroad，那么道路上的头车以概率β驶出路段，而紧跟其后的第二辆车成为新的头车。

2 动态路段走行时间计算模型

图1 累积车辆数曲线Fig.1 Cumulative arrival and departure curves

已知初始路段车辆到达率以及路段上车辆数后，经过元胞自动机系统演化，可以得到累积驶入车辆数曲线和累积驶出车辆数曲线（见图1），进而得到关于车辆进入路段时刻的走行时间函数。yi（t），累积流入车辆数为Yi（t），路段最后1个元胞的单位流出流量为yo（t），累积流出量为Yo（t），初始路段上的车辆数为x（0），由图1可见，当Yi（t）＝Yot＋τ（）（）t时，τ（）t即为时刻t进入路段的车辆的走行时间。

NaSch模型的时间维度是离散的，累积车辆数曲线是1条离散点连接成的曲线，因此，以一定的时间步长Δt为基点，路段走行时间计算方法如下。

车辆在第k个时段进入路段，此时，累积流入车辆数为Yi（k），如果在k＋m个时段第k个时段进入路段的车辆全部流出，即累积流出车辆数Y0（k＋m）＝Yi（k），则第k个时段进入路段的车辆的走行时间为：mΔt

如果累积流入车辆数与累计流出车辆数存在这样的关系：Yi（t）＞Yo（t＋mΔt）且Yi（t）＜Yo（t＋ （m ＋1）Δt），那么路段的行程时间为：

通过上述方法计算出的路段走行时间函数，可以计算出任意时刻进入路段车辆的走行时间。由以上模型可知，当路段有车辆进出时，模型可以准确计算出该车辆的走行时间；当没有车辆进出时，模型无法计算出路段走行时间函数。这就是说，模型的精度随路段车流量的增减而增减，路段走行时间是关于车辆进入路段时间的函数，对应的是车辆个体，这一点恰好满足了对于路段走行时间函数的需求。

3 模型求解及数值分析

3.1 模型求解

在Matlab平台上设计了基于元胞自动机NaSch模型的单车道交通流仿真程序。仿真系统由主程序及路段车辆位置初始化器、路段车辆速度初始化器、前方车辆查询器、首车查询器、尾车查询器、首车更新器、随机慢化器、驶入车辆及驶出车辆生成器等子函数组成。输出内容包括车辆行驶轨迹的时空分布图、累积驶入驶出车辆函数图、以及关于车辆驶入时刻的走行时间与车流量、平均车速之间的关系。求解程序流程图见图2。

3.2 数值分析

根据实际情况，设计1个长度为150个元胞的路段，允许最大行驶速度为每个单位时间间隔3个元胞。驶入车辆按泊松分布到达，每个单位时间间隔到达率为0.25，驶出车辆每周期按概率0.9离开路段，路段初始车辆数为20辆。

图2 求解程序流程图Fig.2 Flow diagram of solution

3.2.1 车辆运动时空图

路段每单位间隔更新车辆位置，程序将记录下每个时刻的车辆位置，最终形成时间－位置矩阵，进而得到车辆时空图［16］，见图3。

图3 车辆运动时空图Fig.3 Space-time diagram of vehicles movement

图3 显示了本次仿真的车辆运动时空图，图中纵轴为时间轴，方向自上而下，横轴为位移轴，方向自左而右。该图反映出了本次仿真中的实际交通状况，从图中可以清晰地看出，路段交通流发生了多次自发性拥堵。特别是图片居中靠下部分1条自上而下的1条拥堵带，十分明显（图中方框部分）。这个拥堵对于后面车辆产生回滞波，使得排队不断后移，使下游交通受到了较大的影响。以上现象与现实交通流运行状况相吻合，说明本次次仿真实验具有较大可信度。但在实际情况中可能存在一些突发状况，比如交通事故、恶劣天气等，在这些状况下可能会存在仿真结果与现实状况相差较大。

3.2.2 累积驶入、驶出车辆函数

根据模型求解中设计的程序可知，车辆按一定概率驶入路段，当车辆进入路段时，计数器开始记录累积驶入车辆，同样出口计数器也记录了累积驶出车辆数。

根据出入口计数器的数据得到了如图4所示的车辆累积驶入、驶出函数曲线。图中纵轴表示累积车辆数，横轴代表时间，实线表示累积驶入车辆函数曲线，点划线表示累积驶出车辆函数曲线。

图4 累积驶入、驶出车辆函数Fig.4 Cumulative arrival and departure functions

由图4可见，驶入和驶出车辆函数曲线的纵向距离随时间的变化，体现出路段车流量的变化。通过分析还能得出路段车辆的分布状态，若驶入车辆曲线变陡，驶出车辆曲线变缓则说明车辆集中分布在上游入口处，而相反则表示是车辆分布在下游出口处。若驶入驶出车辆曲线同向变化，仅表示路段车流量的增减。

图4中驶入车辆曲线较为平稳，变化不大，相比之下，驶出车辆曲线却有较大的增减幅度变化，这说明车辆在路段内发生了自发性拥挤排队及消散，但上图中曲线不能够反映出一些突发事故导致的路段驶入驶出车辆的突变。

3.2.3 路段走行时间函数

根据本文建立的动态路段走行时间计算模型，得到了设计路段的动态走行时间函数曲线图，见图5。

由于数值分析只采用了1段单车道的路段，没有涉及到交叉口，所以仿真结果不受交叉口信号配时的影响。因此，由图5可见，路段走行时间函数与车辆驶入路段时刻没有明显的关联。车辆由于路段随机的自发性拥堵导致延误，而自发性拥堵不仅与车流量、速度、密度相关，更与车辆的随机慢化相关，这表明自发性拥堵导致的延误有一定的随机性，当车辆驶入路段时遇到自发性拥堵，则走行时间变长；反之，则变短。

图5 动态路段走行时间函数图Fig.5 Dynamic link travel time functions

另一方面，从图中还可以看出每个走行时间的峰值对应的左侧曲线比右侧曲线更陡，这说明，该点对应车辆随机慢化引起了拥堵，进而导致后续车辆走行时间急剧变长，然后车辆消散，车辆走行时间逐渐变小。

3.2.4 路段走行时间函数与车流量关系

根据交通流守恒关系，已知累积驶入、驶出车辆函数，初始路段交通量，即容易得到各个时刻的车流量，进而通过车流量和路段走行时间关于时间的一一对应，绘出图6所示的散点图。

图6 动态路段走行时间与车流量关系图Fig.6 Relationship between dynamic link travel time and traffic flow

在静态BPR函数中，行程时间是路段流量的单调递增函数，而在动态走行时间的仿真中可以发现，二者并没有太多联系。实际上，在动态交通网络中，影响路段行程时间的因素中，流量只是1个次要因素，根据动态交通分析中交通流的先进先出规则，车辆进入路段时刻路段以后的交通状态是1个主要因素，而路段中的交通状态是根据NaSch交通流传播模型得到的。举例来说，车辆在进入路段时，车流量并不一定非常小，但仍可以保证以较快速度有序行驶，因此走行时间较短；当车辆进入路段中下游时，车辆通常因为随机慢化、减速换道等因素形成自发性拥堵排队，或由下游信号灯导致的周期性排队，这时尽管车流量可能很小，但走行时间仍然可能很长。

3.2.5 路段走行时间函数与区间平均车速关系

程序中每单位间隔更新车辆位置、速度，程序将记录下每个时刻的车辆速度，根据区间平均车速定义求出各时刻的路段区间平均车速，进而通过区间平均车速和路段走行时间关于时间的一一对应，绘出如图7所示的散点图。

图7 动态路段走行时间与区间平均车速关系图Fig.7 Relationship between dynamic link travel time and average link speed

对于静态的路段走行时间函数而言，其走行时间函数就等于路段长度除以路段区间平均车速。而从图7中可以发现，此次模拟的交通流区间平均车速主要分布在1.6～2.2之间，不属于自由流。路段走行时间和路段区间平均车速对应的点，均匀分布在图中的各个位置，路段走行时间与路段区间平均车速无明显的关联。

实际上，动态交通网络中的路段走行时间随不同时刻路段交通状态而变化，反映在走行时间模型中为路段驶入、驶出车流量的变化。路段区间平均车速不等于某一单独的平均行驶速度，因此也就无法准确描绘出各时刻车辆的路段走行时间。

4 结束语

通过对动态交通网络中交通流的传播模型进行研究，利用元胞自动机NaSch交通流模型，建立了动态路段走行时间计算模型，并在Matlab平台上基于元胞自动机NaSch模型设计了单车道交通流仿真程序进行了数值分析。

交通流仿真程序输出了车辆行驶轨迹的时空分布图，能够很好地重现众多实际交通现象，准确清晰的显示出交通流波动状态，表明NaSch交通流模型能够很好地为动态交通网络分析提供路网交通流传播模式。

根据累积驶入驶出车辆函数图可知交通流状态在路网中时时发生变化，结合路网交通流传播的FIFO规则及累积驶入、驶出车辆函数能够得到各时刻进入路段车辆的走行时间，比静态交通规划中的路段走行时间更为复杂；由路段走行时间与车流量和区间平均车速之间的关系图可知，由于没有考虑到路段交通状态的实时变化，任何静态的交通参数，如车流量，区间平均车速等，都不能准确适当的反映实际的动态路段走行时间的变化。

［1］ MERCHANT D K，Nemhauser G L.A model and an algorithm for the dynamic traffic assignment problems［J］.Transportation Science，1978，23（12）：183-199.

［2］ WIE B W.Dynamic analysis of user optimized network flows with elastic travel demand［J］.Transportation Research Record No.1328：Travel Demand Forecasting，1991（1328）：81-87.

［3］ DAGANZO C F.Properties of link travel time functions under dynamic loads［J］.Transport Research Part B，1995，29B（2）：95-98.

［4］ KUWAHARA M，AKAMATSU T.Decomposition of the reactive dynamic assignments with queues for a many-to-many origin-destination pattern ［J］.Transportation Research Part B：Methodological，1997，31（1）：1-10.

［5］ 袁振洲.动态交通分配中道路阻抗模型的研究［J］.中国公路学报，2002，15（3），92-95.YUAN Zhenzhou.Study of link travel time functions for dynamic traffic assignment model based on computer simulation［J］.China Journal of Highway and Transport，2002，15（3）：92-95.（in Chinese）

［6］ 宋志勇.交通网络动态路阻模型研究［D］.长沙：湖南大学，2004.SONG Zhiyong.A study on dynamic link impedance function of transportation network［D］.Changsa：Hunan University，2004.（in Chinese）

［7］ DAGANZO C F.The cell transmission model：A dynamic representation of highway traffic consistent with the hydrodynamic theory［J］.Transportation Research Part B：Methodological，1994，28（4）：269-287.

［8］ DAGANZO C F.The cell transmission model，part II：network traffic［J］.Transportation Research Part B：Methodological，1995，29（2）：79-93.

［9］ LIGHTHILL M J，WHITHAM G B.On kinematic waves.II.A theory of traffic flow on long crowded roads［J］.Proceedings of the Royal Society of London.Series A.Mathematical and Physical Sciences，1955，229（1178）：317-345.

［10］ RICHARDS P I.Shock waves on the highway［J］.Operations Research，1956，4（2）：42-51.

［11］ ZILIASKOPOULOS A K.A linear programming model for the single destination system optimum dynamic trafc assignment problem［J］.Transportation Science，2000，34，37-49.

［12］ 贾 斌，高自友.基于元胞自动机的交通系统建模与模拟［M］.北京：科学出版社，2007.JIA Bin，GAO Ziyou et al.Models and simulations of traffic system based on the theory of cellular automata［M］.Beijing：Science Press，2007.（in Chinese）

［13］ CHOPARD B，DROZ M.Cellular automata modeling of physical systems［M］.Cambridge：Cambridge University Press，1998.

［14］ NAGEL K，SCHRECKENBERG M.A cellular au-tomaton model for freeway traffic［J］.Journal de Physique I，1992，2（12）：2221-2229.

［15］ 李兵强，钟诚文.基于安全效应的双车道元胞自动机交通流模型研究［J］.交通与计算机，2007，25（3）：27-30.LI Bingqiang，ZHONG Chengwen et al.A two-iane cellular automata traffic flow model based on safety effect［J］.Computer and Communications，2007，25（3）：27-30.（in Chinese）

［16］ 温惠英，罗 军.基于CA的短时交通事件干扰下的交通流仿真［J］.交通信息与安全，2012，30（4）：80-84.WEN Huiying，LUO Jun.CA-based simulation of traffic flow under the disturbance of short-term traffic incident［J］.Journal of Transport Information and Safety，2012，30（4）：80-84.（in Chinese）