陳錦渠，殷 勇*，2，3，朱 蔓

(1.西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，四川 成都 611756；2.綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 611756；3.綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，四川 成都 611756)

1 引言

城市軌道交通(Urban Rail Transit，URT)以其安全、快速及環(huán)保的特點(diǎn)正逐漸發(fā)展成為中國(guó)各大城市最為主要的公共交通方式?，F(xiàn)如今，中國(guó)URT在面臨極大發(fā)展機(jī)遇的同時(shí)，也迎接著嚴(yán)峻的運(yùn)營(yíng)挑戰(zhàn)。近年來(lái)URT運(yùn)營(yíng)突發(fā)事件頻發(fā)，該類事件不僅影響著URT的正常運(yùn)營(yíng)產(chǎn)生影響，還降低了乘客采用URT出行的信任度。因此，研究發(fā)生突發(fā)事件情況下URT的修復(fù)策略具有重要意義。

國(guó)內(nèi)外學(xué)者曾對(duì)URT網(wǎng)絡(luò)的防護(hù)策略展開(kāi)研究。在早期研究中，研究學(xué)者注重于分析URT在隨機(jī)攻擊及蓄意攻擊下的脆弱性，并采用網(wǎng)絡(luò)效率[1]，連通度[2]，有效節(jié)點(diǎn)比[3]，相對(duì)最大連通子圖[4]及可容忍出行路徑[5]等作為抗毀性指標(biāo)。他們的研究結(jié)果表明，相較于隨機(jī)攻擊，蓄意攻擊對(duì)URT網(wǎng)絡(luò)抗毀性的影響更大，保護(hù)關(guān)鍵站點(diǎn)能夠有效提升URT網(wǎng)絡(luò)的抗毀性。然而該類研究并未深入探討失效網(wǎng)絡(luò)的修復(fù)順序問(wèn)題。隨著研究的深入，Bruneau等人[6]提出了彈性損失三角形的概念用于衡量系統(tǒng)應(yīng)對(duì)突發(fā)事件的能力。基于Bruneau等人的研究，Li等人[7]、Zhang等人[8]及Saadat等人[9]分別運(yùn)用彈性損失三角形理論分析了北京、上海及華盛頓地鐵網(wǎng)絡(luò)應(yīng)對(duì)突發(fā)事件的能力，并結(jié)合枚舉的方式，以網(wǎng)絡(luò)彈性最優(yōu)為目標(biāo)分析了受損URT站點(diǎn)的最優(yōu)修復(fù)策略。此外，Hua等人[10]建立了以最大化運(yùn)營(yíng)能力、最小化恢復(fù)時(shí)間為目標(biāo)的URT受損修復(fù)模型，以新加坡城市快運(yùn)系統(tǒng)為例分析了所建立模型的有效性。

上述研究指出合適的URT防護(hù)策略能夠顯著提高URT網(wǎng)絡(luò)的抗毀性、保證URT的正常運(yùn)營(yíng)。已有研究側(cè)重于研究URT站點(diǎn)的防護(hù)策略，而作為URT重要組成部分的區(qū)間卻鮮有涉及，且均強(qiáng)調(diào)通過(guò)枚舉的方式得到最優(yōu)修復(fù)策略，當(dāng)失效站點(diǎn)(區(qū)間)數(shù)過(guò)多時(shí)，枚舉法將不再適用。因此為彌補(bǔ)現(xiàn)有研究的不足，本文以失效URT區(qū)間為研究對(duì)象，建立了全日客運(yùn)量最大、修復(fù)完成后擁擠度最小的多目標(biāo)模型，結(jié)合NSGA-II算法求解得到該模型的Pareto最優(yōu)解集。

2 模型建立

2.1 攻擊策略

實(shí)際運(yùn)營(yíng)中，URT區(qū)間有可能由于受到暴雨、地震、恐怖襲擊等事件的影響而失效。其中，暴雨、地震等自然災(zāi)害屬于隨機(jī)事件，恐怖襲擊等人為破壞屬于蓄意事件。因此，為貼合實(shí)際情況，本文分別選用隨機(jī)攻擊及蓄意攻擊模擬URT區(qū)間受自然災(zāi)害及人為破壞而失效的情況。

計(jì)算時(shí)，運(yùn)用Matlab的隨機(jī)數(shù)確定隨機(jī)攻擊的區(qū)間；結(jié)合式(1)計(jì)算區(qū)間在全網(wǎng)的重要程度，選取最重要的區(qū)間作為蓄意攻擊的對(duì)象。

(1)

式中，LIe為區(qū)間e的重要度；ve為區(qū)間e的客流量；V為全網(wǎng)的客流量。

2.2 URT區(qū)間失效修復(fù)模型

2.2.1 模型假設(shè)

根據(jù)本文模型求解的需要，降低求解的復(fù)雜度，提出以下幾點(diǎn)假設(shè)：

1)假設(shè)URT區(qū)間全日客運(yùn)量均勻分布，不隨時(shí)間變化；

2)修復(fù)1個(gè)失效URT區(qū)間需要1單位維修資源，不考慮不同失效區(qū)間修復(fù)的難易程度；

3)因URT失效而無(wú)法出行的乘客將采用其它公共交通方式出行。

2.2.2 目標(biāo)函數(shù)

乘客通過(guò)URT實(shí)現(xiàn)出行目的，而當(dāng)URT網(wǎng)絡(luò)因隨機(jī)攻擊或蓄意攻擊而失效時(shí)，乘客的出行將受到極大影響，部分乘客將無(wú)法通過(guò)URT網(wǎng)絡(luò)出行。因此，在制定修復(fù)策略時(shí)，應(yīng)以最大化全日客運(yùn)量為目標(biāo)，目標(biāo)函數(shù)表達(dá)式為

(2)

劉朝陽(yáng)等人[3]的研究指出，站點(diǎn)失效將直接導(dǎo)致URT站點(diǎn)流量的重分配，同理可得，URT區(qū)間的失效也將導(dǎo)致URT區(qū)間流量的重分配。區(qū)間流量的重分配有可能導(dǎo)致部分區(qū)間的流量過(guò)大，嚴(yán)重影響URT的運(yùn)營(yíng)安全。結(jié)合嚴(yán)波[11]及李田野等人[12]的研究，區(qū)間流量可以轉(zhuǎn)化為區(qū)間的擁擠度。此外，部分乘客由于區(qū)間失效將無(wú)法通過(guò)URT出行，只得選乘其它公共交通方式?？紤]URT與其它公共交通方式舒適度的差異，本文為該部分乘客統(tǒng)一定義一個(gè)出行擁擠度。綜上所述，修復(fù)完成后出行擁擠度最小目標(biāo)函數(shù)為

(3)

2.2.3 約束條件

在URT區(qū)間失效修復(fù)模型中，根據(jù)約束條件的類型可將約束條件分為三類。第一類為決策變量約束，如式(4)-(5)所示；第二類為修復(fù)約束，如式(6)-(8)所示；第三類為出行需求約束，如式(9)-(11)所示。

(4)

(5)

(6)

(7)

T0+Tm+m=Ttotal

(8)

(9)

(10)

(11)

2.3 修復(fù)效果評(píng)價(jià)

Bruneau等人所提出的彈性損失三角形常用于衡量系統(tǒng)應(yīng)對(duì)突發(fā)事件的能力。本文對(duì)彈性損失三角形進(jìn)行了改進(jìn)，結(jié)果如圖1所示，圖中黑色部分面積即為系統(tǒng)的彈性損失，由式(12)計(jì)算得到。一般而言，彈性損失越小，所對(duì)應(yīng)的修復(fù)策略越優(yōu)，因此本文以系統(tǒng)彈性損失Lv為指標(biāo)來(lái)衡量修復(fù)策略的有效性。

圖1 彈性三角形

(12)

式中，t0及tm分別表示URT網(wǎng)絡(luò)的失效時(shí)刻及修復(fù)完成時(shí)刻；V(t)為客運(yùn)量，為時(shí)間的函數(shù)；V0為正常運(yùn)營(yíng)情況下的全網(wǎng)客運(yùn)量。

3 求解算法

上述模型為多目標(biāo)0-1規(guī)劃問(wèn)題，是典型的NP-hard問(wèn)題，難以找到唯一最優(yōu)解，只能找到非劣解集。帶精英策略的快速非支配排序遺傳算法(Non-Dominated Sorting Genetic Algorithm，NSGA-II)具有收斂快、結(jié)果準(zhǔn)確的優(yōu)點(diǎn)，適用于求解多目標(biāo)0-1規(guī)劃問(wèn)題。因此，本文采用NSGA-II算法對(duì)上述模型進(jìn)行求解，使用NSGA-II算法求解該模型的步驟為：

Step1：染色體編碼與解碼

圖2 編碼示意圖

Step2：種群排序

采用快速非支配排序及個(gè)體間的擁擠度對(duì)個(gè)體進(jìn)行排序，定義個(gè)體間擁擠度為目標(biāo)函數(shù)之間的距離。根據(jù)個(gè)體i所能支配的個(gè)體數(shù)di及能支配個(gè)體i的個(gè)體數(shù)dei實(shí)現(xiàn)對(duì)個(gè)體i的非支配排序；當(dāng)不同個(gè)體的非支配排序值相同時(shí)，則根據(jù)個(gè)體間的擁擠度對(duì)個(gè)體進(jìn)行排序。

Step3：選擇算子

采用二進(jìn)制競(jìng)標(biāo)賽的方式選擇優(yōu)秀個(gè)體。對(duì)個(gè)體進(jìn)行選擇時(shí)，選擇非支配排序等級(jí)低的個(gè)體；若兩個(gè)體的排序等級(jí)相同，則選擇擁擠度大的個(gè)體。

Step4：交叉和變異

采用隨機(jī)交叉及變異的方式實(shí)現(xiàn)染色體的交叉與變異。染色體的交叉與變異如圖3所示，染色體1與染色體2在a點(diǎn)交叉，染色體1在子串1的b處發(fā)生變異，染色體2在子串2的c和d處產(chǎn)生變異。對(duì)于子串2處的變異，為保證修復(fù)順序的唯一性，子串2染色體采用成對(duì)變異的形式，例如c與d處成對(duì)變異，c處變異為6，d處變異為2。

圖3 交叉及變異示意圖

Step5：精英策略

精英策略的目的在于保留父代的優(yōu)秀個(gè)體直接進(jìn)入子代，在降低計(jì)算復(fù)雜度的同時(shí)，還能最大限度保留優(yōu)秀個(gè)體不被淘汰。使用NSGA-II求解該模型的算法流程圖如圖4所示。

圖4 NSGA-II算法流程圖

4 實(shí)例應(yīng)用

4.1 杭州地鐵

杭州是浙江省省會(huì)、杭州都市圈的中心城市，杭州地鐵1號(hào)線于2012年11月開(kāi)通運(yùn)營(yíng)，標(biāo)志著杭州進(jìn)入了地鐵時(shí)代。截止2019年1月，杭州地鐵共開(kāi)通運(yùn)營(yíng)3條地鐵線路、81座站點(diǎn)及83個(gè)線路區(qū)間，運(yùn)營(yíng)線路里程達(dá)到117.72 km。2019年1月時(shí)杭州地鐵網(wǎng)絡(luò)如圖5所示。

圖5 杭州地鐵網(wǎng)絡(luò)圖(2019年1月)

本文從杭州地鐵獲得了2019年1月1日至25日，共25日的自動(dòng)售檢票(Automatic Fare Collection，AFC)數(shù)據(jù)，該組AFC數(shù)據(jù)包括乘客編號(hào)、乘客類型、進(jìn)出站刷卡時(shí)間等數(shù)據(jù)。在計(jì)算前先對(duì)該組AFC數(shù)據(jù)進(jìn)行了預(yù)處理：刪除了乘客類型為員工及進(jìn)站刷卡時(shí)間在運(yùn)營(yíng)時(shí)間以外(0:00-5:30)的AFC數(shù)據(jù)。此外，本文還從杭州地鐵獲得了列車(chē)運(yùn)行圖、站點(diǎn)換乘時(shí)間、站間距等數(shù)據(jù)。結(jié)合上述數(shù)據(jù)，分析了在隨機(jī)攻擊及蓄意攻擊情況下，杭州地鐵網(wǎng)絡(luò)區(qū)間的最優(yōu)修復(fù)策略問(wèn)題。

4.2 結(jié)果分析

運(yùn)用NSGA-II算法對(duì)本模型進(jìn)行求解前，需要設(shè)置相關(guān)參數(shù)。設(shè)置種群規(guī)模為50，最大遺傳代數(shù)為50，變異概率為0.1，交叉概率為0.9，攻擊區(qū)間數(shù)為8，維修資源總數(shù)為4，采用Matlab編程實(shí)現(xiàn)對(duì)該問(wèn)題的求解。利用Matlab計(jì)算得到隨機(jī)攻擊及蓄意攻擊的區(qū)間如表1所示(例：表中11-12表示武林廣場(chǎng)站-鳳起路站區(qū)間，其余編號(hào)類似)，在攻擊時(shí)令區(qū)間上下行均失效。

表1 隨機(jī)及蓄意攻擊區(qū)間

在運(yùn)行平臺(tái)為Intel(R)Core(TM)i7-8750H 2.20GHz CPU及運(yùn)行內(nèi)存為8.0G的計(jì)算機(jī)上對(duì)該模型進(jìn)行了求解，得到該模型的最優(yōu)Pareto解集。隨機(jī)及蓄意攻擊情況下的計(jì)算結(jié)果分別如圖6-(a)及圖6-(b)所示，圖6橫坐標(biāo)表示進(jìn)化代數(shù)，左縱坐標(biāo)為全日客運(yùn)量，右縱坐標(biāo)為乘客出行擁擠度的倒數(shù)。由圖6可得，兩個(gè)目標(biāo)函數(shù)的Pareto解集平均值迭代到一定次數(shù)后收斂，說(shuō)明算法在經(jīng)歷一定迭代次數(shù)后穩(wěn)定在最優(yōu)解集附近保持不變。

圖6 目標(biāo)函數(shù)平均解集進(jìn)化過(guò)程

根據(jù)進(jìn)化得到的Pareto解集，統(tǒng)計(jì)得到兩類優(yōu)化目標(biāo)下的計(jì)算結(jié)果如表2所示。對(duì)比分析表2可得，修復(fù)受損URT區(qū)間時(shí)，兩類修復(fù)目標(biāo)所修復(fù)的失效區(qū)間不同，客運(yùn)量最優(yōu)目標(biāo)傾向于修復(fù)網(wǎng)絡(luò)中的最重要區(qū)間，而擁擠度最優(yōu)目標(biāo)則傾向于修復(fù)不同線路的失效區(qū)間。

表2 隨機(jī)及蓄意攻擊受損區(qū)間最優(yōu)修復(fù)策略

結(jié)合Matlab編程實(shí)現(xiàn)受損網(wǎng)絡(luò)區(qū)間的平均修復(fù)及偏好修復(fù)，統(tǒng)計(jì)計(jì)算結(jié)果得到采用平均修復(fù)、偏好修復(fù)及URT區(qū)間失效修復(fù)模型的計(jì)算結(jié)果如圖7所示(圖中圖例：隨機(jī)-平均表示采用平均修復(fù)策略修復(fù)因隨機(jī)攻擊而失效的URT網(wǎng)絡(luò)，其余類似)。結(jié)合式(12)計(jì)算采用平均修復(fù)策略、偏好修復(fù)策略及URT區(qū)間失效修復(fù)模型修復(fù)因隨機(jī)攻擊而失效URT網(wǎng)絡(luò)的彈性損失分別為426036，447479及329548；修復(fù)因蓄意攻擊而失效URT網(wǎng)絡(luò)的彈性損失分別為289289，292489及286526。結(jié)合計(jì)算結(jié)果可得，相比于平均修復(fù)策略及偏好修復(fù)策略，采用本文所建立的URT區(qū)間失效修復(fù)模型能夠最大限度降低因區(qū)間受損而導(dǎo)致的乘客損失，減少因區(qū)間失效而導(dǎo)致的URT運(yùn)營(yíng)損失。

圖7 不同修復(fù)策略的修復(fù)進(jìn)程曲線

5 結(jié)論

本文以受損URT網(wǎng)絡(luò)全日客運(yùn)量最大、修復(fù)完成后乘客出行擁擠度最小為目標(biāo)，以修復(fù)能力、出行需求等為約束條件，建立URT區(qū)間失效修復(fù)模型，結(jié)合NSGA-II算法對(duì)該模型進(jìn)行了求解。與平均修復(fù)策略及偏好修復(fù)策略等常規(guī)策略對(duì)比發(fā)現(xiàn)，本文所建立的數(shù)學(xué)模型能更加有效修復(fù)因隨機(jī)攻擊和蓄意攻擊而失效網(wǎng)絡(luò)，降低因URT區(qū)間失效給乘客及管理部門(mén)而帶來(lái)的損失。