王志強(qiáng)， 王驍龍， 毛宇洋， 董忠濤， 劉文霞， 黃易君成

(新能源電力系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室(華北電力大學(xué))，北京 102206)

0 引 言

現(xiàn)代社會(huì)依靠電力不斷發(fā)展，漸漸地已難以脫離電力而存在，如通訊系統(tǒng)、醫(yī)療衛(wèi)生系統(tǒng)、交通信號系統(tǒng)等社會(huì)支撐力量離開電力供應(yīng)將難以正常運(yùn)行。然而，近年來地震、洪澇等自然災(zāi)害的頻發(fā)對電力系統(tǒng)造成不同程度的破壞，伴隨而來的便是巨大的損失[1]。災(zāi)害場景下電力應(yīng)急修復(fù)是降低損失的重要手段，其中電力應(yīng)急物資輸送是應(yīng)急修復(fù)基礎(chǔ)，因此如何在復(fù)雜災(zāi)害路況下結(jié)合多源信息優(yōu)化電力應(yīng)急物資輸送路徑對提高電力系統(tǒng)韌性具有重要意義。

針對災(zāi)害場景下應(yīng)急物資輸送的路徑規(guī)劃方法，眾多學(xué)者對其進(jìn)行了研究。文獻(xiàn)[2]考慮到應(yīng)急物資需求程度的差異，以總延遲時(shí)間最短、軟時(shí)間窗的懲罰成本最小和硬時(shí)間窗的不滿足個(gè)數(shù)最少為目標(biāo)構(gòu)建應(yīng)急物資車輛配送路徑規(guī)劃模型，規(guī)劃結(jié)果有效提高了物資配送效率。文獻(xiàn)[3]基于經(jīng)典Dijkstra算法，結(jié)合道路中斷概率對算法進(jìn)行改進(jìn)，不僅縮短了路徑運(yùn)輸時(shí)間而且提高了規(guī)劃結(jié)果的穩(wěn)定性。文獻(xiàn)[4]以運(yùn)輸時(shí)間、網(wǎng)絡(luò)可靠性和運(yùn)輸損耗為目標(biāo)，并考慮不同目標(biāo)優(yōu)先級，提出了災(zāi)后應(yīng)急救援運(yùn)輸路徑的多目標(biāo)隨機(jī)規(guī)劃方法。文獻(xiàn)[5]以路徑效用和連通可靠性為目標(biāo)建立雙層規(guī)劃模型，下層模型實(shí)現(xiàn)交通流分配，上層模型在下層目標(biāo)基礎(chǔ)上求取總目標(biāo)最優(yōu)，有效提高了應(yīng)急救援工作的響應(yīng)能力。上述文獻(xiàn)均基于已有地圖中的暢通道路進(jìn)行規(guī)劃，未充分利用具有通行潛力的潛在道路，并且未考慮道路搶修后投入使用對縮短輸送路徑通行時(shí)間的貢獻(xiàn)，導(dǎo)致物資輸送效率較低。

目前應(yīng)急物資輸送環(huán)節(jié)仍大范圍采用避開道路障礙的方式，但隨著通信網(wǎng)絡(luò)逐漸發(fā)達(dá)和大數(shù)據(jù)等新興技術(shù)的推進(jìn)，應(yīng)急部門和道路搶修部門聯(lián)系日益緊密，可實(shí)現(xiàn)道路搶修部門協(xié)助應(yīng)急部門開展應(yīng)急物資輸送工作，保證物資更快到達(dá)需求點(diǎn)。應(yīng)急路徑優(yōu)化中考慮破損道路搶修的研究已有部分成果。文獻(xiàn)[6]從占用物資、通行時(shí)間影響兩方面特性對損毀道路修復(fù)、臨時(shí)道路新修和較差道路平整三種修整工作進(jìn)行分析，并建立了道路修整與應(yīng)急車輛路徑的集成優(yōu)化模型。文獻(xiàn)[7]利用物資要素和時(shí)延要素之間的轉(zhuǎn)換，同時(shí)對路網(wǎng)結(jié)構(gòu)和車輛路徑進(jìn)行優(yōu)化。道路搶修包括搶修隊(duì)前往路障和路障修復(fù)兩個(gè)過程，上述文獻(xiàn)認(rèn)為只要搶修隊(duì)到達(dá)路障，道路就轉(zhuǎn)變?yōu)檫B通狀態(tài)，未考慮路障修復(fù)時(shí)間[8]。文獻(xiàn)[9]考慮應(yīng)急搶通導(dǎo)致交通線通過性變化可能帶來的影響，構(gòu)建了最優(yōu)救援路徑和最優(yōu)交通搶通方案雙層規(guī)劃模型。文獻(xiàn)[10]基于道路系統(tǒng)抗震性預(yù)測，考慮震后不同階段的道路搶修時(shí)間，提出了一種震后最優(yōu)運(yùn)輸路徑選擇方法。上述兩個(gè)文獻(xiàn)考慮了路障修復(fù)時(shí)間，但未給出具體計(jì)算方法。實(shí)際場景中，一般由偵察人員依據(jù)現(xiàn)場情況一次性給定路障修復(fù)時(shí)間，但因?yàn)椴煌瑐刹槿藛T在經(jīng)驗(yàn)，認(rèn)知等方面存在差異，使得判定結(jié)果因人而異，具有明顯的主觀性，并且此種方式中不良判定結(jié)果會(huì)導(dǎo)致規(guī)劃結(jié)果產(chǎn)生較大偏差，魯棒性較差，因此需要一種準(zhǔn)確可靠的計(jì)算方法。

為此，考慮災(zāi)害場景下破損道路搶修的影響，本文提出一種計(jì)及潛在道路、路障修復(fù)時(shí)間不確定性的電力應(yīng)急物資輸送路徑優(yōu)化方法。首先，基于單兵軌跡信息，建立了軌跡點(diǎn)的道路匹配模型，并基于匹配結(jié)果給出潛在道路的篩選連接方法，得到計(jì)及潛在道路的應(yīng)急增廣電子地圖生成方法；其次，基于增廣電子地圖，并考慮物資輸送過程中對破損道路開展搶修工作，以期望通行時(shí)間最短為主要目標(biāo)、路徑長度最短為次要目標(biāo)建立電力應(yīng)急物資輸送路徑優(yōu)化模型，其中為增強(qiáng)判定結(jié)果的魯棒性，并削弱路障修復(fù)時(shí)間的傳統(tǒng)判定方式的主觀性，提出基于模糊理論的路障修復(fù)時(shí)間估算和物資輸送路徑期望通行時(shí)間計(jì)算方法；最后，利用改進(jìn)遺傳算法對所提模型進(jìn)行求解，并且對比分析了潛在道路、修復(fù)時(shí)間不確定性和破損道路搶修對規(guī)劃結(jié)果的影響，研究成果可以為災(zāi)害前期通信能力受限制的場景下進(jìn)行離線路徑規(guī)劃提供參考方案，可有效提高電力應(yīng)急物資輸送效率。

1 計(jì)及潛在道路的應(yīng)急增廣電子地圖生成方法

隨著社會(huì)的不斷發(fā)展，城市中封閉式小區(qū)大量出現(xiàn)，導(dǎo)致內(nèi)部綠化走廊面積隨之增加，同時(shí)小區(qū)圍墻的拆除可成為溝通內(nèi)部道路與外部道路的有效途徑，除此之外，各種運(yùn)動(dòng)場、停車場等場地的圍墻拆除也具有類似效果。視線轉(zhuǎn)至農(nóng)村，鄰里巷道、干涸農(nóng)田等具有通行潛力的場景眾多。以上所有場景可統(tǒng)稱為潛在道路，在災(zāi)害發(fā)生時(shí)經(jīng)過不同程度的修整、加固均可成為運(yùn)輸車輛通行的備選道路，進(jìn)而縮短路徑通行時(shí)間，其中潛在道路的發(fā)掘由單兵完成，潛在道路的修整、加固工作由運(yùn)輸隊(duì)利用隨行攜帶的工具完成。本文將潛在道路的修整、加固時(shí)間計(jì)入潛在道路的通行時(shí)間，不再額外設(shè)立時(shí)間量。

基于單兵的軌跡信息，本章從單兵軌跡點(diǎn)的道路匹配和潛在道路篩選添加兩個(gè)過程生成應(yīng)急增廣電子地圖，其中前者得到最佳匹配道路，后者依據(jù)匹配結(jié)果篩選出潛在道路上的軌跡點(diǎn)，并連接成軌跡添加至已有電子地圖上得到應(yīng)急增廣電子地圖。

1.1 基于HMM模型的單兵軌跡點(diǎn)的道路匹配

單兵軌跡點(diǎn)以經(jīng)緯度坐標(biāo)的形式呈現(xiàn)，分為潛在道路上的軌跡點(diǎn)和已有電子地圖的已有道路上的軌跡點(diǎn)兩類，分別是單兵于潛在道路和已有道路上采集返回的軌跡點(diǎn)。其中，潛在道路上的軌跡點(diǎn)與已有道路之間的距離較大；已有道路上的軌跡點(diǎn)由于定位精度、傳輸誤差等原因，與已有道路間同樣存在距離，區(qū)別在于誤差導(dǎo)致的距離較小[11]。道路匹配要解決的問題是在已知單兵軌跡的前提下，利用隱馬爾可夫模型(Hidden Markov Model, HMM)將單兵軌跡點(diǎn)均匹配到已有電子地圖，最后得到單兵軌跡點(diǎn)在已有電子地圖中匹配度最高的最佳匹配道路。

地圖匹配(Map Match, MM)技術(shù)是將采集得到的GPS點(diǎn)匹配到電子地圖中的一項(xiàng)技術(shù)，減小定位結(jié)果與電子地圖之間的差距[12]。HMM模型可以描述一個(gè)隱含未知參數(shù)的馬爾可夫過程，其中預(yù)測問題的求解可以應(yīng)用于MM技術(shù)，該問題已知可觀測狀態(tài)序列{Y1,Y2,…,Yi,…,Yn-1,Yn}、隱含狀態(tài)序列{X1,X2,…,Xi,…,Xn-1,Xn}之間的狀態(tài)轉(zhuǎn)移概率P(Ski+1∣Sji)和隱含狀態(tài)與可觀測狀態(tài)之間的觀測概率Q(Yi∣Sji)，其中隱含狀態(tài)Xi(={S1,S2,…,Sj,…,Sm-1,Sm})表示可能與可觀測狀態(tài)Yi關(guān)聯(lián)的隱含狀態(tài)[13]，預(yù)測問題通過求解可以得到概率最高的最優(yōu)隱含狀態(tài)序列。

本文基于HMM模型，考慮已有道路網(wǎng)絡(luò)的拓?fù)溥B接關(guān)系，建立了如圖1所示的道路匹配模型，其中可觀測狀態(tài)Yi表示第i個(gè)單兵軌跡點(diǎn)，隱含狀態(tài)Xi表示第i個(gè)單兵軌跡點(diǎn)可能匹配的每條道路Sj。

圖1 道路匹配模型Fig. 1 Road matching model

(1)

(2)

(3)

圖2 垂直距離和夾角示意圖Fig. 2 Schematic diagram of vertical distance and angle

其中，α、β分別表示垂直距離與方向夾角在匹配距離中的權(quán)重。

(1)初始化第一個(gè)可觀測狀態(tài)Y1的所有可能隱含狀態(tài)的概率，并設(shè)置對應(yīng)的前驅(qū)狀態(tài)為0；

(4)

(5)

(2)遞推計(jì)算其他可觀測狀態(tài)Yi的所有可能隱含狀態(tài)的概率及前驅(qū)狀態(tài)；

j=1,2,…,mi

(6)

j=1,2,…,mi

(7)

(3)比較最后一個(gè)可觀測狀態(tài)Yn的所有可能隱含狀態(tài)的概率，將概率最高的隱含狀態(tài)設(shè)為Yn對應(yīng)的最佳隱含狀態(tài)；

(4)根據(jù)所求的前驅(qū)狀態(tài)結(jié)果，找出前面所有可觀測狀態(tài)的最佳隱含狀態(tài)，即找到所有單兵軌跡點(diǎn)的最佳匹配道路[15]。

1.2 潛在道路的篩選及添加

基于匹配結(jié)果，并依據(jù)兩類單兵軌跡點(diǎn)與已有道路間的距離具有明顯差距的特征，篩選環(huán)節(jié)可以得到潛在道路上的軌跡點(diǎn)，連接后形成潛在道路的軌跡，最后通過添加環(huán)節(jié)將其添加至已有電子地圖中形成應(yīng)急增廣電子地圖。

文獻(xiàn)[11]的思想與本文類似，其中篩選環(huán)節(jié)設(shè)定一個(gè)閾值作為全局標(biāo)準(zhǔn)，并將垂直距離大于閾值的軌跡點(diǎn)設(shè)定為失配點(diǎn)，若失配點(diǎn)連續(xù)則判定為潛在道路上的軌跡點(diǎn)。本文考慮到對相隔較遠(yuǎn)的單兵軌跡點(diǎn)進(jìn)行定位和傳輸?shù)挠布顟B(tài)難以保持一致，使得軌跡點(diǎn)與真實(shí)位置之間的誤差具有明顯差距，因此通過將相鄰單兵軌跡點(diǎn)的匹配距離差值與允許相鄰軌跡點(diǎn)匹配距離差值ΔFlimit進(jìn)行對比得到失配點(diǎn)，并設(shè)定最小潛在道路長度Llimit，將連續(xù)數(shù)量大于Llimit的失配點(diǎn)最終判定為潛在道路上的軌跡點(diǎn)，從而去除了失配點(diǎn)中的匹配失誤點(diǎn)。

假設(shè)第一個(gè)單兵軌跡點(diǎn)為已有道路上的軌跡點(diǎn)，按如下步驟進(jìn)行篩選：

(1)計(jì)算各單兵軌跡點(diǎn)與最佳匹配道路間的匹配距離。

(2)按照時(shí)間順序，計(jì)算單兵軌跡點(diǎn)與上一軌跡點(diǎn)的匹配距離的差值，若差值小于ΔFlimit，則該單兵軌跡點(diǎn)與上一軌跡點(diǎn)同為已有道路上的軌跡點(diǎn)或失配點(diǎn)，否則與上一軌跡點(diǎn)屬性相反。

(3)針對失配點(diǎn)，若失配點(diǎn)的連續(xù)數(shù)量大于或等于Llimit，則這一部分失配點(diǎn)為潛在道路上的軌跡點(diǎn)，否則為匹配失誤點(diǎn)。

篩選得到潛在道路上的軌跡點(diǎn)集合后，先將潛在道路上的軌跡點(diǎn)按時(shí)間順序進(jìn)行連接，其次將兩端的連接點(diǎn)垂直投影到最佳匹配道路上，最后將潛在道路的軌跡與連接點(diǎn)相連接即可形成應(yīng)急增廣電子地圖。

2 基于增廣地圖的電力應(yīng)急物資輸送路徑優(yōu)化方法

2.1 考慮修復(fù)時(shí)間不確定性的應(yīng)急輸送路徑優(yōu)化模型

假設(shè)G=(E，V，W)是基于應(yīng)急增廣電子地圖并根據(jù)單兵采集信息抽象出來的路網(wǎng)結(jié)構(gòu)。E表示G中的節(jié)點(diǎn)集合(E={i1，…，in})，包含正常道路節(jié)點(diǎn)和路障節(jié)點(diǎn)兩部分；V表示G中的邊集合({i，j}∈V)，具體為節(jié)點(diǎn)之間的路段，在本文中稱為“道路”；W表示V的權(quán)重集合(wij∈W)，若邊{i，j}連通，則wij為道路的通行時(shí)間，具體為道路長度與運(yùn)輸車輛速度的商，其中考慮到災(zāi)害場景的緊急性，運(yùn)輸車輛速度設(shè)置為限速值，具體數(shù)值由單兵根據(jù)現(xiàn)場情況給定。

模型中其他參數(shù)和變量定義如下：

L1為運(yùn)輸出發(fā)點(diǎn)O到需求點(diǎn)D的某一物資輸送路徑，由道路的有序序列構(gòu)成，R1為L1的集合；Xij為一個(gè)二元變量，當(dāng)?shù)缆穥i，j}包含在當(dāng)前考慮路徑L1中，取值為1，否則為0；ti為運(yùn)輸隊(duì)到達(dá)但未通過節(jié)點(diǎn)i的時(shí)刻，Ti(ti)為ti情況下，運(yùn)輸隊(duì)通過節(jié)點(diǎn)i的通行時(shí)間，其中正常道路節(jié)點(diǎn)的通行時(shí)間為0，路障節(jié)點(diǎn)的通行時(shí)間如式(9)所示；t0為運(yùn)輸隊(duì)的出發(fā)時(shí)刻；Tmax為需求點(diǎn)要求運(yùn)輸隊(duì)的最晚到達(dá)時(shí)間。

實(shí)際中難以保證運(yùn)輸隊(duì)和搶修隊(duì)于同一時(shí)刻出發(fā)，本文假設(shè)各搶修隊(duì)于零時(shí)刻出發(fā)，運(yùn)輸隊(duì)稍后再出發(fā)。應(yīng)急輸送路徑優(yōu)化模型綜合道路的通行時(shí)間(wijXij)和節(jié)點(diǎn)的通行時(shí)間(TiXij)得到路徑期望通行時(shí)間(具體計(jì)算方法見2.1.3)，并以此為主要目標(biāo)，求取期望通行時(shí)間最短的最優(yōu)輸送路徑(Popt)。模型具體數(shù)學(xué)形式如式(8-12)所示，其中式(8)、(9)為目標(biāo)函數(shù)，式(10-12)為約束條件。

(8)

Ti(ti)=max(T1i+T2i-ti,0)

(9)

s.t.

(10)

i,j=1,2,…,n,i≠j

(11)

(12)

式(9)中，T1i為搶修隊(duì)從搶修出發(fā)點(diǎn)到達(dá)路障i的時(shí)間，具體計(jì)算方法見2.1.1；T2i為搶修隊(duì)修復(fù)路障i所需要的時(shí)間，具體計(jì)算方法見2.1.2。

式(10)是不成環(huán)約束，限制運(yùn)輸隊(duì)出發(fā)點(diǎn)O和物資需求點(diǎn)D不重合；式(11)是節(jié)點(diǎn)約束，保證道路兩端節(jié)點(diǎn)i、j不重合；式(12)是硬時(shí)間窗約束，保證路徑的期望通行時(shí)間不大于Tmax。

式(9)中，若路障i的T1i+T2i較長，不同輸送路徑到達(dá)該路障時(shí)均需要等待，通過該路障均需要時(shí)長ti+Ti=ti+(T1i+T2i-ti)=T1i+T2i，可能導(dǎo)致不同輸送路徑的期望通行時(shí)間相同，此時(shí)應(yīng)以通行成本最低，即路徑長度最短為次要目標(biāo)，選出最優(yōu)輸送路徑。

2.1.1 搶修隊(duì)前往路障的時(shí)間T1i

針對T1i的計(jì)算，本文做出以下假設(shè)：

(1)各備選搶修出發(fā)點(diǎn)擁有足夠搶修力量，可在零時(shí)刻向各待修路障派遣充足的搶修力量。

(2)各路障與兩端最近的道路交叉口之間無其他路障存在，進(jìn)而搶修隊(duì)伍可以到達(dá)路障。

(13)

s.t.

(14)

p,q=1,2,…,n,p≠q

(15)

(16)

2.1.2 基于模糊關(guān)系理論的路障修復(fù)時(shí)間T2i的估算方法

以往一般由偵察人員一次性給定路障修復(fù)時(shí)間，但由于偵察人員在經(jīng)驗(yàn)和對事物認(rèn)知等方面存在差異，導(dǎo)致得到的結(jié)果具有明顯的主觀性。本文基于多名單兵及專家的綜合判定信息，利用模糊理論中模糊關(guān)系的相關(guān)知識(shí)進(jìn)行路障修復(fù)時(shí)間估算，保證估算結(jié)果可以較準(zhǔn)確反映路障真實(shí)情況，從而提高路徑規(guī)劃結(jié)果的可靠性[16]。

設(shè)論域U={u1,u2,…,ui,…,uf}，其中ui代表第i個(gè)路障；V={v1,v2,…,vj,…,vg}，其中vj代表第j個(gè)路障修復(fù)時(shí)間，建立直積U×V={(u,v)∣u∈U,v∈V}，并定義其中一個(gè)模糊子集R，即U到V的一個(gè)模糊關(guān)系，該關(guān)系具體描述為“修復(fù)路障ui需要時(shí)間vj”。關(guān)系程度由隸屬函數(shù)R：U×V→[0,1]刻畫，可表示為表1所示的模糊矩陣的形式，其中bij表示(ui,vj)對模糊子集R的隸屬度。

表1 模糊矩陣BTab.1 Fuzzy matrix B

本文采用模糊統(tǒng)計(jì)法來確定隸屬度，該方法基于模糊統(tǒng)計(jì)試驗(yàn)進(jìn)行，試驗(yàn)步驟如下[17]：

(1)組織統(tǒng)計(jì)小組，要求統(tǒng)計(jì)小組的成員對模糊子集R的概念熟悉，并有用數(shù)量近似表達(dá)模糊概念的能力。

(2)針對直積U×V中某一個(gè)元素(ui,vj)，每一個(gè)小組成員基于認(rèn)知進(jìn)行試驗(yàn)，判別該元素是否隸屬于模糊子集R。

(3)統(tǒng)計(jì)結(jié)果，按式(17)計(jì)算(ui,vj)的隸屬度bij。

(17)

(4)重復(fù)步驟2、3，計(jì)算U×V中每個(gè)元素的隸屬度。

為保證試驗(yàn)結(jié)果的可靠性，試驗(yàn)總次數(shù)必須充足，因此設(shè)計(jì)統(tǒng)計(jì)小組由前方單兵和后方專家共同構(gòu)成，其中后方專家通過前方傳回的路障圖片來進(jìn)行判定試驗(yàn)。鑒于前方單兵基于現(xiàn)場情況進(jìn)行試驗(yàn)，結(jié)果可信度高，因此給予單兵特殊的權(quán)重Q，并采用式(18)進(jìn)行隸屬度計(jì)算。

(18)

式中：P1ij、P2ij分別是單兵和專家判定“(ui,vj)∈R”的次數(shù)；N1ij、N2ij分別是單兵和專家針對元素(ui,vj)的判定次數(shù)。

由于時(shí)間緊迫性，實(shí)際中每個(gè)統(tǒng)計(jì)小組成員針對某個(gè)路障僅會(huì)給出一個(gè)修復(fù)時(shí)間，因此可以簡化試驗(yàn)：每個(gè)小組成員針對每個(gè)路障僅進(jìn)行一次試驗(yàn)，每次試驗(yàn)基于自我認(rèn)知給出路障ui的修復(fù)時(shí)間vj。在統(tǒng)計(jì)試驗(yàn)結(jié)果時(shí)，試驗(yàn)(ui,vj)的結(jié)果為“(ui,vj)∈R”，而路障ui與其他時(shí)間vy的試驗(yàn)(例如(ui,vy)，yj)的結(jié)果為“(ui,vy)不屬于R”。

除此之外，考慮到部分修復(fù)時(shí)間對應(yīng)的可能性過小，設(shè)置最小可能性bmin達(dá)到縮小修復(fù)時(shí)間集合的效果。

2.1.3 電力應(yīng)急物資輸送路徑期望通行時(shí)間的計(jì)算方法

由于修復(fù)時(shí)間的不確定性，每一條運(yùn)輸出發(fā)點(diǎn)O到需求點(diǎn)D的物資輸送路徑(L1)的通行時(shí)間具有多種可能性，本文設(shè)置每一種可能的通行時(shí)間對應(yīng)一條時(shí)空路徑，即將每條輸送路徑依據(jù)可能的通行時(shí)間劃分為多條時(shí)空路徑[18]。

已知路網(wǎng)結(jié)構(gòu)G中的邊V的權(quán)重W和T1i、T2i，針對某一條輸送路徑，首先計(jì)算每條時(shí)空路徑對應(yīng)的通行時(shí)間及其可能性，然后將每條時(shí)空路徑的通行時(shí)間進(jìn)行線性加權(quán)得到該輸送路徑的期望通行時(shí)間。具體步驟如下：

(1)計(jì)算時(shí)空路徑的通行時(shí)間：

1)首先按式(19)計(jì)算輸送路徑上的第二個(gè)節(jié)點(diǎn)的到達(dá)(但未通過)時(shí)間：

t2(t0)=t0+w12

(19)

2)逐一處理其他每一個(gè)節(jié)點(diǎn)i，判斷上一節(jié)點(diǎn)的節(jié)點(diǎn)類型，并采取如下對應(yīng)的計(jì)算方式：

①若為路障節(jié)點(diǎn)：由于某條時(shí)空路徑在計(jì)算各路障修復(fù)時(shí)間時(shí)均只取定一種可能的情況，因此在取定的修復(fù)時(shí)間下，將搶修隊(duì)到達(dá)路障節(jié)點(diǎn)i-1的時(shí)間T1(i-1)、路障節(jié)點(diǎn)i-1的修復(fù)時(shí)間u(i-1)和路障節(jié)點(diǎn)i-1的到達(dá)時(shí)間ti-1依據(jù)式(9)計(jì)算得到路障節(jié)點(diǎn)i-1的通行時(shí)間Ti-1，再加上路障節(jié)點(diǎn)i-1的到達(dá)時(shí)間ti-1和兩節(jié)點(diǎn)之間的通行時(shí)間W(i-1)i，即可得到節(jié)點(diǎn)i的到達(dá)時(shí)間ti，如式(20)所示：

(20)

式中：u(i-1)1表示路障i-1的第1種可能的修復(fù)時(shí)間；mj表示路障節(jié)點(diǎn)j可能的修復(fù)時(shí)間數(shù)目。

②若為正常道路節(jié)點(diǎn)：將上一節(jié)點(diǎn)的到達(dá)時(shí)間ti-1加上兩節(jié)點(diǎn)之間的道路通行時(shí)間W(i-1)i作為節(jié)點(diǎn)i的到達(dá)時(shí)間ti，如式(21)所示：

ti(to)=ti-1(to)+W(i-1)i

(21)

3)將物資需求點(diǎn)D的到達(dá)時(shí)間作為該條時(shí)空路徑的通行時(shí)間。依據(jù)以上步驟可計(jì)算每條時(shí)空路徑的通行時(shí)間。

(2)計(jì)算時(shí)空路徑的可能性：

物資輸送路徑通行時(shí)間的不確定性是由路障修復(fù)時(shí)間的不確定性引起的，因此時(shí)空路徑的可能性由路障修復(fù)時(shí)間的可能性決定。本文比較輸送路徑中所有路障節(jié)點(diǎn)在某條時(shí)空路徑中所取定修復(fù)時(shí)間對應(yīng)的可能性，將最小值作為時(shí)空路徑的可能性。其中存在部分時(shí)空路徑的通行時(shí)間相同的情況，僅需將其合并，可能性取最大值。

(3)計(jì)算各時(shí)空路徑的權(quán)重wj：

式中：γk表示第k條時(shí)空路徑的可能性；N表示某條輸送路徑對應(yīng)時(shí)空路徑的數(shù)目。

(4)計(jì)算輸送路徑的期望通行時(shí)間：

(23)

式中：Ts表示第s條時(shí)空路徑的通行時(shí)間。

2.2 求解方法

2.2.1 求解算法

由式(9)可知，電力應(yīng)急物資輸送路徑優(yōu)化模型中，節(jié)點(diǎn)i的通行時(shí)間Ti與到達(dá)節(jié)點(diǎn)i的時(shí)間ti有關(guān)，即與運(yùn)輸隊(duì)在節(jié)點(diǎn)i前方的通行情況有關(guān)，導(dǎo)致Dijkstra[19]、Floyd[20]等經(jīng)典最短路徑算法難以適用，因此本文選用遺傳算法進(jìn)行模型求解，將路徑的節(jié)點(diǎn)序列設(shè)為染色體，其中的節(jié)點(diǎn)編號設(shè)為基因，進(jìn)而通過比較一部分備選路徑獲得整個(gè)道路網(wǎng)絡(luò)的最優(yōu)輸送路徑。

實(shí)際道路網(wǎng)絡(luò)中節(jié)點(diǎn)眾多，但與節(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)較少，屬于大型稀疏網(wǎng)絡(luò)，經(jīng)典遺傳算法無規(guī)律生成的種群大部分為無效路徑，即路徑的節(jié)點(diǎn)在實(shí)際道路網(wǎng)絡(luò)中存在不相連的情況。為保證種群中均為有效路徑，進(jìn)而提高收斂速度，本文基于文獻(xiàn)[21]提出的改進(jìn)遺傳算法，結(jié)合模型特征對經(jīng)典遺傳算法作了如下改進(jìn)：

(1)基于可行性約束的初始種群生成：從起點(diǎn)開始逐一確定路徑節(jié)點(diǎn)，通過搜索鄰接矩陣并從關(guān)聯(lián)節(jié)點(diǎn)中隨機(jī)選取的方法確定，路徑生成后檢測路徑可行性及是否與已生成初始種群重合。

(2)基于父代染色體重合特性的交叉算子：若父代染色體有重合基因，通過重合基因進(jìn)行交叉。若父代染色體不具有重合基因，各隨機(jī)選取一個(gè)基因進(jìn)行交叉，如果子代染色體交叉處的兩節(jié)點(diǎn)沒有相連，則在不涉及子代染色體其他節(jié)點(diǎn)的前提下，按初始種群生成方法生成兩節(jié)點(diǎn)之間的有效子路徑并修正子代染色體。

(3)刪減式變異算子：隨機(jī)選取一個(gè)基因刪除，如果子代染色體中刪除位置前后的兩節(jié)點(diǎn)沒有相連，生成有效子路徑進(jìn)行修正。

除此之外，對于搶修隊(duì)前往路障的時(shí)間T1i的計(jì)算同樣采用本文所提遺傳算法，其中適應(yīng)度函數(shù)設(shè)置為搶修出發(fā)點(diǎn)到路障的路徑通行時(shí)間。

2.2.2 求解過程

本文依據(jù)如圖3所示的流程對電力應(yīng)急物資輸送路徑優(yōu)化模型進(jìn)行求解。

圖3 電力應(yīng)急物資輸送路徑優(yōu)化方法流程圖Fig. 3 Flow diagram of transportation path optimization method of power emergency supplies

3 算例分析

3.1 仿真系統(tǒng)與參數(shù)

由于本文提出的電力應(yīng)急物資輸送路徑優(yōu)化方法依賴于單兵從災(zāi)害現(xiàn)場采集的信息，已有案例中難于找到完整的數(shù)據(jù)，因此本文首先擬定如表2所示的8條單兵探測軌跡(紅色標(biāo)記節(jié)點(diǎn)為路障，方框標(biāo)記的道路為潛在道路)，并在文獻(xiàn)[8]構(gòu)建的道路網(wǎng)絡(luò)基礎(chǔ)上添加探測軌跡中的潛在道路得到如圖4所示的應(yīng)急增廣道路網(wǎng)絡(luò)。

表2 單兵探測軌跡及模糊統(tǒng)計(jì)試驗(yàn)結(jié)果(單兵)Tab.2 Soldier tracks and its fuzzy statistical test results

表2中包含了關(guān)于路障修復(fù)時(shí)間的單兵判定結(jié)果，判定結(jié)果由括號中的數(shù)值表示。與之相對應(yīng)的專家判定結(jié)果如表3所示。

表3 模糊統(tǒng)計(jì)試驗(yàn)結(jié)果(專家)Tab.3 Fuzzy statistical test results(expert)

應(yīng)急增廣道路網(wǎng)絡(luò)中，已有道路通行時(shí)間如表4所示，潛在道路通行時(shí)間(包含潛在道路修整、加固時(shí)間)如表5所示。

求解算例的改進(jìn)遺傳算法采用Matlab腳本程序?qū)崿F(xiàn)，其中設(shè)置交叉率為0.8，變異率為0.3，最大迭代次數(shù)為50，種群規(guī)模為300。

3.2 算例結(jié)果與分析

基于單兵和專家的判定結(jié)果，采用模糊統(tǒng)計(jì)法，可得到如表6所示的路障修復(fù)時(shí)間估算結(jié)果。

結(jié)合搶修隊(duì)到達(dá)路障的時(shí)間計(jì)算得到輸送路徑的期望通行時(shí)間，并采用所提改進(jìn)遺傳算法求解得到如表7所示的最優(yōu)應(yīng)急物資輸送方案。

表4 已有道路通行時(shí)間Tab.4 Travel time of existing road

表5 潛在道路通行時(shí)間Tab.5 Travel time of potential road

圖4 應(yīng)急增廣道路網(wǎng)絡(luò)Fig. 4 Emergency augmented road network

表6 路障修復(fù)時(shí)間估算結(jié)果Tab.6 Estimated repair barricades time

表7 電力應(yīng)急物資輸送路徑規(guī)劃結(jié)果

結(jié)果顯示，最優(yōu)輸送路徑為[1-13-2-3-31-4-5- 42-6-54-55-51-9-48-10-40-33-11-53-12](已在圖4中標(biāo)注)，期望通行時(shí)間為29.28 h，路徑長度為26.31 v(v表示平均車速)。

分析結(jié)果的過程中發(fā)現(xiàn)，存在與最優(yōu)輸送路徑類似的輸送路徑，即[1-2-3-31-4-5-42-6-54-55- 51-9-48-10-40-33-11-53-12]，期望通行時(shí)間比最優(yōu)輸送路徑略多0.000 5 h，原因在于：子路徑[1-2-3- 31]的通行時(shí)間為10.54 h，搶修隊(duì)到達(dá)路障31需要8.52 h，由表6可知路障31的修復(fù)時(shí)間可能為2 h，8.52+2=10.52<10.54，運(yùn)輸隊(duì)可直接通過路障，通過時(shí)間為10.54 h；最優(yōu)輸送路徑的子路徑[1-13-2-3-31]的通行時(shí)間為8.71 h，由于8.52+2 =10.52>8.71，運(yùn)輸隊(duì)需要等待路障31修復(fù)完成后方可通過，通過時(shí)間為10.52 h，這種可能情況下的差別導(dǎo)致兩條輸送路徑在期望通行時(shí)間上存在微小差距。除此之外，最優(yōu)輸送路徑的路徑長度少1.83 v，能有效降低運(yùn)輸車輛的通行成本。

3.3 潛在道路對輸送效率的影響

為分析潛在道路對物資輸送效率的影響，本文基于控制變量的思想設(shè)計(jì)對比場景1，該場景不再考慮潛在道路，道路網(wǎng)絡(luò)對應(yīng)于刪去虛線道路和節(jié)點(diǎn)后的圖4，并在模型求解時(shí)將遺傳算法的種群規(guī)模設(shè)置為150。對比場景1的規(guī)劃結(jié)果如表8所示。

表8 對比場景1的規(guī)劃結(jié)果Tab.8 Optimization result of contrast scenario 1

對比場景1的最優(yōu)輸送路徑為[1-13-2-3-31-4 -5-6-32-7-8-9-10-33-11-12]，期望通行時(shí)間為 30.61 h，路徑長度為26.74 v。與表7中算例的最優(yōu)輸送路徑對比可知，潛在道路使得期望通行時(shí)間減少了1.33 h，路徑長度減少了0.43 v，輸送效率提高了4.34%，可更有效地保證電力應(yīng)急物資的快速送達(dá)，并且可以節(jié)約一部分通行成本。

其中，潛在道路對路障的搶修路徑同樣具有優(yōu)化作用。算例中路障32的搶修路徑為[23-39-9- 51-55-54-32]，通行時(shí)間為6.58 h；對比場景1中路障32的搶修路徑為[23-9-8-7-32]，通行時(shí)間為6.95 h。

通過對比可知，潛在道路54-55使得搶修隊(duì)到達(dá)路障32的時(shí)間縮短了0.37 h，進(jìn)而加快道路搶修進(jìn)度，使得運(yùn)輸隊(duì)更快通過路障32，可能達(dá)到縮短輸送路徑通行時(shí)間的效果。

3.4 修復(fù)時(shí)間不確定性對規(guī)劃結(jié)果特性的影響

為分析考慮修復(fù)時(shí)間不確定性的效果，本文基于控制變量的思想設(shè)計(jì)對比場景2，該場景中各路障的修復(fù)時(shí)間取可能性最大的情況，即不考慮修復(fù)時(shí)間不確定性。對比場景2的規(guī)劃結(jié)果如表9所示。

表9 對比場景2的規(guī)劃結(jié)果Tab.9 Optimization result of contrast scenario 2

為分析修復(fù)時(shí)間不確定性對規(guī)劃結(jié)果魯棒性的影響，本文設(shè)置算例的對比試驗(yàn)，試驗(yàn)將某個(gè)單兵針對路障31的判定結(jié)果改為6 h(由表6可知6 h為不良判定結(jié)果)，得到如表10所示的試驗(yàn)結(jié)果。同時(shí)設(shè)置對比場景2的對比試驗(yàn)，試驗(yàn)將路障31的修復(fù)時(shí)間改為6 h，得到如表11所示的試驗(yàn)結(jié)果。

表10 算例的對比試驗(yàn)結(jié)果Tab.10 Result of contrast test of example

表11 對比場景2的對比試驗(yàn)結(jié)果Tab.11 Result of contrast test of contrast scenario 2

對比表7與表10可知，不良判定結(jié)果使得算例最優(yōu)輸送路徑的期望通行時(shí)間由29.28 h增加至29.36 h，改變了0.08 h；對比表9與表11可知，不良判定結(jié)果不僅改變了對比場景1的最優(yōu)輸送路徑，并且通行時(shí)間由29.12 h增加至29.82 h，改變了0.7 h。

由上述分析可知：考慮修復(fù)時(shí)間不確定性可以減輕不良判定結(jié)果的影響，增強(qiáng)規(guī)劃結(jié)果的魯棒性，進(jìn)而降低對單兵的要求。除此之外，模糊統(tǒng)計(jì)法判定修復(fù)時(shí)間的過程中征求多人意見，降低了傳統(tǒng)判定過程的主觀性。

3.5 破損道路搶修對輸送效率的影響

若不考慮破損道路搶修，本文設(shè)置算例的對比試驗(yàn)2，得到最優(yōu)輸送路徑為[1-14-16-20-24-57- 30-41-12]，通行時(shí)間為35.91 h。與表7中最優(yōu)輸送路徑相比，期望通行時(shí)間增加了6.63 h，破損道路搶修使得輸送效率提升了18.46%。

因此應(yīng)急部門應(yīng)加強(qiáng)與道路搶修部門的合作，共同保證電力應(yīng)急物資快速到達(dá)災(zāi)害現(xiàn)場。

4 結(jié) 論

為保證電力應(yīng)急物資快速送達(dá)災(zāi)害現(xiàn)場，進(jìn)而促進(jìn)電力供應(yīng)快速恢復(fù)，降低災(zāi)害給電力系統(tǒng)及社會(huì)帶來的損失，本文首先基于單兵軌跡信息提出計(jì)及潛在道路的應(yīng)急增廣電子地圖生成方法，然后基于增廣電子地圖，并考慮物資輸送過程中對破損道路開展搶修工作，以期望通行時(shí)間最短為主要目標(biāo)、路徑長度最短為次要目標(biāo)建立電力應(yīng)急物資輸送路徑優(yōu)化模型，同時(shí)提出基于模糊理論的路障修復(fù)時(shí)間估算和物資輸送路徑期望通行時(shí)間計(jì)算方法，并利用改進(jìn)遺傳算法對模型進(jìn)行求解。通過算例分析，得到以下結(jié)論：

(1)充分利用潛在道路不僅可以縮短路障搶修路徑的通行時(shí)間，進(jìn)一步還明顯縮短了電力應(yīng)急物資輸送路徑的期望通行時(shí)間。

(2)綜合單兵和專家判定結(jié)果的方式考慮修復(fù)時(shí)間不確定性是可行且有效的，規(guī)劃結(jié)果可以容納少數(shù)不良判定結(jié)果，提高魯棒性，降低對單兵的要求，并且削弱了傳統(tǒng)判定過程的主觀性。

(3)破損道路搶修可明顯縮短物資輸送路徑的通行時(shí)間，隨著數(shù)據(jù)透明化和各相關(guān)部門聯(lián)系緊密化，應(yīng)該鼓勵(lì)此種處理方式由理論走向?qū)嶋H，更大程度保證應(yīng)急物資快速到達(dá)物資需求點(diǎn)。

在災(zāi)害前期通信能力受限的場景中，本文所提方法可以給應(yīng)急部門提供參考方案，為快速恢復(fù)供電準(zhǔn)備快速可靠的物資輸送路徑。