基于博弈论的高速公路网络关键路段识别方法＊

安 实 张 涛 张昕明 王 健

（哈尔滨工业大学交通科学与工程学院 哈尔滨150001）

0 引 言

高速公路网络是交通运输业的重要组成部分，是区域联系及社会活动能够有效维持的物质基础。但自然灾害、重特大交通事故、交通拥堵等突发事件，往往会导致重要路段的失效，进而影响整个路网的交通运输功能。高速公路网络安全正逐渐成为研究热点［1－2］。因此，关键路段识别技术，有利于保障高速公路网络结构的重要功能，提高高速公路网络结构的可靠性，科学管理高速公路网络。

关键路段是指“移除后对路网性能影响最大的路段”［3］。Wollmer［4］首先定义了最重要弧，当最重要弧被移除后，产生了最大的损失。Corley和Sha［5］将网络上的最重要路段或节点定义为移除后将会导致2点间的最短路程显著增加的路段或节点。Ball等［6］随后将此问题定义为权重网络的最重要弧问题。Scott等［7］运用高速系统弹性和可靠性来识别关键路段，评价网络性能。Nagurney和 Qiang［8］捕捉了路网的需求、流量、成本和行为，并可用于路网组成部分的重要性。Sullivan等［9］将改进的方法用到不同路段的能力干扰数值中，列出了最重要的路段。目前对路网中关键路段识别的方法可以分为3类：

1）基于仿真的方法。在每一路段的通行能力都有所降低，即路网降级的条件下解决交通分配问题。Jenelius［10］通过总结受交通量影响的失效路段内外最小行程时间的不同，识别网络的关键路段。虽然这种迭代方法能够完整分析网络，但需要耗费大量的时间，尤其在路网规模较大的情况下，更是如此。

2）根据一定的选择标准，如路线功能、技术等级和交通量等，找出能够迅速评估路网水平的候选路段，随后对候选路段进行细节分析。Taylor和D′Este［11］应用网络搜索的概念评价路网被干扰的后果。第1步是识别候选关键路段，这些路段要么是最短路径上的一部分，要么是起讫点之间较高使用率的多个路段。第2步是将每一候选路段依次关闭，评估失效后果。此方法与第1种方法相比，能够缩减候选路段，提高计算效率。但是，潜在缺点是对关键路段的分级不够准确。

3）根据博弈论寻找关键路段。Bell和Murray-Tuite［12］构造了网络破坏者的主体，试图将路段降级，以最大化路网总行驶时间，而行驶者却寻找特定路径以最小化预期时间。根据博弈论，关键路段很可能被降级或者受到破坏者的干扰［13］。与第1种方法相似，在每一路段关闭时，都对新的平衡条件依次评估。因此，这种方法对于大规模路网很费时间。

笔者基于博弈论框架，变被动识别为主动分析，对高速公路网络的关键路段进行评估，引入信息熵来表征路段被攻击信息的平均不确定度，结合用户均衡分配，构造了能够有效应用于实际高速公路网络的关键路段识别方法。

1 交通管理者和网络攻击者博弈模型

记高速公路网络为有向图G＝（N，I）。其中：N为网络中的节点集合，I为网络中的路段集合。如图1所示，博弈双方分别为交通管理者和网络攻击者，交通管理者指高速公路交通管理部门，网络攻击者为高速公路网络威胁事件的抽象主体。博弈双方的目的分别是通过实施相应的路径分配策略或路段失效策略，增加或降低整个网络的考虑失效风险的总出行费用V。当某一博弈过程中系统的带有失效风险的总出行费用值V的变化量小于给定的收敛阈值ε时，则博弈过程终止，系统达到纳什均衡状态。此时交通管理者的交通分配策略与网络攻击者的路网攻击策略均可达最优。

图1 高速公路网络中的博弈模型Fig.1 Game model in freeway network

博弈结束时，输出的网络攻击者的各路段失效概率的排序，即为网络中关键路段识别的标准；交通管理者的交通流量分配策略，则包含了交通管理者为降低路网脆弱性所能够实施的相应的交通管理规划或交通设施改善的最优方案。

表1为相关符号的定义。交通管理者和网络攻击者之间的博弈目标可以用极大极小准则来表示。

目标函数（1）中，网络考虑失效风险的总出行费用V的值是由每个路段的考虑失效风险的出行费用累加求和得到的，与交通管理者的路段流量分配比例γ和网络攻击者的路段失效概率ρ有关，在该博弈框架中，1个路段同时具有2个属性，即交通管理者在交通分配时将该路段作为可选路段的概率和网络攻击者在攻击路网时选择该路段失效的概率。交通管理者的目标是通过交通分配策略使网络的考虑失效风险的总出行费用最小，而网络攻击者的目标是通过选择一些路段使其失效而使网络的考虑失效风险的总出行费用最大。

对式（2）进行一些基本的约束，即高速公路网络中的所有路段被交通管理者所分配的流量比例累加和应该为1，且被网络攻击者失效的概率累加和也为1，并且每个路段的γ和ρ的取值都为非负。

然而，交通管理者问题和网络攻击者问题仍然比较复杂。目标函数是基于路段累加的形式来表示的，实际上基于路径的方法能够更加真实的反应网络上的流量传播及分配情形，但很难以路径的形式进行表示。为简化模型及计算过程，本文仍以路段为基本单元表示目标函数。但是为了更真实的反映网络流量沿路径传播的情形，在交通管理者进行决策求解的问题中，以路径为基本对象，体现流量沿路径传播的现实。而对于网络攻击者的决策仍以路段为单元，但由于其选择路段失效概率会相应的参考交通管理者的决策方案，所以也包含了路径方面的考虑。

表1 符号定义Tab.1 Notation index

2 博弈双方的策略集

2.1 交通管理者决策过程

基于Wardrop平衡原理的交通分配的数学规划模型为：

2.2 网络破坏者决策过程

为了计算网络攻击者对路网中各路段的失效概率，本文将网络攻击者的路段失效策略看作1种包含信息量，引入信息熵的概念，来表征信息源在发出信息前的平均不确定度，则由信息熵的概念，的熵函数为的熵函数赋权值，引入加权熵函数，这一权值不仅在一定程度上体现了网路攻击者的理性程度，而且还使网络攻击者对于路段失效概率有显式解。引入加权熵函数后，当θ≠0时，原问题的修正目标函数如下：

同时，由于约束条件的存在，即所有的路段失效的概率应该收敛于1，故定义1个收敛于1的数列，即

将上式除号上下2项乘以e，则有：

通过上面的分析，最终的等式（13）描述了当交通管理者更新其交通分配策略时，网络攻击者做出的相应的对策。本文称参数θ为网络攻击者对于交通管理者策略的反应强度。当θ变大时，网络中路段失效策略的不确定度会随之变小，也就是说网络攻击者对于网络攻击的确定性越强，对交通分配方案的反应强度大，将集中攻击网络中的一小部分路段，这些路段即为所谓的关键路段，对于网络功能的维持具有重要的作用，此时网络攻击者的攻击性越强；反之，当θ变小时，网络攻击者攻击路段的不确定度变大，对于这些关键路段的攻击性则变弱，路段失效概率在网络中就越分散，此时网络攻击者的攻击性越弱。

当θ为0时，网络攻击者攻击网络的不确定度变得无效大，即对于网络中各个路段的损坏的概率是相等的，即1／｜I｜。实质上，参数θ一定程度上体现了网络攻击者的理性程度。

3 算法基本流程

流程的基本输入数据为路网基本数据，可分为3个部分：网络拓扑结构、OD需求和自由流行程时间。在网络的初始化阶段，设定ε的值，并设定，i∈I。路段失效状态函数会基于路段行程时间和初值设置参数，计算路段在失效状态下的费用。该步骤的计算结果将作为计算路段加权失效费用的输入信息。此外，加权失效路段费用函数还需要上1个博弈过程中的路段失效信息，并应用连续平均法来计算路段历史费用信息；计算结果将与路网拓扑结构和OD需求一起作为输入数据，实现交通管理者的用户均衡分配。

由于假设网络攻击者和交通管理者具有完全信息，网络攻击者直接收集交通管理者的用户均衡交通分配中的路段流量分配比例信息，根据交通管理者和加权熵函数来确定攻击策略。网络攻击者策略的输出是路段被攻击概率，交通管理者策略的输出是流量分配比例，以及路段费用加权失效费用共同输入到网络考虑失效风险的总出行费用函数中，当网络考虑失效风险的总出行费用收敛于给定的判别条件时，博弈终止，输出关键路段排序数据。算法基本流程如下：

步骤1。网络初始化。

步骤4。进行用户均衡交通分配。

步骤6。计算网络的考虑失效风险的总出行费用，Vn（γ，ρ）。

步骤7。若Vn（γ，ρ）－Vn－1（γ，ρ）＜ε，结束；否则，返回步骤1。

4 算例分析

黑龙江省高速公路全长4 084km，是全国为数不多高速公路超过4 000km的省份之一。共有149个网络节点（收费站），179个路段，服务区68对。以哈同高速、哈双高速、哈绥高速、哈大高速、鹤大高速等为骨干，连接省内各主要城市及地区。道路多为双向4车道，中央均设置分隔带。正常路段小客车最高限速120km／h、大客车100km／h、货车80km／h，特殊受限路段（连续弯道、隧道、桥梁等）限速相应降低。

黑龙江省高速公路网络拓扑结构如图2所示。

图2 黑龙江省高速公路网络图Fig.2 Freeway network of Heilongjiang province

黑龙江省高速公路的联网收费数据，记录了车辆进入路网和驶出路网的位置及时间，也就是路网中的每个节点都是1个交通需求点，既是起始点也是目的地。关键路段识别结果见表2（只列出前15个路段）。

根据表2的计算结果，对θ值变化时的关键路段的失效概率及路段流量分配比例进行分析。如图3（a）所示，随着θ的值由1增加到10，网络攻击者使排序在前几位的关键路段的失效概率随θ值的增大而增大，由于受到约束条件 ∑eEρe＝1的限制，则排序名次靠后的路段的失效概率相应有所减少，也就是路段失效的概率逐渐集中到一小部分路段上，当θ＝10时，网络攻击者的基本上只是使极少部分路段失效。即随着θ的增大，路段失效概率在路网中分配趋向于集中某些路段上。也就是θ的值越大，网络攻击者对于关键路段的攻击性越强，从而相应制定重点攻击最为关键的一些路段的策略。

表2 流量分配比例及被攻击概率Tab.2 Use probability and failure probability

图3 路段失效策略及流量分配策略在路网中的分配Fig.3 Distribution of link failure and link using strategy

而对于各路段流量分配比例，则恰恰相反，如图3（b）所示，当θ值较小时，由于网络攻击者的失效策略在网络中分配较为均匀，且各路段失效概率都不太大，所以交通管理者能够更为可靠的使用路网中的最短路径，从而使路径的分配主要集中在某些重要道路上，同样由于 ∑eEγi＝1的限制，其他道路的流量分配比例则较小；而随着θ的增大，网络攻击者对于关键路段，也就是最短路径较为集中的路段的攻击性变强，使其失效概率增大，这时交通管理者将相应的对路径分配进行调整，将其流量分流到其他路段，从而使得路网中路段的流量分配比例的分配则趋于均匀，这正是博弈的结果。然而，无论θ取值的大小如何，一些被攻击概率大的路段的结果基本一致，即θ的取值只影响网络攻击者的攻击策略分布范围，也可以说是集中程度，而不会影响关键路段的识别结果。关键路段识别结果见图4（θ＝5）

图4 关键路段识别结果Fig.3 Results of critical link identification

图4 的识别结果中，106号路段为哈同高速宾县段，该路段不仅是事故多发路段，而且交通需求较高，车流量大；97，98号路段为哈同高速依兰段，该路段同样为事故多发路段，冬季雪大且易结冰，且夏季雨水多，发生过雨水淹没道路的情况；同样，26，27，28号道路，哈牡高速亚布力段，冬季道路容易结冰，而且道路线形多连续弯路；12，14号路段分别为哈双高速瓦盆窑段及拉林河段，16号路段为哈阿高速，这几处均为车流量较大路段，而且连接省会城市哈尔滨及与其联系紧密的双城市及阿城区，交通需求大，同时根据高速公路收费数据可以看出，哈双高速拉林河段，即14号道路大货车混入率较高，交通流组成混杂。可以看出识别结果与实际情况基本一致。

5 结束语

高速公路网络关键路段的识别对于网络的正常运营及交通安全具有重要意义。现有的关键路段识别方法或计算量巨大、或识别效率不高，不能很好的应用于实际的道路网络。基于博弈论的思想，将关键路段的识别方法变被动为主动，构造了网络攻击者的行为主体，建立了攻防博弈模型。攻击者以加权熵函数为决策依据，防守者以用户均衡交通分配为决策依据，当博弈达到均衡时，既能够输出网络的关键路段排序，又能给出相应的交通分配方案。实践证明，该方法能够有效地识别网络中的关键路段。

交通需求是关键路段识别中的重要标准，除此之外，交通网络中的交通事故数据、气象数据等对于突发事件的发生也有明显的影响。利用高速公路网络运营过程中的多源数据来更为全面地分析网络的关键路段及节点，是今后研究的重要方向。

［1］ 王俊骅，赵新勇，丛浩哲.高速公路网突发交通事件时空影响预测模型［J］.交通信息与安全.2013，31（1）：77-82.WANG Junhua，ZHAO Xinyong，CONG Haozhe.Prediction model of freeway network traffic incident space-time effect［J］.Journal of Transport Information and Safety.2013，31（1）：77-82.（in Chinese）

［2］ 李斌，张纪升，袁 宇，等.国家高速公路安全和服务技术开发与工程应用示范综述［J］.交通信息与安全.2013，31（1）：19-23.LI Bin，ZHANG Jisheng，YUAN Yu，et al.Review of National Freeway Safety and Service Technology Development and Demonstration［J］.Journal of Transport Information and Safety.2013，31（1）：19-23.（in Chinese）

［3］ UKKUSURI S V，YUSHIMITO W F.A methodology to assess the criticality of highway transportation networks［J］.Journal of Transportation Security，2009，2（12）：29-46.

［4］ WOLLMER R.Removing arcs from a network［J］.Operations Research，1964，12（6）：934-940.

［5］ CORLEY H W，SHA D Y.Most vital links and nodes in weighted networks［J］.Operations Research Letters，1982，1（4）：157-160.

［6］ ADEVA B，ADRIANI O，Aguilar-Benitez M，et al.A determination of the properties of the neutral intermediate vector boson［J］.Physics Letters B，1989，231（4）：509-518.

［7］ SCOTT D M，NOVAK D C，AULTMANl-Hall L，et al.Network robustness index：a new method for identifying critical links and evaluating the performance of transportation networks［J］.Journal of Transport Geography，2006，14（3）：215-227.

［8］ NAGURNEY A，QIANG Q.A network efficiency measure with application to critical infrastructure networks［J］.Journal of Global Optimization，2008，40（1-3）：261-275.

［9］ SULLIVAN J L，NOVAK D C，AULTMAN-Hall L，et al.Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links：a link-based capacityreduction approach［J］.Transportation Research Part A：Policy and Practice，2010，44（5）：323-336.

［10］ JENELIUS E，PETERSEN T，MATTSSON L G.Importance and exposure in road network vulnerability analysis［J］.Transportation Research Part A：Policy and Practice，2006，40（7）：537-560.

［11］ TAYLOR M A P，D′ESTE G M.Transport network vulnerability：a method for diagnosis of critical locations in transport infrastructure systems［M］.Heidelberg：Springer Berlin：2007.

［12］ BELL M G H.A game theory approach to measuring the performance reliability of transport networks［J］.Transportation Research Part B：Methodological，2000，34（6）：533-545.

［13］ MURRAY-TUITE P M，MAHMASSANI H S.Methodology for determining vulnerable links in a transportation network［J］.Transportation Research Record：Journal of the Transportation Research Board，2004，1882（1）：88-96.