基于博弈論的高速公路網(wǎng)絡關(guān)鍵路段識別方法＊

安 實 張 濤 張昕明 王 健

（哈爾濱工業(yè)大學交通科學與工程學院 哈爾濱150001）

0 引 言

高速公路網(wǎng)絡是交通運輸業(yè)的重要組成部分，是區(qū)域聯(lián)系及社會活動能夠有效維持的物質(zhì)基礎。但自然災害、重特大交通事故、交通擁堵等突發(fā)事件，往往會導致重要路段的失效，進而影響整個路網(wǎng)的交通運輸功能。高速公路網(wǎng)絡安全正逐漸成為研究熱點［1－2］。因此，關(guān)鍵路段識別技術(shù)，有利于保障高速公路網(wǎng)絡結(jié)構(gòu)的重要功能，提高高速公路網(wǎng)絡結(jié)構(gòu)的可靠性，科學管理高速公路網(wǎng)絡。

關(guān)鍵路段是指“移除后對路網(wǎng)性能影響最大的路段”［3］。Wollmer［4］首先定義了最重要弧，當最重要弧被移除后，產(chǎn)生了最大的損失。Corley和Sha［5］將網(wǎng)絡上的最重要路段或節(jié)點定義為移除后將會導致2點間的最短路程顯著增加的路段或節(jié)點。Ball等［6］隨后將此問題定義為權(quán)重網(wǎng)絡的最重要弧問題。Scott等［7］運用高速系統(tǒng)彈性和可靠性來識別關(guān)鍵路段，評價網(wǎng)絡性能。Nagurney和 Qiang［8］捕捉了路網(wǎng)的需求、流量、成本和行為，并可用于路網(wǎng)組成部分的重要性。Sullivan等［9］將改進的方法用到不同路段的能力干擾數(shù)值中，列出了最重要的路段。目前對路網(wǎng)中關(guān)鍵路段識別的方法可以分為3類：

1）基于仿真的方法。在每一路段的通行能力都有所降低，即路網(wǎng)降級的條件下解決交通分配問題。Jenelius［10］通過總結(jié)受交通量影響的失效路段內(nèi)外最小行程時間的不同，識別網(wǎng)絡的關(guān)鍵路段。雖然這種迭代方法能夠完整分析網(wǎng)絡，但需要耗費大量的時間，尤其在路網(wǎng)規(guī)模較大的情況下，更是如此。

2）根據(jù)一定的選擇標準，如路線功能、技術(shù)等級和交通量等，找出能夠迅速評估路網(wǎng)水平的候選路段，隨后對候選路段進行細節(jié)分析。Taylor和D′Este［11］應用網(wǎng)絡搜索的概念評價路網(wǎng)被干擾的后果。第1步是識別候選關(guān)鍵路段，這些路段要么是最短路徑上的一部分，要么是起訖點之間較高使用率的多個路段。第2步是將每一候選路段依次關(guān)閉，評估失效后果。此方法與第1種方法相比，能夠縮減候選路段，提高計算效率。但是，潛在缺點是對關(guān)鍵路段的分級不夠準確。

3）根據(jù)博弈論尋找關(guān)鍵路段。Bell和Murray-Tuite［12］構(gòu)造了網(wǎng)絡破壞者的主體，試圖將路段降級，以最大化路網(wǎng)總行駛時間，而行駛者卻尋找特定路徑以最小化預期時間。根據(jù)博弈論，關(guān)鍵路段很可能被降級或者受到破壞者的干擾［13］。與第1種方法相似，在每一路段關(guān)閉時，都對新的平衡條件依次評估。因此，這種方法對于大規(guī)模路網(wǎng)很費時間。

筆者基于博弈論框架，變被動識別為主動分析，對高速公路網(wǎng)絡的關(guān)鍵路段進行評估，引入信息熵來表征路段被攻擊信息的平均不確定度，結(jié)合用戶均衡分配，構(gòu)造了能夠有效應用于實際高速公路網(wǎng)絡的關(guān)鍵路段識別方法。

1 交通管理者和網(wǎng)絡攻擊者博弈模型

記高速公路網(wǎng)絡為有向圖G＝（N，I）。其中：N為網(wǎng)絡中的節(jié)點集合，I為網(wǎng)絡中的路段集合。如圖1所示，博弈雙方分別為交通管理者和網(wǎng)絡攻擊者，交通管理者指高速公路交通管理部門，網(wǎng)絡攻擊者為高速公路網(wǎng)絡威脅事件的抽象主體。博弈雙方的目的分別是通過實施相應的路徑分配策略或路段失效策略，增加或降低整個網(wǎng)絡的考慮失效風險的總出行費用V。當某一博弈過程中系統(tǒng)的帶有失效風險的總出行費用值V的變化量小于給定的收斂閾值ε時，則博弈過程終止，系統(tǒng)達到納什均衡狀態(tài)。此時交通管理者的交通分配策略與網(wǎng)絡攻擊者的路網(wǎng)攻擊策略均可達最優(yōu)。

圖1 高速公路網(wǎng)絡中的博弈模型Fig.1 Game model in freeway network

博弈結(jié)束時，輸出的網(wǎng)絡攻擊者的各路段失效概率的排序，即為網(wǎng)絡中關(guān)鍵路段識別的標準；交通管理者的交通流量分配策略，則包含了交通管理者為降低路網(wǎng)脆弱性所能夠?qū)嵤┑南鄳慕煌ü芾硪?guī)劃或交通設施改善的最優(yōu)方案。

表1為相關(guān)符號的定義。交通管理者和網(wǎng)絡攻擊者之間的博弈目標可以用極大極小準則來表示。

目標函數(shù)（1）中，網(wǎng)絡考慮失效風險的總出行費用V的值是由每個路段的考慮失效風險的出行費用累加求和得到的，與交通管理者的路段流量分配比例γ和網(wǎng)絡攻擊者的路段失效概率ρ有關(guān)，在該博弈框架中，1個路段同時具有2個屬性，即交通管理者在交通分配時將該路段作為可選路段的概率和網(wǎng)絡攻擊者在攻擊路網(wǎng)時選擇該路段失效的概率。交通管理者的目標是通過交通分配策略使網(wǎng)絡的考慮失效風險的總出行費用最小，而網(wǎng)絡攻擊者的目標是通過選擇一些路段使其失效而使網(wǎng)絡的考慮失效風險的總出行費用最大。

對式（2）進行一些基本的約束，即高速公路網(wǎng)絡中的所有路段被交通管理者所分配的流量比例累加和應該為1，且被網(wǎng)絡攻擊者失效的概率累加和也為1，并且每個路段的γ和ρ的取值都為非負。

然而，交通管理者問題和網(wǎng)絡攻擊者問題仍然比較復雜。目標函數(shù)是基于路段累加的形式來表示的，實際上基于路徑的方法能夠更加真實的反應網(wǎng)絡上的流量傳播及分配情形，但很難以路徑的形式進行表示。為簡化模型及計算過程，本文仍以路段為基本單元表示目標函數(shù)。但是為了更真實的反映網(wǎng)絡流量沿路徑傳播的情形，在交通管理者進行決策求解的問題中，以路徑為基本對象，體現(xiàn)流量沿路徑傳播的現(xiàn)實。而對于網(wǎng)絡攻擊者的決策仍以路段為單元，但由于其選擇路段失效概率會相應的參考交通管理者的決策方案，所以也包含了路徑方面的考慮。

表1 符號定義Tab.1 Notation index

2 博弈雙方的策略集

2.1 交通管理者決策過程

基于Wardrop平衡原理的交通分配的數(shù)學規(guī)劃模型為：

2.2 網(wǎng)絡破壞者決策過程

為了計算網(wǎng)絡攻擊者對路網(wǎng)中各路段的失效概率，本文將網(wǎng)絡攻擊者的路段失效策略看作1種包含信息量，引入信息熵的概念，來表征信息源在發(fā)出信息前的平均不確定度，則由信息熵的概念，的熵函數(shù)為的熵函數(shù)賦權(quán)值，引入加權(quán)熵函數(shù)，這一權(quán)值不僅在一定程度上體現(xiàn)了網(wǎng)路攻擊者的理性程度，而且還使網(wǎng)絡攻擊者對于路段失效概率有顯式解。引入加權(quán)熵函數(shù)后，當θ≠0時，原問題的修正目標函數(shù)如下：

同時，由于約束條件的存在，即所有的路段失效的概率應該收斂于1，故定義1個收斂于1的數(shù)列，即

將上式除號上下2項乘以e，則有：

通過上面的分析，最終的等式（13）描述了當交通管理者更新其交通分配策略時，網(wǎng)絡攻擊者做出的相應的對策。本文稱參數(shù)θ為網(wǎng)絡攻擊者對于交通管理者策略的反應強度。當θ變大時，網(wǎng)絡中路段失效策略的不確定度會隨之變小，也就是說網(wǎng)絡攻擊者對于網(wǎng)絡攻擊的確定性越強，對交通分配方案的反應強度大，將集中攻擊網(wǎng)絡中的一小部分路段，這些路段即為所謂的關(guān)鍵路段，對于網(wǎng)絡功能的維持具有重要的作用，此時網(wǎng)絡攻擊者的攻擊性越強；反之，當θ變小時，網(wǎng)絡攻擊者攻擊路段的不確定度變大，對于這些關(guān)鍵路段的攻擊性則變?nèi)?，路段失效概率在網(wǎng)絡中就越分散，此時網(wǎng)絡攻擊者的攻擊性越弱。

當θ為0時，網(wǎng)絡攻擊者攻擊網(wǎng)絡的不確定度變得無效大，即對于網(wǎng)絡中各個路段的損壞的概率是相等的，即1／｜I｜。實質(zhì)上，參數(shù)θ一定程度上體現(xiàn)了網(wǎng)絡攻擊者的理性程度。

3 算法基本流程

流程的基本輸入數(shù)據(jù)為路網(wǎng)基本數(shù)據(jù)，可分為3個部分：網(wǎng)絡拓撲結(jié)構(gòu)、OD需求和自由流行程時間。在網(wǎng)絡的初始化階段，設定ε的值，并設定，i∈I。路段失效狀態(tài)函數(shù)會基于路段行程時間和初值設置參數(shù)，計算路段在失效狀態(tài)下的費用。該步驟的計算結(jié)果將作為計算路段加權(quán)失效費用的輸入信息。此外，加權(quán)失效路段費用函數(shù)還需要上1個博弈過程中的路段失效信息，并應用連續(xù)平均法來計算路段歷史費用信息；計算結(jié)果將與路網(wǎng)拓撲結(jié)構(gòu)和OD需求一起作為輸入數(shù)據(jù)，實現(xiàn)交通管理者的用戶均衡分配。

由于假設網(wǎng)絡攻擊者和交通管理者具有完全信息，網(wǎng)絡攻擊者直接收集交通管理者的用戶均衡交通分配中的路段流量分配比例信息，根據(jù)交通管理者和加權(quán)熵函數(shù)來確定攻擊策略。網(wǎng)絡攻擊者策略的輸出是路段被攻擊概率，交通管理者策略的輸出是流量分配比例，以及路段費用加權(quán)失效費用共同輸入到網(wǎng)絡考慮失效風險的總出行費用函數(shù)中，當網(wǎng)絡考慮失效風險的總出行費用收斂于給定的判別條件時，博弈終止，輸出關(guān)鍵路段排序數(shù)據(jù)。算法基本流程如下：

步驟1。網(wǎng)絡初始化。

步驟4。進行用戶均衡交通分配。

步驟6。計算網(wǎng)絡的考慮失效風險的總出行費用，Vn（γ，ρ）。

步驟7。若Vn（γ，ρ）－Vn－1（γ，ρ）＜ε，結(jié)束；否則，返回步驟1。

4 算例分析

黑龍江省高速公路全長4 084km，是全國為數(shù)不多高速公路超過4 000km的省份之一。共有149個網(wǎng)絡節(jié)點（收費站），179個路段，服務區(qū)68對。以哈同高速、哈雙高速、哈綏高速、哈大高速、鶴大高速等為骨干，連接省內(nèi)各主要城市及地區(qū)。道路多為雙向4車道，中央均設置分隔帶。正常路段小客車最高限速120km／h、大客車100km／h、貨車80km／h，特殊受限路段（連續(xù)彎道、隧道、橋梁等）限速相應降低。

黑龍江省高速公路網(wǎng)絡拓撲結(jié)構(gòu)如圖2所示。

圖2 黑龍江省高速公路網(wǎng)絡圖Fig.2 Freeway network of Heilongjiang province

黑龍江省高速公路的聯(lián)網(wǎng)收費數(shù)據(jù)，記錄了車輛進入路網(wǎng)和駛出路網(wǎng)的位置及時間，也就是路網(wǎng)中的每個節(jié)點都是1個交通需求點，既是起始點也是目的地。關(guān)鍵路段識別結(jié)果見表2（只列出前15個路段）。

根據(jù)表2的計算結(jié)果，對θ值變化時的關(guān)鍵路段的失效概率及路段流量分配比例進行分析。如圖3（a）所示，隨著θ的值由1增加到10，網(wǎng)絡攻擊者使排序在前幾位的關(guān)鍵路段的失效概率隨θ值的增大而增大，由于受到約束條件 ∑eEρe＝1的限制，則排序名次靠后的路段的失效概率相應有所減少，也就是路段失效的概率逐漸集中到一小部分路段上，當θ＝10時，網(wǎng)絡攻擊者的基本上只是使極少部分路段失效。即隨著θ的增大，路段失效概率在路網(wǎng)中分配趨向于集中某些路段上。也就是θ的值越大，網(wǎng)絡攻擊者對于關(guān)鍵路段的攻擊性越強，從而相應制定重點攻擊最為關(guān)鍵的一些路段的策略。

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

圖3 路段失效策略及流量分配策略在路網(wǎng)中的分配Fig.3 Distribution of link failure and link using strategy

而對于各路段流量分配比例，則恰恰相反，如圖3（b）所示，當θ值較小時，由于網(wǎng)絡攻擊者的失效策略在網(wǎng)絡中分配較為均勻，且各路段失效概率都不太大，所以交通管理者能夠更為可靠的使用路網(wǎng)中的最短路徑，從而使路徑的分配主要集中在某些重要道路上，同樣由于 ∑eEγi＝1的限制，其他道路的流量分配比例則較??；而隨著θ的增大，網(wǎng)絡攻擊者對于關(guān)鍵路段，也就是最短路徑較為集中的路段的攻擊性變強，使其失效概率增大，這時交通管理者將相應的對路徑分配進行調(diào)整，將其流量分流到其他路段，從而使得路網(wǎng)中路段的流量分配比例的分配則趨于均勻，這正是博弈的結(jié)果。然而，無論θ取值的大小如何，一些被攻擊概率大的路段的結(jié)果基本一致，即θ的取值只影響網(wǎng)絡攻擊者的攻擊策略分布范圍，也可以說是集中程度，而不會影響關(guān)鍵路段的識別結(jié)果。關(guān)鍵路段識別結(jié)果見圖4（θ＝5）

圖4 關(guān)鍵路段識別結(jié)果Fig.3 Results of critical link identification

圖4 的識別結(jié)果中，106號路段為哈同高速賓縣段，該路段不僅是事故多發(fā)路段，而且交通需求較高，車流量大；97，98號路段為哈同高速依蘭段，該路段同樣為事故多發(fā)路段，冬季雪大且易結(jié)冰，且夏季雨水多，發(fā)生過雨水淹沒道路的情況；同樣，26，27，28號道路，哈牡高速亞布力段，冬季道路容易結(jié)冰，而且道路線形多連續(xù)彎路；12，14號路段分別為哈雙高速瓦盆窯段及拉林河段，16號路段為哈阿高速，這幾處均為車流量較大路段，而且連接省會城市哈爾濱及與其聯(lián)系緊密的雙城市及阿城區(qū)，交通需求大，同時根據(jù)高速公路收費數(shù)據(jù)可以看出，哈雙高速拉林河段，即14號道路大貨車混入率較高，交通流組成混雜?？梢钥闯鲎R別結(jié)果與實際情況基本一致。

5 結(jié)束語

高速公路網(wǎng)絡關(guān)鍵路段的識別對于網(wǎng)絡的正常運營及交通安全具有重要意義?，F(xiàn)有的關(guān)鍵路段識別方法或計算量巨大、或識別效率不高，不能很好的應用于實際的道路網(wǎng)絡。基于博弈論的思想，將關(guān)鍵路段的識別方法變被動為主動，構(gòu)造了網(wǎng)絡攻擊者的行為主體，建立了攻防博弈模型。攻擊者以加權(quán)熵函數(shù)為決策依據(jù)，防守者以用戶均衡交通分配為決策依據(jù)，當博弈達到均衡時，既能夠輸出網(wǎng)絡的關(guān)鍵路段排序，又能給出相應的交通分配方案。實踐證明，該方法能夠有效地識別網(wǎng)絡中的關(guān)鍵路段。

交通需求是關(guān)鍵路段識別中的重要標準，除此之外，交通網(wǎng)絡中的交通事故數(shù)據(jù)、氣象數(shù)據(jù)等對于突發(fā)事件的發(fā)生也有明顯的影響。利用高速公路網(wǎng)絡運營過程中的多源數(shù)據(jù)來更為全面地分析網(wǎng)絡的關(guān)鍵路段及節(jié)點，是今后研究的重要方向。

［1］ 王俊驊，趙新勇，叢浩哲.高速公路網(wǎng)突發(fā)交通事件時空影響預測模型［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］ 李斌，張紀升，袁 宇，等.國家高速公路安全和服務技術(shù)開發(fā)與工程應用示范綜述［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.