譚中楠,曹明月,郭 飛

(1.河南省交通運(yùn)輸發(fā)展集團(tuán)有限公司鄭州分公司,河南 鄭州 450000；2.河南北斗衛(wèi)星導(dǎo)航平臺(tái)有限公司,河南 鄭州 450003)

0 引言

近年來,以計(jì)算機(jī)、網(wǎng)絡(luò)、通信、大數(shù)據(jù)、物聯(lián)網(wǎng)等技術(shù)為支撐[1-3],高速公路智能管理系統(tǒng)[4-5]得到了迅速發(fā)展。然而,直到目前為止,我國公路管理水平與事故處理速度仍無法滿足人們的需求,道路擁堵和交通事故頻發(fā)現(xiàn)象十分嚴(yán)重。

為此,有研究將物聯(lián)網(wǎng)、云計(jì)算引入智能交通系統(tǒng)[6-7]，從而改善高速公路信息收集不準(zhǔn)確和未及時(shí)反饋的問題。文獻(xiàn)[8]基于物聯(lián)網(wǎng)技術(shù)對(duì)隧道洞口結(jié)冰動(dòng)態(tài)監(jiān)測技術(shù)進(jìn)行研究。文獻(xiàn)[9]設(shè)計(jì)了基于故障狀態(tài)演化的高速公路機(jī)電設(shè)備智能維護(hù)系統(tǒng),實(shí)現(xiàn)高速公路機(jī)電設(shè)備故障檢測。文獻(xiàn)[10]基于深度學(xué)習(xí)方法搭建了高速公路智能監(jiān)控分析平臺(tái)。然而,上述研究主要是對(duì)歷史數(shù)據(jù)進(jìn)行分析,對(duì)事故處理及資源調(diào)度等方面的研究較少。目前,在解決突發(fā)事件應(yīng)急資源調(diào)度方案的構(gòu)建問題時(shí),主要采用優(yōu)化建模方法。主流的優(yōu)化建模方法有分層序列法[11]、遺傳算法[12-13]等。然而,目前多目標(biāo)優(yōu)化算法在處理3個(gè)以上的目標(biāo)函數(shù)時(shí)仍存在很多問題。首先,優(yōu)化目標(biāo)數(shù)量的增加導(dǎo)致種群中非支配解的比例增加,從而降低求解效率；其次,在高維目標(biāo)空間中,保持多樣性指數(shù)的計(jì)算復(fù)雜度過高；最后,在高維對(duì)象空間的情況下,復(fù)合算子的搜索效率較低。

考慮到高速公路資源調(diào)度管理時(shí)效性要求,本文將處理高速公路應(yīng)急事件資源調(diào)度問題轉(zhuǎn)化為多目標(biāo)優(yōu)化問題,并提出利用改進(jìn)的多目標(biāo)優(yōu)化算法實(shí)現(xiàn)資源的最優(yōu)調(diào)度方案。該方案充分結(jié)合非支配排序遺傳算法(non-dominated sorting gentic algorithm,NSGA-Ⅲ)和高斯估算法優(yōu)點(diǎn)，可有效解決高速公路應(yīng)急處理與資源調(diào)度多目標(biāo)優(yōu)化問題。

1 處理與資源調(diào)度建模

考慮到高速公路緊急情況發(fā)生的不確定性,這些應(yīng)急事件可能發(fā)生在多個(gè)地點(diǎn)。同時(shí),由于緊急情況的關(guān)聯(lián)性,如極端事件(暴雪、臺(tái)風(fēng)、地震、洪水等),可能使許多潛在地點(diǎn)受到影響。因此,需要考慮災(zāi)難現(xiàn)場和潛在災(zāi)難現(xiàn)場的共同需求。這也導(dǎo)致資源調(diào)度模型的多目標(biāo)優(yōu)化特性。為最大化滿足高速公路災(zāi)難現(xiàn)場和潛在災(zāi)難現(xiàn)場資源調(diào)度需求，本文研究以最小化調(diào)度時(shí)間、調(diào)度成本、災(zāi)難現(xiàn)場損失和最小化潛在災(zāi)難現(xiàn)場不滿意度為目標(biāo)函數(shù),建立高速公路多目標(biāo)優(yōu)化模型。因此,該資源調(diào)度模型能夠最大程度地滿足現(xiàn)實(shí)生活中應(yīng)對(duì)突發(fā)事件的需求。

1.1 相關(guān)假設(shè)

為簡化計(jì)算,本文作如下假設(shè)。

①本文只考慮從1個(gè)救援站點(diǎn)到多個(gè)災(zāi)難站點(diǎn)和多個(gè)潛在災(zāi)難站點(diǎn)的場景。

②已知從救援現(xiàn)場到每個(gè)災(zāi)難現(xiàn)場的距離和資源調(diào)度的速度。

③每個(gè)災(zāi)難現(xiàn)場對(duì)不同資源的需求是已知的。

④在調(diào)度過程中,災(zāi)難現(xiàn)場的調(diào)度成本和每個(gè)資源的損失是已知的。

1.2 優(yōu)化模型

資源調(diào)度模型目標(biāo)函數(shù)如式(1)所示。

(1)

式中：f1(X)為最小化調(diào)度時(shí)間目標(biāo)函數(shù)；f2(X)為最小化調(diào)度成本目標(biāo)函數(shù)；f3(X)為最小化災(zāi)難現(xiàn)場損失目標(biāo)函數(shù)；f4(X)為最大化潛在災(zāi)難現(xiàn)場滿意度目標(biāo)函數(shù)。

式(1)顯示了應(yīng)急資源調(diào)度模型的總體優(yōu)化目標(biāo)。

(2)

式中：R1,R2,…,Rr為r個(gè)可調(diào)度的資源；N1,N2,…,Nn為n個(gè)災(zāi)難現(xiàn)場；ti(i=[1,N])為第i個(gè)資源的單位調(diào)度時(shí)間；Xik為救援點(diǎn)向第i個(gè)災(zāi)難現(xiàn)場分配的第k個(gè)資源量；Di為從救援點(diǎn)到第i個(gè)災(zāi)難現(xiàn)場的距離；vi為從救援點(diǎn)到第i個(gè)災(zāi)難現(xiàn)場的資源調(diào)度速度。

(3)

式中：ci(i=[1,N])為第i個(gè)資源的單位調(diào)度成本。

(4)

(5)

約束條件為：

(6)

(7)

2 結(jié)合NSGA-III和高斯估計(jì)的混合進(jìn)化算法

2.1 算法思路

NSGA-III在高維目標(biāo)空間中具有明顯優(yōu)勢。NSGA-III使用廣泛分布的參考點(diǎn)來維持群體中個(gè)體的多樣性。在優(yōu)化目標(biāo)構(gòu)建的超平面中選擇個(gè)體時(shí),使用理想點(diǎn)和參考點(diǎn)之間的連接,即從理想點(diǎn)和參考點(diǎn)組成的直線中選擇最近的個(gè)體。然而,NSGA-III使用傳統(tǒng)的交叉變異算子在父種群中隨機(jī)選擇個(gè)體。這種操作顯然只考慮個(gè)體的局部特征。因此,本文設(shè)計(jì)了1種結(jié)合NSGA-III和高斯估計(jì)的混合進(jìn)化算法?；旌纤惴ㄔ诿總€(gè)種群中選擇非優(yōu)勢個(gè)體計(jì)算總體特征,并使用高斯估計(jì)算法生成新一代種群。這可以大大提高最優(yōu)解的搜索效率和準(zhǔn)確性。

令父種群為Pt,首先計(jì)算總體的適應(yīng)度函數(shù)Ft。

Ft=[f1(Pt),f2(Pt),f3(Pt),f4(Pt)]

(8)

式中：fi(i=1,2,3,4)為第i個(gè)目標(biāo)函數(shù)的適應(yīng)度函數(shù)。

其次,對(duì)各個(gè)適應(yīng)度值執(zhí)行非支配排序操作。然后,對(duì)排名最高的個(gè)體計(jì)算其高斯分布均值和協(xié)方差。再次,通過高斯分布生成后代個(gè)體。接著,對(duì)新生成的個(gè)體執(zhí)行變異操作。最后,使用父種群Pt和后代個(gè)體Gt計(jì)算最小適應(yīng)度函數(shù)Zmin。最小適應(yīng)度函數(shù)計(jì)算如式(9)所示。

(9)

進(jìn)一步,對(duì)Gt和Ft進(jìn)行非顯性排序,使用生成的參考點(diǎn)和最小適應(yīng)度值Zmin進(jìn)行個(gè)體選擇,以獲得子種群Pt+1。

混合進(jìn)化算法流程如圖1所示。

圖1 混合進(jìn)化算法流程圖

混合進(jìn)化算法流程的主要階段包括交叉遺傳算子和時(shí)變高斯變異。圖1中：t為迭代步長；g為最大迭代次數(shù)。

2.2 優(yōu)化策略

2.2.1 交叉遺傳算子

遺傳算子對(duì)于控制進(jìn)化算法的優(yōu)化過程具有重要意義。在本小節(jié)中,交叉和變異算子將應(yīng)用于創(chuàng)建與初始種群大小相同的新種群。首先,隨機(jī)挑選來自第t代的2個(gè)父代x1(t)和x2(t),并使用模擬二進(jìn)制交叉技術(shù)執(zhí)行交叉操作,從而產(chǎn)生2個(gè)子代x1(t+1)和x2(t+1)。

(10)

式中：γ為擴(kuò)展因子,表示子代與父代絕對(duì)差異的比率。

(11)

式中：μj為隨機(jī)參數(shù),且μj∈(0,1)；η為固定參數(shù),通常取1。

2.2.2 時(shí)變高斯變異

在求解多目標(biāo)優(yōu)化問題時(shí),傳統(tǒng)NSGA-III可能會(huì)使種群過早陷入局部最優(yōu),并失去多樣性。因此,為了提高解的質(zhì)量,還可以增強(qiáng)算法的魯棒性。本小節(jié)設(shè)計(jì)了1種時(shí)變高斯變異函數(shù),通過變異算子產(chǎn)生新的種群。具體思路是在每一代對(duì)一些最差的個(gè)體使用高斯變異。一維高斯密度函數(shù)rg(x)定義如式(12)所示。

(12)

式中：μ和σ分別為高斯密度函數(shù)的均值和標(biāo)準(zhǔn)差,通常取μ=1、σ=0.5。

所提混合進(jìn)化算法中,時(shí)變高斯變異函數(shù)計(jì)算如下。

(13)

式中：Pm為變異概率；rg為服從平均值為0、方差為1的高斯分布；Vu和Vl為決策變量的上界和下界；Mr為變異參數(shù),本文取值為0.5；t為迭代次數(shù)；T為最大迭代次數(shù)。

3 仿真與分析

3.1 仿真環(huán)境

表1 救援站點(diǎn)對(duì)各資源參數(shù)

表2所示為災(zāi)難點(diǎn)/潛在災(zāi)難點(diǎn)對(duì)各資源需求。

表2 災(zāi)難點(diǎn)/潛在災(zāi)難點(diǎn)對(duì)各資源需求

同時(shí)，救援站點(diǎn)與災(zāi)難點(diǎn)相關(guān)參數(shù)如下：救援站點(diǎn)與災(zāi)難點(diǎn)1的距離為453 m，與災(zāi)難點(diǎn)2的距離為411 m，與災(zāi)難點(diǎn)3的距離為107 m，與災(zāi)難點(diǎn)4的距離為111 m。潛在災(zāi)難點(diǎn)災(zāi)難發(fā)生概率參數(shù)如下：潛在災(zāi)難點(diǎn)1災(zāi)難發(fā)生概率為0.65，潛在災(zāi)難點(diǎn)2災(zāi)難發(fā)生概率為0.23，潛在災(zāi)難點(diǎn)3災(zāi)難發(fā)生概率為0.38。試驗(yàn)場景相關(guān)參數(shù)信息設(shè)置如下：初始種群大小為700，最大迭代次數(shù)為150，交叉率為0.1，變異率為0.01。

3.2 性能對(duì)比與分析

圖2所示為不同算法目標(biāo)函數(shù)對(duì)比結(jié)果。由圖2可知，傳統(tǒng)NSGA-III將在第120代左右收斂,所提混合算法將在40～110代收斂到最優(yōu)解。仿真結(jié)果表明,混合進(jìn)化算法與NSGA-III相比性能更優(yōu),運(yùn)算效率提升9%～200%。因此,所提算法性能優(yōu)于傳統(tǒng)NSGA-III。仿真結(jié)果進(jìn)一步驗(yàn)證了本文方法對(duì)高速公路應(yīng)急事件管理具有一定的借鑒作用。

圖2 不同算法目標(biāo)函數(shù)對(duì)比結(jié)果

4 結(jié)論

本文對(duì)高速公路應(yīng)急處理進(jìn)行了研究與分析,提出了一種高速公路應(yīng)急救援資源調(diào)度管理策略,實(shí)現(xiàn)應(yīng)急事件資源調(diào)度。為查找最優(yōu)資源調(diào)度方案，本文提出了混合進(jìn)化算法，建立調(diào)度時(shí)間最優(yōu)、調(diào)度成本最優(yōu)、災(zāi)難站點(diǎn)損失最小、潛在災(zāi)難現(xiàn)場不滿意程度最小的4目標(biāo)資源調(diào)度優(yōu)化模型。本文方法對(duì)高速公路應(yīng)急事件管理具有一定借鑒作用。未來工作可對(duì)分布式節(jié)點(diǎn)計(jì)算進(jìn)行研究,從而進(jìn)一步提升調(diào)度效率。