殷允強(qiáng), 羅琴鳳, 陳 旭, 王杜娟, 徐新蕊

(1.電子科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院,四川 成都 611731; 2.四川大學(xué) 商學(xué)院,四川 成都 610065)

1 引言

隨著地球生態(tài)環(huán)境惡化,世界各地頻繁突發(fā)自然災(zāi)害,給人類生命安全和社會(huì)發(fā)展帶來了巨大威脅。黨和國(guó)家對(duì)于災(zāi)后救援工作給予高度重視,黨的十九屆四中全會(huì)提出了“優(yōu)化我國(guó)應(yīng)急管理能力體系建設(shè),提高防災(zāi)減災(zāi)救災(zāi)能力”的努力方向。其中物流工作是決定救援行動(dòng)成功與否的關(guān)鍵[1],而救援物資供應(yīng)的有效性在很大程度上取決于災(zāi)區(qū)道路網(wǎng)絡(luò)的狀況。尤其在極端自然災(zāi)害后,道路、橋梁、隧道等交通基礎(chǔ)設(shè)施中斷,需要及時(shí)修復(fù)受損道路以保障應(yīng)急物資配送效率。因此,有必要對(duì)考慮道路修復(fù)的應(yīng)急物流集成優(yōu)化問題展開深入研究[2],提高災(zāi)后應(yīng)急救援的社會(huì)效力和經(jīng)濟(jì)效率。

在考慮道路修復(fù)的應(yīng)急物流集成優(yōu)化研究方面,按照維修車輛的數(shù)量,可分為單維修車輛問題和多維修車輛問題。在單維修車輛問題上,Maya-Duque等[3],Moreno等[4,5]以最小化需求節(jié)點(diǎn)可達(dá)時(shí)間的加權(quán)和為目標(biāo),研究了維修車輛調(diào)度及救援車輛路徑問題。Shin等[6]對(duì)Maya-Duque等的模型進(jìn)行拓展,增加了救援車輛調(diào)度決策,以最小化需求節(jié)點(diǎn)最晚可達(dá)時(shí)間為目標(biāo),并設(shè)計(jì)蟻群算法進(jìn)行求解。Kim等[7]考慮了修復(fù)工作的黃金時(shí)期,若在黃金時(shí)期后仍未對(duì)災(zāi)區(qū)進(jìn)行訪問將給予較高懲罰,還考慮了修復(fù)工作的完成時(shí)間最小化,同樣設(shè)計(jì)蟻群算法進(jìn)行求解?？梢园l(fā)現(xiàn),無法進(jìn)入受災(zāi)地區(qū)會(huì)導(dǎo)致疏散、救援和醫(yī)療援助等活動(dòng)延誤,因此及時(shí)、有效地修復(fù)受損的道路網(wǎng)絡(luò)對(duì)應(yīng)急物流至關(guān)重要。

在多維修車輛問題中,對(duì)于某維修車輛負(fù)責(zé)修復(fù)的受損節(jié)點(diǎn),其他車輛必須等待該受損節(jié)點(diǎn)恢復(fù)才可穿越路網(wǎng)。因此,除考慮救援車輛和維修車輛的配合,各維修車輛也需相互協(xié)同工作。Xu和Song[8]研究了最小化救援物資到達(dá)時(shí)間的災(zāi)后多維修車輛調(diào)度與救援車輛路徑優(yōu)化問題。李雙琳和鄭斌[9]構(gòu)建了綜合考慮震后路網(wǎng)搶修排程與應(yīng)急物資配送的動(dòng)態(tài)雙層規(guī)劃模型,并設(shè)計(jì)穩(wěn)態(tài)混合遺傳算法進(jìn)行求解。Li等[10]認(rèn)為災(zāi)后道路修復(fù)工作的開展依賴于有效的后勤保障,將維修車輛調(diào)度與后勤保障調(diào)度進(jìn)行集成優(yōu)化,并設(shè)計(jì)兩階段啟發(fā)式算法進(jìn)行求解。張夢(mèng)玲等[11]為實(shí)現(xiàn)精準(zhǔn)的物資配送與道路修復(fù)決策,基于手機(jī)定位數(shù)據(jù)構(gòu)建混合整數(shù)線性規(guī)劃模型,并設(shè)計(jì)嵌套遺傳算法和蟻群算法進(jìn)行求解。Moreno等[12]認(rèn)為現(xiàn)有研究忽略了維修車隊(duì)的異質(zhì)性,探究了異構(gòu)多車的道路修復(fù)和救援路徑規(guī)劃問題。上述研究表明,多維修車輛和多救援車輛協(xié)同工作更加符合實(shí)際救災(zāi)場(chǎng)景,能有效提升災(zāi)后響應(yīng)階段的應(yīng)急救援效率。

綜上可知,目前路網(wǎng)維修和應(yīng)急物流優(yōu)化已有一定研究成果,但鮮有研究綜合考慮災(zāi)后道路修復(fù)、應(yīng)急物資選址與配送的多目標(biāo)集成優(yōu)化問題。而救災(zāi)倉庫的位置對(duì)后續(xù)救援調(diào)配工作的效力和效率具有重大影響,需要在災(zāi)后應(yīng)急管理決策中綜合考慮救災(zāi)倉庫選址。并且由于上述組合優(yōu)化問題的復(fù)雜性和災(zāi)后響應(yīng)階段的時(shí)間緊迫性,也難以設(shè)計(jì)有效算法進(jìn)行精確求解。此外,災(zāi)后應(yīng)急物流的首要任務(wù)是減輕災(zāi)民痛苦,必須著重關(guān)注緩解災(zāi)民心理創(chuàng)傷,避免發(fā)生重大社會(huì)問題。除了考慮救援經(jīng)濟(jì)成本,救援行動(dòng)對(duì)災(zāi)民心理的影響是不可忽略的社會(huì)成本,也應(yīng)被考慮為一項(xiàng)重要的決策目標(biāo)[13]。

基于此,本文針對(duì)地震等自然災(zāi)害的實(shí)際救援需求,(1)綜合考慮災(zāi)民無法及時(shí)獲得救援物資的痛苦感知和實(shí)際救援經(jīng)濟(jì)支出,并將之量化為匱乏成本和救援成本,構(gòu)建道路修復(fù)、應(yīng)急物資選址與配送的雙目標(biāo)集成優(yōu)化模型。(2)設(shè)計(jì)基于密度峰值聚類的非支配排序遺傳算法II進(jìn)行求解,并引入初始解生成策略、基于聚類輪廓系數(shù)的不動(dòng)點(diǎn)策略以及變鄰域局部搜索策略對(duì)算法進(jìn)行改進(jìn)。(3)利用汶川地震案例和隨機(jī)算例,驗(yàn)證上述模型和算法的有效性,并提煉管理啟示。

2 問題描述與模型構(gòu)建

2.1 問題描述

考慮道路修復(fù)的應(yīng)急物資選址與配送集成優(yōu)化問題定義在無向圖G=(V=Vd∪Vr,A)上。其中V為節(jié)點(diǎn)集合,A為弧集,Vd?V為需求節(jié)點(diǎn)集合,Vr?V為受損節(jié)點(diǎn)集合,Vs?Vd為候選救災(zāi)倉庫集合,Ks為倉庫s∈Vs處的救援車輛集合。記Vs=(VVs)∪{s},Vs′=(VVs)∪{s′},其中s′為節(jié)點(diǎn)s的復(fù)制節(jié)點(diǎn)。需求節(jié)點(diǎn)i∈Vd的救援物資需求量為di,受損節(jié)點(diǎn)i∈Vr的維修時(shí)間為ri和維修成本為ui,弧(i,j)、弧(l,m)∈A的旅行時(shí)間為tij和tlm。擬開設(shè)救災(zāi)倉庫的總數(shù)量為D_num,倉庫s∈Vs的開設(shè)成本為Fs,啟用一輛救援車的固定成本為R,救援車輛和維修車輛的單位時(shí)間旅行成本為c。M為充分大的數(shù)。

相關(guān)假設(shè)如下。(1)需求節(jié)點(diǎn)的數(shù)量、位置、需求量已知。(2)每個(gè)受損節(jié)點(diǎn)和需求節(jié)點(diǎn)都僅由一輛車服務(wù)一次,且各需求節(jié)點(diǎn)的需求被完全供應(yīng)。(3)每個(gè)候選倉庫配置有限個(gè)容量為C的同規(guī)格救援車輛,以及數(shù)量充足的同規(guī)格維修車輛。(4)每個(gè)救援車輛可服務(wù)多個(gè)需求節(jié)點(diǎn),每個(gè)維修車輛最多只修復(fù)一個(gè)受損節(jié)點(diǎn)。(5)所有被指派車輛均在零時(shí)刻從倉庫出發(fā),結(jié)束任務(wù)后返回原倉庫。(6)不考慮維修車輛返回路徑。

為有效度量救援效力,本文利用救援物資匱乏時(shí)長(zhǎng)來描繪災(zāi)民無法獲得物資的痛苦感知,定義匱乏成本函數(shù)為Γ(t)=a(eb×t-1),其中a、b均為常數(shù)[13],t為救援車輛達(dá)到需求節(jié)點(diǎn)的時(shí)間。

2.2 模型構(gòu)建

基于以上參數(shù),構(gòu)建如下數(shù)學(xué)規(guī)劃模型

(1)

(2)

(30)

3 算法設(shè)計(jì)

上述模型為雙目標(biāo)非線性規(guī)劃模型,難以設(shè)計(jì)有效的精確算法進(jìn)行求解。為了在災(zāi)后響應(yīng)階段快速求解此類復(fù)雜的集成優(yōu)化問題,本文設(shè)計(jì)一種基于密度峰值聚類的非支配排序遺傳算法II,快速求得近似帕累托最優(yōu)解集。該算法利用密度峰值聚類(density peaks clustering,DPC)算法快速選定救災(zāi)倉庫的位置,采用Floyd算法決策受損道路修復(fù)方案,并獲得各受損節(jié)點(diǎn)的最早修復(fù)完成時(shí)間。然后,利用非支配排序遺傳算法II(NSGA-II)確定應(yīng)急物資配送方案及需修復(fù)的受損節(jié)點(diǎn)。最后,設(shè)計(jì)初始解生成策略、基于聚類輪廓系數(shù)的不動(dòng)點(diǎn)策略以及變鄰域局部搜索策略對(duì)上述算法進(jìn)行改進(jìn),記為CGAVNS算法。整體算法流程如圖1所示。

圖1 CGAVNS算法流程圖

3.1 救災(zāi)倉庫選址算法設(shè)計(jì)

本文首先基于DPC算法確定若干個(gè)聚類中心和相應(yīng)群簇,選定聚類中心作為救災(zāi)倉庫,其群簇作為相應(yīng)客戶群,基于此生成救災(zāi)倉庫和各需求節(jié)點(diǎn)的初始指派方案。然后利用聚類輪廓系數(shù),衡量各群簇內(nèi)的緊密程度以及各群簇間的離散程度,以此生成其他指派方案,用于后續(xù)初始解生成。關(guān)鍵算法步驟如下:

(1)確定救災(zāi)倉庫:計(jì)算局部密度ρi和相對(duì)距離δi,記γi=ρiδi,將γi降序排列,選擇前D_num個(gè)需求節(jié)點(diǎn)作為聚類中心s,即救災(zāi)倉庫。

(31)

(32)

其中dij為節(jié)點(diǎn)i和j之間的最短距離,dc為截?cái)嗑嚯x,qi表示按ρi降序排列的節(jié)點(diǎn)序列,即ρq1≥ρq2≥…≥ρqN。

(2)非聚類中心指派:確定局部密度比i大的節(jié)點(diǎn)中與i距離最近的節(jié)點(diǎn)編號(hào)ni。記聚類中心的類別標(biāo)簽為其本身,非聚類中心i的類別標(biāo)簽與ni一致。據(jù)此,將非聚類中心i(其他需求節(jié)點(diǎn))指派給救災(zāi)倉庫進(jìn)行服務(wù)。

(33)

(3)確定不動(dòng)點(diǎn)并生成其他指派方案:計(jì)算各非聚類中心的輪廓系數(shù)Si和最近簇,將Si升序排列,選擇后1-α比例的節(jié)點(diǎn)存入不動(dòng)點(diǎn)集合constant。再將[0,α]比例的非不動(dòng)點(diǎn)重新指派到其最近簇中,生成不同指派方案。

(34)

其中ai為i與同簇其他節(jié)點(diǎn)的平均距離,bi=biJ=min{bi1,bi2,…,biK}為i與其他簇中所有節(jié)點(diǎn)平均距離的最小值,J為節(jié)點(diǎn)i的最近簇。

3.2 受損道路修復(fù)算法設(shè)計(jì)

本文采用Floyd算法的思想,求解到各受損節(jié)點(diǎn)最快的修復(fù)路徑以及相應(yīng)修復(fù)完成時(shí)間。由于考慮了多維修車輛協(xié)同工作,當(dāng)某維修車輛的修復(fù)路徑經(jīng)過其他受損路段,若該受損路段已被其他維修車輛修復(fù),則車輛可直接行駛;若當(dāng)該維修車輛到達(dá)時(shí)上述路段尚未完全修復(fù),則車輛需等待至該路段修復(fù)后才能通行。因此,在使用Floyd算法時(shí)需要單獨(dú)計(jì)算并更新各受損節(jié)點(diǎn)的最早修復(fù)完成時(shí)間,且在利用路徑矩陣進(jìn)行路徑擴(kuò)展時(shí),必須檢查路徑中是否含有受損節(jié)點(diǎn)。

3.3 應(yīng)急物資配送算法設(shè)計(jì)

使用改進(jìn)的NSGA-II算法決策應(yīng)急物資配送方案,相關(guān)操作和步驟如下:

(1)染色體編碼

兩段式染色體編碼方式能夠消除部分冗余解,提高算法的搜索效率[14]。其中第一部分為需求節(jié)點(diǎn)的排列編碼,第二部分為各倉庫的各救援車輛對(duì)應(yīng)訪問的需求節(jié)點(diǎn)數(shù)。例如,現(xiàn)有15個(gè)需求節(jié)點(diǎn),2個(gè)救災(zāi)倉庫(記為倉庫1和2),每個(gè)救災(zāi)倉庫2輛救援車,則根據(jù)上述編碼規(guī)則,可得到圖2的一條染色體。圖2表示倉庫1的救援車輛1供應(yīng)6個(gè)需求節(jié)點(diǎn),配送順序?yàn)?-8-13-7-1-10,倉庫1的救援車輛2不啟用;倉庫2的救援車輛1供應(yīng)4個(gè)需求節(jié)點(diǎn),配送順序?yàn)?-9-15-11,倉庫2的救援車輛2供應(yīng)5個(gè)需求節(jié)點(diǎn),配送順序?yàn)?-6-12-14-5。

圖2 染色體編碼示意圖

(2)染色體解碼

根據(jù)染色體的編碼思路,先將染色體按照車輛拆分成配送順序s-s′(k),然后檢查兩相鄰需求節(jié)點(diǎn)(i和i+1)的配送路徑ODi是否經(jīng)過受損節(jié)點(diǎn)。若經(jīng)過受損節(jié)點(diǎn),救援車輛可能會(huì)發(fā)生等待,則需將受損節(jié)點(diǎn)的最早修復(fù)完成時(shí)間用于救援車輛到達(dá)時(shí)間的計(jì)算。對(duì)應(yīng)各路徑累積計(jì)算匱乏成本和救援成本,進(jìn)而解碼得到染色體的適應(yīng)度。

(3)初始解生成

使用基于聚類的節(jié)約法生成一部分高質(zhì)量的初始解。以各聚類中心s為節(jié)約法的基點(diǎn),在其群簇內(nèi),基于節(jié)約值,利用貪婪策略將各需求節(jié)點(diǎn)插入救援車輛路徑中,形成各倉庫客戶群的較優(yōu)配送路徑,最終初始解為所有客戶群對(duì)應(yīng)的配送路徑組合?；?.1節(jié)的多種指派方案,生成不同的初始解。

為保證初始解多樣性,使用插入啟發(fā)式生成另一部分初始解。核心步驟為:通過準(zhǔn)則φ1找到需求節(jié)點(diǎn)j的最佳可行插入位置,通過準(zhǔn)則φ2選擇最佳需求節(jié)點(diǎn)j*,再將j*插入到路徑中的最佳可行插入位置。(35)式表示插入節(jié)點(diǎn)j后服務(wù)需求節(jié)點(diǎn)m和l總旅行時(shí)間的增加量,其中Tlm為兩節(jié)點(diǎn)之間的總旅行時(shí)間;(36)式表示插入節(jié)點(diǎn)j后路徑總匱乏成本的增加量,其中route為原路徑,route′為插入節(jié)點(diǎn)j后的路徑。

(35)

(36)

(4)遺傳算子

采用輪盤賭策略進(jìn)行染色體選擇,使用自適應(yīng)選擇psi、交叉pci概率進(jìn)行遺傳進(jìn)化,其中ranki為個(gè)體i在種群pops中非支配排序后的等級(jí),pops={1,2,…,pop_size},pc為固定交叉概率。

(37)

(38)

參考特殊的兩段式染色體交叉算子[15]進(jìn)行交叉操作,并利用聚類獲得的不動(dòng)點(diǎn)集合constant對(duì)交叉算子進(jìn)行改進(jìn),后續(xù)算法搜索過程中不動(dòng)點(diǎn)與倉庫的指派關(guān)系不變,從而提高搜索效率。給定一對(duì)待交叉的染色體c1和c2,假設(shè)以染色體c1為基礎(chǔ),生成子染色體child1。首先從c1的各路徑中隨機(jī)選擇一個(gè)基因片段(子路)保留下來,然后根據(jù)c2第一部分的基因順序?qū)ι鲜鑫幢Ａ艋蜻M(jìn)行排序,將未保留基因Q排序?yàn)镼′。接著,根據(jù)constant確定Q′中的不動(dòng)點(diǎn)并按照倉庫拆分。然后,基于車輛容量約束和各倉庫不動(dòng)點(diǎn)限制,產(chǎn)生可行隨機(jī)數(shù),按照隨機(jī)數(shù)將Q′中的基因新添到c1各路徑中,最終形成子染色體child1。類似地,再以染色體c2為基礎(chǔ),可生成另一條子染色體。

設(shè)計(jì)4種變異算子:①Inter_exchange:隨機(jī)選擇兩條配送路徑,若屬于同一倉庫,則在容量約束下,再各自隨機(jī)選擇1個(gè)需求節(jié)點(diǎn)進(jìn)行交換;否則,只能選擇非不動(dòng)點(diǎn)進(jìn)行交換。②Inter_relocation:隨機(jī)選擇兩條配送路徑,若屬于同一倉庫,則從需求節(jié)點(diǎn)數(shù)較多的路徑中隨機(jī)刪除1個(gè)節(jié)點(diǎn),在容量約束下,再隨機(jī)插入另一條路徑;否則,只能選擇非不動(dòng)點(diǎn)進(jìn)行刪除插入。③Intra_exchange:隨機(jī)選擇同一配送路徑中的2個(gè)需求節(jié)點(diǎn)進(jìn)行交換。④Intra_relocation:隨機(jī)刪除一條配送路徑中的1個(gè)需求節(jié)點(diǎn),再隨機(jī)插入該路徑的其他位置。

(5)變鄰域局部搜索

采用變異階段的4種算子構(gòu)造鄰域動(dòng)作集Nl=(N1,N2,N3,N4),對(duì)最后一代的非支配個(gè)體進(jìn)行變鄰域局部搜索,避免算法陷入局部最優(yōu)。主要核心思想為:若在鄰域搜索次數(shù)內(nèi)找不到比當(dāng)前解更優(yōu)的解,則跳到下一個(gè)鄰域繼續(xù)搜索;若找到了更優(yōu)解,則以此為最好解重新進(jìn)行變鄰域搜索。

4 數(shù)值實(shí)驗(yàn)

以2008年汶川地震案例和隨機(jī)算例進(jìn)行數(shù)值實(shí)驗(yàn),驗(yàn)證本文模型和算法的有效性。使用軟件Python 3.8進(jìn)行編程,運(yùn)行在AMD Ryzen 7 4800U@1.80Ghz的CPU,16.0GB內(nèi)存的筆記本電腦上。

4.1 案例背景

依據(jù)汶川地震災(zāi)情報(bào)告,共設(shè)38個(gè)物資需求節(jié)點(diǎn)(0-37),16個(gè)道路受損節(jié)點(diǎn)(38-53),需開設(shè)3個(gè)救災(zāi)倉庫,各倉庫備有6輛救援車,車輛容量為1800,單個(gè)倉庫的開設(shè)成本為30000元,旅行成本為8元/分鐘,受損節(jié)點(diǎn)的維修成本設(shè)為維修時(shí)間的100倍。災(zāi)區(qū)路網(wǎng)如圖3所示,路徑上的數(shù)值為旅行時(shí)間(分鐘),括號(hào)中的數(shù)值為需求節(jié)點(diǎn)的需求量(個(gè))或受損節(jié)點(diǎn)的維修時(shí)間(分鐘)。匱乏成本函數(shù)中相關(guān)系數(shù)為:a=1.5,b=0.12[13]。算法相關(guān)參數(shù)設(shè)置如下:種群規(guī)模pop_size=60,進(jìn)化代數(shù)maxgen=60,交叉概率pc=0.9,變異概率為pm=0.1,鄰域搜索次數(shù)S=15,鄰域搜索循環(huán)次數(shù)max_N=20,截?cái)啾壤?0.02,不動(dòng)點(diǎn)比例α=0.6。

圖3 汶川地震災(zāi)區(qū)路網(wǎng)圖

4.2 案例求解

基于上述案例背景,以Pareto解集中匱乏成本和救援成本中位數(shù)對(duì)應(yīng)的解為例,展示最終救援決策方案。CGAVNS算法求解得到的救災(zāi)倉庫為節(jié)點(diǎn)12、節(jié)點(diǎn)23和節(jié)點(diǎn)32,分別記為倉庫1、2、3,啟用的救援車輛數(shù)分別為6、4、3。救援車輛配送路徑如表1所示,共需修復(fù)8個(gè)受損節(jié)點(diǎn),維修車輛修復(fù)路徑如表2所示。整體決策方案的匱乏成本為20819元,救援成本為515712元,其中倉庫建設(shè)成本為90000元,救援車輛啟用成本為13000元,道路修復(fù)成本為384000元,車輛旅行成本為28712元。

表1 救援車輛配送路徑及物資到達(dá)時(shí)間

表2 修復(fù)路徑及修復(fù)完成時(shí)間

4.3 修復(fù)策略驗(yàn)證

本節(jié)取受損節(jié)點(diǎn)完全修復(fù)和部分修復(fù)時(shí)目標(biāo)值中位數(shù)所對(duì)應(yīng)救援結(jié)果進(jìn)行比較分析。參考文獻(xiàn)[16]和實(shí)際調(diào)研,按照各節(jié)點(diǎn)平均連接弧數(shù)γ取3、4、5(分別表示鄉(xiāng)村、混合和城市路網(wǎng)),路網(wǎng)受損率?取10%、30%、50%,隨機(jī)生成了100個(gè)需求節(jié)點(diǎn)的9種隨機(jī)算例。

表3 受損節(jié)點(diǎn)部分修復(fù)和完全修復(fù)結(jié)果對(duì)比

基于上述數(shù)值分析,當(dāng)發(fā)生地震、洪水、海嘯等極端自然災(zāi)害后,可總結(jié)以下三點(diǎn)管理啟示:(1)災(zāi)區(qū)路網(wǎng)越稀疏越應(yīng)重視路網(wǎng)修復(fù),農(nóng)村地區(qū)應(yīng)配備更多的道路修復(fù)人員和相關(guān)設(shè)備。(2)災(zāi)情越嚴(yán)重越應(yīng)重視災(zāi)區(qū)路網(wǎng)修復(fù),從而及時(shí)恢復(fù)災(zāi)區(qū)路網(wǎng)的連通性和可達(dá)性。(3)相較于受損路段完全修復(fù),只修復(fù)部分關(guān)鍵受損路段效益更高,尤其在城市路網(wǎng)中。

4.4 算法有效性分析

本節(jié)將不進(jìn)行改進(jìn)的基礎(chǔ)算法CNSGA-II與只添加初始解生成策略的算法CNSGA-II+IS、只添加不動(dòng)點(diǎn)策略的算法CNSGA-II+CN、只添加變鄰域局部搜索策略的算法CNSGA-II+VNS以及添加所有改進(jìn)策略的算法CGAVNS的求解結(jié)果進(jìn)行比較。選擇30%路網(wǎng)受損率的隨機(jī)算例100-3-30、100-4-30、100-5-30,從超體積(HV)和運(yùn)行時(shí)間(T)兩個(gè)性能指標(biāo)上,驗(yàn)證算法改進(jìn)策略的有效性。表4給出了各算法的HV值和T值,以及相較于基礎(chǔ)算法CNSGA-II的變化率(記為CR)。

表4 CNSGA-II與CNSGA-II+IS、CNSGA-II+CN、CNSGA-II+VNS、CGAVN結(jié)果比較

總體來看,相較于基礎(chǔ)算法CNSGA-II,添加各策略后的算法均有明顯的改進(jìn)。這是由于本文算例參考實(shí)際路網(wǎng),均為稀疏圖,算法在全局搜索過程中局部最優(yōu)非常嚴(yán)重且難以跳出。具體來看,(1)初始解生成策略在算法求解時(shí)間上優(yōu)化效果最好,相較于基礎(chǔ)算法,CNSGA-II+IS求解時(shí)間平均降低約82%。這說明本文的初始解策略可明顯加快算法的尋優(yōu)速度,從而使算法在較少的迭代數(shù)下收斂。但CNSGA-II+IS算法仍無法避免陷入局部最優(yōu),CGAVNS以增加約9%的求解時(shí)間,換取超體積值提升72%。(2)變鄰域局部搜索策略在超體積指標(biāo)上優(yōu)化效果最好,相較于基礎(chǔ)算法,CNSGA-II+VNS超體積值平均提升約70%。這說明本文的局部搜索策略可有效解決局部最優(yōu)問題,明顯提高解的質(zhì)量。但CNSGA-II+VNS相較于CGAVNS,需花費(fèi)更多時(shí)間在全局尋優(yōu)上,CGAVNS的超體積值與之差異不大,但求解速度提升約13%。(3)基于聚類輪廓系數(shù)的不動(dòng)點(diǎn)策略在算法運(yùn)行效率上有一定程度的優(yōu)化,但在HV指標(biāo)上表現(xiàn)較弱?？赡茉蚴?不動(dòng)點(diǎn)策略在算法搜索過程中,限制輪廓系數(shù)大的需求節(jié)點(diǎn)與倉庫的指派關(guān)系不變,從而避免無效搜索、加快尋優(yōu)速度,但同時(shí)也會(huì)因限制搜索從而遺漏一些高質(zhì)量解。

5 結(jié)論與啟示

本文針對(duì)極端自然災(zāi)害的實(shí)際救援需求,對(duì)道路修復(fù)、應(yīng)急物資選址與配送集成優(yōu)化問題展開研究。以匱乏成本和救援成本最小化為目標(biāo),構(gòu)建考慮道路修復(fù)的應(yīng)急物資選址與配送雙目標(biāo)優(yōu)化模型,設(shè)計(jì)基于密度峰值聚類的非支配排序遺傳算法II進(jìn)行求解,并添加初始解生成策略、基于聚類輪廓系數(shù)的不動(dòng)點(diǎn)策略以及變鄰域局部搜索策略進(jìn)一步改進(jìn)算法性能。最后,利用數(shù)值實(shí)驗(yàn)驗(yàn)證模型和算法的有效性。結(jié)果表明:(1)本文模型和算法具備較好的應(yīng)用性,可以幫助決策者在社會(huì)成本和經(jīng)濟(jì)成本的權(quán)衡下做出科學(xué)的救災(zāi)戰(zhàn)略規(guī)劃。(2)災(zāi)情越嚴(yán)重、災(zāi)區(qū)路網(wǎng)越稀疏,越應(yīng)重視災(zāi)后道路修復(fù),且在應(yīng)急響應(yīng)階段只需修復(fù)關(guān)鍵受損路段便可高效支撐救援任務(wù),從而為實(shí)際救援節(jié)約人力物力,實(shí)現(xiàn)救援效益最大化。(3)三種算法改進(jìn)策略均有明顯優(yōu)化效果,設(shè)計(jì)的CGAVNS算法具備較好的綜合求解性能,能夠在災(zāi)后快速生成較優(yōu)的救援方案,保障救災(zāi)工作的效力和效率。

未來研究工作可考慮災(zāi)害的多維不確定性和動(dòng)態(tài)性,研究動(dòng)態(tài)多周期的道路修復(fù)和資源調(diào)配問題,并利用大數(shù)據(jù)技術(shù)實(shí)時(shí)獲取災(zāi)民需求、定位等數(shù)據(jù),探究實(shí)際災(zāi)害情景的表征手段和建模方法。另外,實(shí)際救援中還會(huì)設(shè)置后勤工作站以作維修資源供給,如何進(jìn)行異構(gòu)維修車輛協(xié)同調(diào)度及工作站選址分配也有待進(jìn)一步探究。