基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法

1.一種基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法，其特征在于，包括如下步驟：
(1)、用原始法建立交通網(wǎng)絡(luò)的拓?fù)淠Ｐ?，?gòu)筑每條有向路段的子網(wǎng)絡(luò)，同時(shí)統(tǒng)計(jì)子網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和有向路段數(shù)，計(jì)算相應(yīng)路段所在子網(wǎng)絡(luò)的冗余度指數(shù)；
(2)、以步驟(1)中路段所在子網(wǎng)絡(luò)冗余度指數(shù)小者優(yōu)先選取的原則，從交通網(wǎng)絡(luò)的所有路段中先選取若干條路段作為候選關(guān)鍵路段；
(3)、逐一計(jì)算步驟(2)中每條候選關(guān)鍵路段的損壞、降級(jí)或失效對(duì)交通網(wǎng)絡(luò)的影響程度，選取影響程度較大的若干條路段作為交通網(wǎng)絡(luò)的關(guān)鍵路段。
2.如權(quán)利要求1所述的方法，其特征在于，步驟(1)中，構(gòu)以有向路段為中心，其中i,j為節(jié)點(diǎn)編號(hào)；步長半徑為η的子網(wǎng)絡(luò) 步長半徑η表示子網(wǎng)絡(luò) 中所有節(jié)點(diǎn)與有向路段的最大距離。
3.如權(quán)利要求1所述的方法，其特征在于，步驟(1)中，所述子網(wǎng)絡(luò) 的冗余度指數(shù)的計(jì)算方式為 其中， 表示子網(wǎng)絡(luò) 中的節(jié)點(diǎn)數(shù)，
表示子網(wǎng)絡(luò) 中的有向邊數(shù)或無向邊數(shù)的2倍，在子網(wǎng)絡(luò)構(gòu)筑同時(shí)對(duì) 和進(jìn)行計(jì)數(shù)。

基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法\n技術(shù)領(lǐng)域\n[0001] 本發(fā)明涉及智能交通技術(shù)領(lǐng)域，主要涉及交通網(wǎng)絡(luò)關(guān)鍵路段辨識(shí)與搜索方面，更具體地說，是一種滿足一定搜索準(zhǔn)確率條件下具有較高搜索效率的關(guān)鍵路段搜索方法。\n背景技術(shù)\n[0002] 交通網(wǎng)絡(luò)是城市交通運(yùn)輸系統(tǒng)的重要組成部分，將城市在空間上聯(lián)系起來，是城市各項(xiàng)機(jī)能得以正常運(yùn)轉(zhuǎn)的基礎(chǔ)。而交通網(wǎng)絡(luò)的關(guān)鍵路段是指在一定時(shí)期內(nèi)的損壞、降級(jí)或失效會(huì)對(duì)整個(gè)交通網(wǎng)絡(luò)產(chǎn)生重大負(fù)面影響的路段。準(zhǔn)確快速辨識(shí)交通網(wǎng)絡(luò)的關(guān)鍵路段在戰(zhàn)略規(guī)劃層面、戰(zhàn)術(shù)規(guī)劃層面和交通運(yùn)行管理與控制層面均具有重要意義，準(zhǔn)確快速定位交通網(wǎng)絡(luò)的脆弱部位，針對(duì)性地采取交通治理措施，有助于提高網(wǎng)絡(luò)的抗干擾能力，具有較高的產(chǎn)出投入比。\n[0003] 交通網(wǎng)絡(luò)關(guān)鍵路段辨識(shí)過程中的重要一點(diǎn)是高效準(zhǔn)確地搜索交通網(wǎng)絡(luò)的關(guān)鍵路段，常用的關(guān)鍵路段搜索方法可以分為暴力搜索法和候選路段法兩類。\n[0004] 傳統(tǒng)的暴力搜索法是理論研究中較常用的關(guān)鍵路段搜索算法，通過依次斷開交通網(wǎng)絡(luò)的所有路段計(jì)算每條路段對(duì)交通網(wǎng)絡(luò)性能的影響程度，以此可以準(zhǔn)確搜索出對(duì)交通網(wǎng)絡(luò)性能影響程度最大的關(guān)鍵路段，是最簡單的搜索方法。暴力搜索法的優(yōu)點(diǎn)是可以比較交通網(wǎng)絡(luò)所有路段對(duì)網(wǎng)絡(luò)性能的影響程度，因此可以準(zhǔn)確搜索網(wǎng)絡(luò)的關(guān)鍵路段，搜索準(zhǔn)確率為100％。但由于需要依次斷開網(wǎng)絡(luò)的每條路段進(jìn)行一次交通分配，計(jì)算量較大，搜索效率較低，在大規(guī)模交通網(wǎng)絡(luò)應(yīng)用中可行較差。例如，對(duì)于39018條路段組成的芝加哥局部交通網(wǎng)絡(luò)，進(jìn)行一次交通分配約0.5小時(shí)(達(dá)到0.0001精度)[1]，可以計(jì)算暴力搜索法在交通分配階段耗時(shí)已超過2年。\n[0005] 候選路段法先根據(jù)某種法則預(yù)先選取最有可能成為關(guān)鍵路段的路段作為候選路段，然后依次斷開候選路段獲得每條候選路段對(duì)交通網(wǎng)絡(luò)性能的影響程度，以此從候選路段中搜索對(duì)交通網(wǎng)絡(luò)性能影響程度最大的路段作為關(guān)鍵路段。一般候選路段數(shù)遠(yuǎn)小于交通網(wǎng)絡(luò)的總路段數(shù)，因此候選路段法的交通分配執(zhí)行次數(shù)顯著小于暴力搜索法，搜索效率較高，在實(shí)際大規(guī)模交通網(wǎng)絡(luò)中應(yīng)用較多。其關(guān)鍵在于確定候選路段的選取法則，可以是OD對(duì)間最小成本路徑的組成路段，或是隨機(jī)交通分配中具有較高選擇概率的路段。\n[0006] 有搜索方法[2]選取了10種基于路段的候選路段選取指標(biāo)(例如V/C比)，但結(jié)果表明這些指標(biāo)并不能較為準(zhǔn)確地搜索交通網(wǎng)絡(luò)的關(guān)鍵路段。也有搜索方法[3]引入了一種基于路段影響區(qū)域的候選路段選取法則，其基本思想是生成以某路段為中心的一定步長半徑的路段子網(wǎng)絡(luò)，通過子網(wǎng)絡(luò)各路段交通流量反推子網(wǎng)絡(luò)的OD矩陣，用于該路段斷開前后子網(wǎng)絡(luò)的交通分配，最后以路段斷開后子網(wǎng)絡(luò)行程時(shí)間的增加程度作為候選路段的選取指標(biāo)，優(yōu)先選取指標(biāo)值大的路段作為關(guān)鍵路段的候選路段。結(jié)果表明，在合適的參數(shù)條件下，基于路段影響區(qū)域的關(guān)鍵路段搜索方法具有較好的搜索準(zhǔn)確率和搜素效率。然而該候選路段選取法則需要反推OD矩陣，顯然OD反推算法的選取對(duì)關(guān)鍵路段的搜索準(zhǔn)確率和搜索效率有重要影響，且操作較為復(fù)雜。\n[0007] 綜上，現(xiàn)有的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法很難同時(shí)做到較高的搜索準(zhǔn)確率和搜索效率以及較強(qiáng)的可操作性。\n[0008] 參考資料\n[0009] [1]Dial?R?B.A?path-based?user-equilibrium?traffic?assignment?algorithm?that?obviates?path?storage?and?enumeration[J].Transportation?Research?Part?B:Methodological,2006,40(10):917-936.\n[0010] [2]Knoop?V?L,Snelder?M,Van?Zuylen?H?J.Comparison?of?link-level?robustness?indicators[C]//3rd?International?Symposium?on?Transportation?Network?Reliability,Delft.2007.\n[0011] [3]Chen?B?Y,Lam?W?H?K,Sumalee?A,et?al.Vulnerability?analysis?for?large-scale?and?congested?road?networks?with?demand?uncertainty[J]\n.Transportation?Research?Part?A:Policy?and?Practice,2012,46(3):501-516.發(fā)明內(nèi)容\n[0012] 本發(fā)明的目的是解決現(xiàn)有技術(shù)存在的缺陷和不足，選取反映路段子網(wǎng)絡(luò)拓?fù)涮匦缘穆范稳哂喽戎笖?shù)作為候選關(guān)鍵路段的選取指標(biāo)，提出了基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法，具有較高的搜索準(zhǔn)確率和搜索效率，且由于不涉及OD反推等復(fù)雜方法，可操作較強(qiáng)。\n[0013] 本發(fā)明給出的技術(shù)方案來為：\n[0014] 一種基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法，其特征在于，包括如下步驟：\n[0015] (1)、用原始法建立交通網(wǎng)絡(luò)的拓?fù)淠Ｐ?，?gòu)筑每條有向路段的子網(wǎng)絡(luò)，同時(shí)統(tǒng)計(jì)子網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和有向路段數(shù)，計(jì)算相應(yīng)路段所在子網(wǎng)絡(luò)的冗余度指數(shù)；\n[0016] (2)、以步驟(1)中路段所在子網(wǎng)絡(luò)冗余度指數(shù)小者優(yōu)先選取的原則，從交通網(wǎng)絡(luò)的所有路段中先選取若干條路段作為候選關(guān)鍵路段；\n[0017] (3)、逐一計(jì)算步驟(2)中每條候選關(guān)鍵路段的損壞、降級(jí)或失效對(duì)交通網(wǎng)絡(luò)的影響程度，選取影響程度較大的若干條路段作為交通網(wǎng)絡(luò)的關(guān)鍵路段。\n[0018] 本發(fā)明中，步驟(1)用復(fù)雜網(wǎng)絡(luò)理論中原始法建立交通網(wǎng)絡(luò)的拓?fù)淠Ｐ?，是將交叉路口和道路盡端視為節(jié)點(diǎn)，將連接兩交叉路口的路段視為邊，對(duì)交通網(wǎng)絡(luò)最直觀最簡單的映射，可以直接反映交通網(wǎng)絡(luò)的連通性。又可將各個(gè)連接節(jié)點(diǎn)間的幾何距離簡單地映射到兩節(jié)點(diǎn)間的邊上，可以使用地理學(xué)上的米制距離，比較符合人們的認(rèn)知習(xí)慣，容易理解和運(yùn)用。\n[0019] 步驟(1)中，構(gòu)筑以有向路段為中心、步長半徑為η的子網(wǎng)絡(luò) 步長半徑η表示子網(wǎng)絡(luò) 中所有節(jié)點(diǎn)與路段的最大距離。\n[0020] 步驟(1)中，所述子網(wǎng)絡(luò) 的冗余度指數(shù) 的計(jì)算方式為\n其中， 表示子網(wǎng)絡(luò) 中的節(jié)點(diǎn)數(shù)， 表示子網(wǎng)絡(luò)\n中的有向邊數(shù)或無向邊數(shù)的2倍，在子網(wǎng)絡(luò)構(gòu)筑同時(shí)進(jìn)行計(jì)數(shù)。\n[0021] 本發(fā)明中，步驟(2)從交通網(wǎng)絡(luò)的所有路段中先選取候選關(guān)鍵路段是以路段所在子網(wǎng)絡(luò)冗余度指數(shù) 小者優(yōu)先選取為原則。路段冗余度指數(shù) 越小，則可替換路徑越少，路段失效對(duì)子網(wǎng)絡(luò) 的影響程度越大，路段越可能成為交通網(wǎng)絡(luò)的關(guān)鍵路段，因此優(yōu)先選取為候選路段。\n[0022] 步驟(2)中，候選關(guān)鍵路段數(shù)同時(shí)影響關(guān)鍵路段搜索算法的搜索效率和搜索準(zhǔn)確率，候選關(guān)鍵路段數(shù)越大，搜索準(zhǔn)確率越高，但搜索時(shí)長越長，搜索效率越低。\n[0023] 本發(fā)明中，步驟(3)中候選關(guān)鍵路段對(duì)交通網(wǎng)絡(luò)的影響程度可通過路段損壞、降級(jí)或失效后網(wǎng)絡(luò)性能的變化度量，而網(wǎng)絡(luò)性能描述了在給定時(shí)期內(nèi)交通網(wǎng)絡(luò)可被使用的可能性。常用的交通網(wǎng)絡(luò)性能指標(biāo)可分為可靠性指標(biāo)、脆弱性指標(biāo)和風(fēng)險(xiǎn)指標(biāo)?？煽啃灾笜?biāo)側(cè)重交通網(wǎng)絡(luò)滿足預(yù)定要求的可靠程度，包括連通可靠性指標(biāo)、行程時(shí)間可靠性指標(biāo)和通行能力可靠性指標(biāo)。脆弱性指標(biāo)包括僅考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的脆弱性指標(biāo)(特征路徑長度、聚類系數(shù)、度分布、效率和集中性指標(biāo)等)和以網(wǎng)絡(luò)可達(dá)性度量的脆弱性指標(biāo)(出行綜合成本、Hansen整體可達(dá)性指數(shù)和ARIA(Accessibility/Remoteness?Index?of?Australia)指數(shù))。\n其中，較為常用的是以路段損壞、降級(jí)或失效后交通網(wǎng)絡(luò)的綜合出行成本的增量為指標(biāo)。\n[0024] 步驟(3)中，路段損壞、降級(jí)或失效后網(wǎng)絡(luò)性能衰退程度越大，表示該路段對(duì)交通網(wǎng)絡(luò)的影響程度越大，路段越關(guān)鍵。搜索得到的交通網(wǎng)絡(luò)關(guān)鍵路段，根據(jù)對(duì)交通網(wǎng)絡(luò)影響程度大小排列，能得到所需的影響程度最大的前幾條關(guān)鍵路段，并能定量輸出需要的關(guān)鍵路段的關(guān)鍵指數(shù)，定量比較得到的關(guān)鍵路段對(duì)交通網(wǎng)絡(luò)的影響程度。\n[0025] 與現(xiàn)有交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法仍以傳統(tǒng)的暴力搜索方法為主，而候選路段法的候選關(guān)鍵路段選取法則在搜索效率、搜索準(zhǔn)確率和操作簡便性方面仍有不足相比，本發(fā)明對(duì)交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法進(jìn)行了以下幾方面的優(yōu)化：\n[0026] (1)預(yù)先選取關(guān)鍵路段候選路段，從候選路段中搜索交通網(wǎng)絡(luò)的關(guān)鍵路段，提高搜索效率；\n[0027] (2)以路段構(gòu)筑的子網(wǎng)絡(luò)的路段冗余度指數(shù)作為關(guān)鍵路段候選路段的選取指標(biāo)，在合理的參數(shù)條件下，具有較高的搜索準(zhǔn)去率和搜索效率；\n[0028] (3)構(gòu)筑路段子網(wǎng)絡(luò)以計(jì)算子網(wǎng)絡(luò)冗余度指數(shù)方法較為簡單，可操作性較強(qiáng)。\n[0029] 因此，在保證一定關(guān)鍵路段搜索準(zhǔn)確率的情況下，能有效提高搜索效率，且具有較強(qiáng)的可操作性。\n附圖說明\n[0030] 圖1為基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法流程圖。\n[0031] 圖2為計(jì)算路段子網(wǎng)絡(luò)冗余度指數(shù)核心方法的實(shí)例實(shí)施基本邏輯圖。\n[0032] 圖3為實(shí)例中以路段<9，10>為中心，步長半徑η為1的子網(wǎng)絡(luò)\n[0033] 圖4為實(shí)例中以路段<9，10>為中心，步長半徑η為2的子網(wǎng)絡(luò)\n具體實(shí)施方式\n[0034] 以下結(jié)合附圖對(duì)本發(fā)明技術(shù)方案作進(jìn)一步說明。\n[0035] 本發(fā)明的核心思想在于，提供一種基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法，通過引入路段子網(wǎng)絡(luò)冗余度指數(shù)作為候選關(guān)鍵路段的選取指標(biāo)，來克服現(xiàn)有交通網(wǎng)絡(luò)關(guān)鍵路段搜索方法在搜索效率、搜素準(zhǔn)確率和可操作性方面的不足。\n[0036] 圖1所示為基于路段子網(wǎng)絡(luò)冗余度的交通網(wǎng)絡(luò)關(guān)鍵路段搜索流程：\n[0037] 首先，城市道路交通網(wǎng)絡(luò)包括快速路(高架)、主干道、次干道和交通性的支路，但為簡化網(wǎng)絡(luò)可根據(jù)實(shí)際研究需求選取部分類型道路，用復(fù)雜網(wǎng)絡(luò)理論的原始法建立交通網(wǎng)絡(luò)拓?fù)淠Ｐ虶＝(V，E，Ω)，其中V表示交通網(wǎng)絡(luò)的非空節(jié)點(diǎn)集，E表示交通網(wǎng)絡(luò)的有向邊集，Ω表示交通網(wǎng)絡(luò)的屬性集。\n[0038] N個(gè)元素的非空節(jié)點(diǎn)集V＝{v1，v2，...，vN}中的元素vi表示第i個(gè)節(jié)點(diǎn)的編號(hào)(1≤i≤N)。以自然數(shù)1...N對(duì)各節(jié)點(diǎn)編號(hào)，令vi＝i，則節(jié)點(diǎn)集又可表示為V＝{1，2，...，N}。以一維數(shù)組R(i)表示與i∈V節(jié)點(diǎn)相連接的節(jié)點(diǎn)的數(shù)目，二維數(shù)組RV(i，j)，表示與i節(jié)點(diǎn)相連接的第j個(gè)(1≤j≤R(i))節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)(按編號(hào)從小到大排列)。因此與i節(jié)點(diǎn)相連接的有向邊可用∈E或∈E表示。屬性集Ω中元素主要為路段長度屬性L、路段自由流車速Vfree、路段實(shí)際通行能力屬性Ca和路段流量屬性F，即Ω＝{L，Vfree，Ca，F(xiàn)}。\n[0039] 路段長度屬性L是道路的基本屬性，可用二維數(shù)組L＝{l(i，j)}描述，表示從節(jié)點(diǎn)i到與之相連接的第j個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)RV(i，j))的有向邊對(duì)應(yīng)的有向路段長度，即：\n[0040]\n[0041] 當(dāng)存在有向邊時(shí)，l(i，j)取值為相應(yīng)有向路段的實(shí)際長度，單位為米(m)；當(dāng)不存在該有向邊時(shí)，以正無窮表示。\n[0042] 路段自由流車速Vfree反映了路段的速度限制，可用二維數(shù)組Vfree＝{vfree(i，j)}描述，表示從節(jié)點(diǎn)i到與之相連接的第j個(gè)節(jié)點(diǎn)(RV(i，j))的有向邊對(duì)應(yīng)的有向路段自由流車速，即：\n[0043]\n[0044] 當(dāng)存在有向邊時(shí)，vfree(i，j)取值為相應(yīng)有向路段的自由流車速FreeVelocity，單位為米/秒(m/s)，可根據(jù)設(shè)計(jì)車速確定；當(dāng)不存在該有向邊時(shí)，可以零表示。由路段長度屬性L和自由流車速Vfree可計(jì)算得各路段自由流狀態(tài)下的行程時(shí)間。\n[0045] 路段實(shí)際通行能力屬性Ca在一定程度上反映了道路等級(jí)，可用二維數(shù)組Ca＝{ca(i，j)}描述，表示從節(jié)點(diǎn)i到與之相連接的第j個(gè)節(jié)點(diǎn)(RV(i，j))的有向邊對(duì)應(yīng)的有向路段通行能力，即：\n[0046]\n[0047] 當(dāng)存在有向邊時(shí)，ca(i，j)取值為相應(yīng)有向路段的實(shí)際通行能力Capacity，單位為標(biāo)準(zhǔn)小汽車/時(shí)(PCU/h)或小時(shí)車流量(veh/h)，可通過調(diào)查或參考HCM(Highway?Capacity?Manual)等規(guī)范確定；當(dāng)不存在該有向邊時(shí)，可以零表示。\n[0048] 路段流量屬性F反映了出行者的路徑選擇結(jié)果，可用二維數(shù)組F＝{f(i，j)}描述，表示從節(jié)點(diǎn)i到與之相連接的第j個(gè)節(jié)點(diǎn)(RV(i，j))的有向邊對(duì)應(yīng)的有向路段實(shí)時(shí)交通流量，即：\n[0049]\n[0050] 當(dāng)存在有向邊時(shí)，f(i；j)取值為相應(yīng)有向路段的實(shí)時(shí)交通量Flow，單位為標(biāo)準(zhǔn)小汽車/時(shí)(PCU/h)或小時(shí)車流量(veh/h)；當(dāng)不存在該有向邊時(shí)，可以零表示。\n[0051] 然后，對(duì)于交通網(wǎng)絡(luò)的有向路段∈E，其中i、j分別表示路段的起、終點(diǎn)(i，j∈V)，可以從網(wǎng)絡(luò)G生成以路段為中心、步長半徑為η的子網(wǎng)絡(luò)，記為記節(jié)點(diǎn)k與路段的距離為Dist(k，)，則步長η\n的定義式為：\n[0052]\n[0053] 子網(wǎng)絡(luò)的步長半徑η的取值主要影響關(guān)鍵路段搜索算法的搜素準(zhǔn)確率，一般存在一個(gè)最佳值。可以η＝3～5為試驗(yàn)值，具體應(yīng)根據(jù)網(wǎng)絡(luò)規(guī)模和拓?fù)浣Y(jié)構(gòu)而定，但不宜過大而使子網(wǎng)絡(luò)規(guī)模接近整個(gè)交通網(wǎng)絡(luò)的規(guī)模。\n[0054] 表示子網(wǎng)絡(luò) 中所有節(jié)點(diǎn)與路段的最大距離。記節(jié)點(diǎn)i、j的距離為||i，j||，表示連接節(jié)點(diǎn)i、j的最小無向邊數(shù)，則節(jié)點(diǎn)與路段的距離Dist(k，)的定義式為：\n[0055] Dist(k，)＝Min(||k，i||，||k，j||)???(6)\n[0056] 如圖2所示，在以路段為中心構(gòu)筑子網(wǎng)絡(luò) 同時(shí)，計(jì)數(shù)子網(wǎng)絡(luò) 中的節(jié)點(diǎn)數(shù) 和有向邊數(shù) 計(jì)算相應(yīng)的冗余度指數(shù) 的核心方法，具體實(shí)施\n方式如下：\n[0057] 輸入：\n[0058] 交通網(wǎng)絡(luò)拓?fù)淠Ｐ虶＝(V，E，Ω)\n[0059] 步長半徑η\n[0060] 路段∈E\n[0061] 輸出：\n[0062] 冗余度指數(shù)\n[0063] ①初始化：\n[0064] 設(shè)置交通網(wǎng)絡(luò)所有節(jié)點(diǎn)與路段的距離\n[0065] 設(shè)置Dist(i，)＝0和Dist(j，)＝0；\n[0066] 設(shè)置研究路段起點(diǎn)集I＝(i，j}；\n[0067] 設(shè)置子網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)數(shù)器Nsub＝0和有向路段計(jì)數(shù)器Msub＝0。\n[0068] ②構(gòu)筑子網(wǎng)絡(luò)同時(shí)統(tǒng)計(jì)子網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和有向路段數(shù)：\n[0069] 從起點(diǎn)集I中選取節(jié)點(diǎn)k，使得Dist(k，)＝Min?Dist(a，)，a∈I，直到起點(diǎn)集I為空；\n[0070] 從起點(diǎn)集I中去除節(jié)點(diǎn)k；\n[0071] 統(tǒng)計(jì)子網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，設(shè)置節(jié)點(diǎn)計(jì)數(shù)器Nsub＝Nsub+1；\n[0072] 設(shè)置研究路段終點(diǎn)集J＝{a}(a∈V)，其中a為滿足∈E或∈E的所有節(jié)點(diǎn)；\n[0073] 對(duì)于終點(diǎn)集J中每一個(gè)節(jié)點(diǎn)l，如果同時(shí)滿足下列兩式(7)(8)，則設(shè)置Dist(l，)＝Dist(k，)+1，并將節(jié)點(diǎn)l添加到起點(diǎn)集I。如果存在路段∈E，同時(shí)滿足下式(9)，則統(tǒng)計(jì)子網(wǎng)絡(luò)有向路段數(shù)，設(shè)置有向路段計(jì)數(shù)器Msub＝Msub+1；\n[0074] Dist(k，)+1≤η????????????????(7)\n[0075] Dist(l，)≥Dist(k，)+1?????????(8)\n[0076] Dist(l，)≤η?????????????????(9)\n[0077] ③計(jì)算子網(wǎng)絡(luò)冗余度指數(shù)：\n[0078] 計(jì)算以路段為中心、步長半徑為η的子網(wǎng)絡(luò) 的冗余度指數(shù)為\n[0079] 圖3和圖4分別為以路段<9，10>為中心，步長半徑η分別為1、2的子網(wǎng)絡(luò) 和計(jì)算相應(yīng)的冗余度指數(shù)分別為 和\n[0080] 其次，對(duì)于交通網(wǎng)絡(luò)G的所有路段∈E，均可計(jì)算得到相應(yīng)子網(wǎng)絡(luò)的冗余度指數(shù) 越小，則可替換路徑越少，路段失效對(duì)子網(wǎng)絡(luò) 的影響程\n度越大，路段越可能成為交通網(wǎng)絡(luò)的關(guān)鍵路段，應(yīng)優(yōu)先選取為候選關(guān)鍵路段，由此可以得到λ條候選關(guān)鍵路段。\n[0081] 顯然，候選關(guān)鍵路段數(shù)λ越大，搜索準(zhǔn)確率越高，但搜索時(shí)長越長，搜索效率越低。\n候選關(guān)鍵路段數(shù)可初步選取為待辨識(shí)關(guān)鍵路段數(shù)的2～5倍，具體應(yīng)根據(jù)網(wǎng)絡(luò)規(guī)模試驗(yàn)估計(jì)得到，但一般不宜超過整個(gè)交通網(wǎng)絡(luò)路段數(shù)的一半。\n[0082] 最后，逐一計(jì)算每條候選關(guān)鍵路段的損壞、降級(jí)或失效對(duì)交通網(wǎng)絡(luò)的影響程度，選取影響程度較大的若干條路段作為交通網(wǎng)絡(luò)的關(guān)鍵路段。路段對(duì)交通網(wǎng)絡(luò)的影響程度可采用路段完全失效后，交通網(wǎng)絡(luò)綜合出行成本的相對(duì)增量度量指標(biāo)。\n[0083] 對(duì)于正常狀態(tài)下的交通網(wǎng)絡(luò)G＝(V，E，Ω)，利用隨機(jī)用戶平衡算法等交通分配方法分配交通網(wǎng)絡(luò)的OD矩陣，可以得到各路段∈E上的交通量f0(i，j)和行程時(shí)間c0(i，j)；對(duì)于候選關(guān)鍵路段完全失效后的交通網(wǎng)絡(luò)Gab＝(V，Eab，Ω)，其中Eab＝E\{}，同樣分配交通網(wǎng)絡(luò)的OD矩陣，相應(yīng)地可以得到各路段∈E上的交通量fab(i，j)和行程時(shí)間cab(i，j)。則候選路段對(duì)交通網(wǎng)絡(luò)的影響指數(shù)CIab計(jì)算式為：\n[0084]\n[0085] CIab指數(shù)值越大，表示路段對(duì)交通網(wǎng)絡(luò)G的影響程度越大，即越關(guān)鍵。\n[0086] 對(duì)各路段的關(guān)鍵指數(shù)從大到小進(jìn)行排序，即：\n[0087]\n[0088] 式中，Ne表示交通網(wǎng)絡(luò)G＝(V，E，Ω)的路段數(shù)。從中選取CIab指數(shù)顯著較大的幾條路段作為交通網(wǎng)絡(luò)的關(guān)鍵路段。