安 實(shí) 張 濤 張昕明 王 健

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 符號(hào)定義Tab.1 Notation index

2 博弈雙方的策略集

2.1 交通管理者決策過程

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

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

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

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

將上式除號(hào)上下2項(xiàng)乘以e，則有：

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

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

3 算法基本流程

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

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

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

步驟4。進(jìn)行用戶均衡交通分配。

步驟6。計(jì)算網(wǎng)絡(luò)的考慮失效風(fēng)險(xiǎn)的總出行費(fèi)用，Vn（γ，ρ）。

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

4 算例分析

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

黑龍江省高速公路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示。

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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