随着社会经济的发展, 汽车保有量快速增加, 导致交通事故频发、交通拥堵日益严重, 显著降低了道路交通运行的可靠性。因此, 对路网交通运行可靠性进行在线分析已成为交通系统可靠性研究领域的一个新课题。

已有的交通系统可靠性分析主要包括连通可靠性、容量可靠性和行程时间可靠性^{[1, 2]}。由于这些可靠性分析都不能实时在线确定路网交通运行的可靠性水平, 因此, 难以满足动态交通管理的需要。

交通运行可靠性是指在规定的条件下和规定的时间内, 路段、路口或路网以规定的运行质量通过规定交通量的能力^[3]。路网交通运行可靠性在线分析以动态交通数据为基础, 通过实时监测可靠度指标的变化, 在线确定路网交通运行的可靠性水平以及需要重点管理的路段和路口, 通过为动态交通管理部门提供更具有针对性的决策依据, 进一步降低路网交通运行失稳状态的发生概率、减少交通拥堵的持续时间。

文献[3]在提出交通运行可靠性概念的基础上, 构建了相应的可靠度指标, 并基于最小路集法设计了交通运行可靠性在线分析方法。该文献进一步拓展了交通系统可靠性分析的范畴, 能在线确定路网交通运行可靠性的水平及敏感的路段和路口, 有效地改善了动态交通管理决策的信息基础, 但在算法效率和时效性方面还存在较大的提升空间。

为此, 本文以文献[3]提出的交通运行可靠性概念及可靠度指标为基础, 借鉴路网结构表达的邻接矩阵思想, 构建了新的路网可靠度表达和存储方法, 并基于因子定理设计了新的路网交通运行可靠性在线分析方法。最后应用仿真试验对本文方法的效果和效率进行了对比分析。

路网是由点、线相互交错组成的复杂网络, 其中, 点代表路口, 线代表路段, 如图1所示。

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 路网结构图Fig.1 Structure diagram of road network

在图论中, 网络的表达与存储主要有邻接矩阵法、邻接表法和边集数组法。文献[3]运用邻接表法对路网进行表达和存储, 其优点是便于查找任一顶点的关联边及邻接点, 不足是由于需要与逆邻接表联合使用, 致使其占用的存储空间较大, 并导致以此为基础的路网可靠性分析计算量较大、耗时较长, 对交通运行可靠性在线分析的实时性具有不利影响。

为了减少路网存储的空间占用量以及后续的路网交通运行可靠性在线分析的计算量, 本文借鉴邻接矩阵法思想, 设计了路网可靠度矩阵的概念及其表达与存储方法。

邻接矩阵法^[4]是利用二维数组 对网络进行表达和存储的方法。在邻接矩阵存储模式中, 以图中的顶点数 作为矩阵的行数和列数, 之间的连通关系。以图1所示的路网为例, 其邻接矩阵如式(1)所示。

式中:当 时, 表示路口 时, 表示连接路口 和路口 的路段。 之间有路段直接连通; 之间没有路段直接连通。 可通过; 不能通过。

以文献[3]提出的分时可靠度指标为基础, 借鉴邻接矩阵的思想, 本文定义一种可靠度矩阵, 并将其作为路网交通运行可靠度表达与存储的新方法, 其中, 路网可靠度矩阵是指运用路口和路段的分时可靠度 代替路网邻接矩阵中的 所得到的矩阵。仍以图1所示的路网为例, 其可靠度矩阵如式(2)所示。

式中: 在产品系统中, 其取值为1或0, 在路网可靠度表达中, 其取值为1和0之间的任何数。

与邻接表法相比, 可靠度矩阵占用的存储空间较小, 且能够在表征路网连通性的同时体现路段和路口的分时可靠度水平, 为进一步改善路网交通运行可靠性在线分析的效率奠定了重要基础。

文献[3]将路网交通运行可靠性分析分解为特定路径的交通运行可靠性分析、特定OD对间子路网的交通运行可靠性分析和路网整体的交通运行可靠性分析三个层次。其中, 路网整体交通运行可靠性分析的基础是路网中所有OD对间子路网交通运行可靠性分析的结果。因此, 路网交通运行可靠性分析的本质是路网中任意OD对之间的端端可靠性分析。

目前交通系统中的端端可靠性分析大多采用枚举法和容斥原理法。文献[3]采用的是枚举法, 方法比较直观, 但计算量较大; 容斥原理法易于理解, 但容易导致较大的累计误差。已有研究表明^{[5, 6]}, 常应用于机械零部件可靠性分析的因子定理法可在一定程度上克服前两种方法的不足, 快速有效实现端端可靠度计算。因此, 为了改善路网交通运行可靠性在线分析的时效性, 本文在路网交通运行可靠度矩阵表达与存储的基础上, 结合路网自身特征, 引用因子定理法设计了道路网络交通运行可靠性在线分析新算法。

设路网 对间子路网的邻接矩阵为 的可靠度矩阵为 其中 对间子路网覆盖的路口数。基于因子定理对路网 的交通运行可靠性进行在线分析的算法包括如下步骤:

Step1 在

Step2 令第 对间子路网的端端可靠度矩阵为 , 并将其写入待分解的可靠度矩阵集合

Step3 在待分解的可靠度矩阵集合 中任选一个可靠度矩阵, 令其为

Step4 在 中, 如果下列条件①②均不成立, 则转Step5; 如果条件之一成立, 则其对应子路网的可靠度为零, 转Step8:条件①: 主对角线上的第一个元素或最后一个元素为零; 条件②: 主对角线上的第一个元素和最后一个元素都不为零, 但其第一行其他元素均为零或最后一列其他元素均为零。

Step5 在 主对角线上, 除了第一个和最后一个元素外, 如果有 , 则删除 列; 如果 列其他元素均为0, 则删除 列。然后判断 的维数, 如果维数大于2, 则转Step6, 否则将其存储到基本可靠度矩阵集合 , 转Step8。

Step6 按照2.1节中的方法确定 的可行分解元, 如果不存在可行分解元, 则将 写入基本可靠度矩阵集合

Step7 按照式(4)对 完全可靠和完全不可靠时的子可靠度矩阵 和

对 和 的维数进行判断, 当其维数为2时, 将其存储到基本可靠度矩阵集合 否则将其存储到待分解的可靠度矩阵集合 其对应的系数存储到子可靠度矩阵系数集合

Step8 判断 是否为空, 如果 为空, 转Step9, 否则转Step3。

Step9 根据 和 对间子路网的可靠度

式中: 个二维或最简可靠度矩阵; 对间子路网端端可靠度矩阵分解后得到的二维子可靠度矩阵和最简可靠度矩阵的总数, 为 的系数, 等于 所有直接上层子可靠度矩阵系数的乘积。

如果 转Step2。

Step10 求当前时段 对间子路网端端可靠度的期望值, 作为整体路网的交通运行可靠度

令 转到Step1。

为了保持可比性, 本文选用与文献[3]相同的实验环境与试验数据。

(1)分时可靠度对比

以采用文献[3]的算法进行各时段路网交通运行分时可靠度估计结果为基础, 计算本文算法估计结果的相对误差

式中: 为本文算法估计的路网交通运行分时可靠度相对于文献[3]算法估计结果的相对误差; 为文献[3]算法估计的分时可靠度; 为本文算法估计的分时可靠度。

两种算法得到的试验路网分时可靠度及其相对误差如表1所示。

表1

Table 1

表1(Table 1)

表1 两种算法的分时可靠度对比表 Table 1 Comparative table of analytic effect from two algorithms 时段/s 分时可靠度 时段/s 分时可靠度 时段/s 分时可靠度 本文 算法 文献[3] 算法 相对误 差/% 本文 算法 文献[3] 算法 相对误 差/% 本文 算法 文献[3] 算法 相对误 差/% 600~900 0.96 0.95 1.05 6300~6600 0.87 0.86 1.16 12000~12300 0.65 0.64 1.56 900~1200 0.98 0.99 1.01 6600~6900 0.81 0.79 2.53 12300~12600 0.56 0.55 1.82 1200~1500 0.89 0.90 1.11 6900~7200 0.89 0.90 1.11 12600~12900 0.68 0.70 2.86 1500~1800 0.90 0.91 1.10 7200~7500 0.84 0.83 1.20 12900~13200 0.79 0.81 2.47 1800~2100 0.88 0.87 1.15 7500~7800 0.9 0.89 1.12 13200~13500 0.82 0.80 2.50 2100~2400 0.85 0.83 2.41 7800~8100 0.88 0.87 1.15 13500~13800 0.79 0.78 1.28 2400~2700 0.93 0.90 3.33 8100~8400 0.91 0.89 2.25 13800~14100 0.83 0.83 0.00 2700~3000 0.95 0.97 2.06 8400~8700 0.94 0.95 1.05 14100~14400 0.80 0.84 4.76 3000~3300 0.82 0.79 3.80 8700~9000 0.92 0.9 2.22 14400~14700 0.89 0.90 1.11 3300~3600 0.87 0.85 2.35 9000~9300 0.95 0.94 1.06 14700~15000 0.97 0.99 2.02 3600~3900 0.81 0.79 2.53 9300~9600 0.89 0.88 1.14 15000~15300 1.00 0.99 1.01 3900~4200 0.78 0.75 4.00 9600~9900 0.84 0.86 2.33 15300~15600 0.91 0.88 3.41 4200~4500 0.71 0.69 2.90 9900~10200 0.90 0.91 1.10 15600~15900 0.92 0.90 2.22 4500~4800 0.59 0.62 4.84 10200~10500 0.80 0.81 1.23 15900~16200 0.89 0.88 1.14 4800~5100 0.67 0.70 4.29 10500~10800 0.83 0.84 1.19 16200~16500 0.90 0.91 1.10 5100~5400 0.72 0.78 7.69 10800~11100 0.74 0.72 2.78 16500~16800 0.88 0.87 1.15 5400~5700 0.81 0.79 2.53 11100~11400 0.91 0.92 1.09 16800~17100 0.85 0.88 3.41 5700~6000 0.76 0.77 1.30 11400~11700 0.49 0.51 3.92 17100~17400 0.93 0.94 1.06 6000~6300 0.88 0.87 1.15 11700~12000 0.60 0.59 1.69 17400~17700 0.95 0.92 3.26

表1 两种算法的分时可靠度对比表 Table 1 Comparative table of analytic effect from two algorithms

从表1可看出, 与文献[3]的算法相比, 本文算法对路网分时可靠度估计的平均相对误差为2.1%, 最大为7.69%, 最小为0。可以认为, 本文所设计算法在进行路网交通运行可靠性在线分析时可获得与文献[3]基本一致的效果。

(2)运行时间对比

以采用文献[3]算法进行各时段路网交通运行可靠度估计的计算时间为基础, 计算本文算法计算时间的节省百分比

式中: 为本文算法相对于文献[3]算法的计算时间节省百分比; 为文献[3]算法的计算时间(s); 为本文算法的计算时间(s)。

两种算法在路网分时可靠度估计时的计算时间及本文算法计算时间的节省百分比如表2所示。

表2

Table 2

表2(Table 2)

表2 两种算法的运行时间对比表 Table 2 Comparative table of analytic efficiency from two algorithms 时段/s 运行时间/s 时段/s 运行时间/s 时段/s 运行时间/s 本文 算法 文献[3] 算法 相对误 差/% 本文 算法 文献[3] 算法 相对误 差/% 本文 算法 文献[3] 算法 相对误 差/% 600~900 0.81 10.95 92.60 6300~6600 0.56 7.21 92.23 12000~12300 0.49 5.86 91.64 900~1200 0.58 7.52 92.29 6600~6900 0.34 5.74 94.08 12300~12600 1.25 15.31 91.84 1200~1500 0.75 8.42 91.09 6900~7200 0.99 14.27 93.06 12600~12900 0.81 9.18 91.18 1500~1800 1.92 10.14 81.07 7200~7500 0.71 6.78 89.53 12900~13200 0.75 9.73 92.29 1800~2100 0.09 2.26 96.02 7500~7800 0.19 2.43 92.18 13200~13500 0.27 13.85 98.05 2100~2400 0.42 5.32 92.11 7800~8100 1.53 15.01 89.81 13500~13800 0.69 16.1 95.71 2400~2700 0.93 11.68 92.04 8100~8400 0.41 5.93 93.09 13800~14100 0.09 5.82 98.45 2700~3000 0.62 10.37 94.02 8400~8700 0.76 8.98 91.54 14100~14400 0.48 8.48 94.34 3000~3300 0.48 9.41 94.90 8700~9000 0.64 9.53 93.28 14400~14700 0.58 8.66 93.30 3300~3600 0.33 5.91 94.42 9000~9300 0.59 7.61 92.25 14700~15000 0.25 8.95 97.21 3600~3900 0.87 10.33 91.58 9300~9600 0.17 3.74 95.45 15000~15300 1.99 14.64 86.41 3900~4200 1.41 11.22 87.43 9600~9900 0.34 5.13 93.37 15300~15600 0.61 7.78 92.16 4200~4500 0.47 10.23 95.41 9900~10200 0.93 12.19 92.37 15600~15900 0.72 9.58 92.48 4500~4800 0.37 6.42 94.24 10200~10500 0.95 8.44 88.74 15900~16200 0.74 8.15 90.92 4800~5100 0.79 11.81 93.31 10500~10800 0.25 5.24 95.23 16200~16500 0.19 8.25 97.70 5100~5400 0.02 3.62 99.45 10800~11100 0.88 10.28 91.44 16500~16800 0.91 9.87 90.78 5400~5700 1.83 12.54 85.41 11100~11400 0.92 13.82 93.34 16800~17100 0.62 10.57 94.13 5700~6000 0.69 8.69 92.06 11400~11700 0.07 1.71 95.91 17100~17400 0.98 10.98 91.07 6000~6300 0.97 11.33 91.44 11700~12000 0.77 14.81 94.80 17400~17700 0.94 13.18 92.87

表2 两种算法的运行时间对比表 Table 2 Comparative table of analytic efficiency from two algorithms

由表2可看出, 与文献[3]算法相比, 本文算法运行时间的节省百分比平均为92.72%, 最大为99.45%, 最小为81.07%。可以认为, 本文方法能够显著提高路网交通运行可靠性在线分析的效率。

路网交通运行可靠性在线分析是交通系统可靠性研究领域的新课题, 对于改善动态交通管理决策的信息基础具有重要意义。针对已有成果运行效率偏低的问题, 本文借鉴邻接矩阵思想, 设计了路网可靠度表达与存储的新方法, 并设计了基于因子定理的路网交通运行可靠性在线分析方法。实证分析结果表明, 本文方法可在基本保持交通运行可靠度估计精度的同时, 显著降低在线运算的时间消耗水平, 可为进一步改善道路交通管理动态决策的及时性提供关键技术支持。