考慮道路受損的震后應(yīng)急物資運(yùn)輸路徑優(yōu)化

閆森， 齊金平,2*， 張儒

(1.蘭州交通大學(xué)機(jī)電技術(shù)研究所, 蘭州 730070; 2.甘肅省物流及運(yùn)輸裝備信息化工程技術(shù)研究中心， 蘭州 730070)

中國地震災(zāi)害頻發(fā)，給人們的生命財(cái)產(chǎn)造成了巨大的損失，應(yīng)急物資的配送在救災(zāi)過程中十分重要。合理的規(guī)劃配送路徑，不僅能夠保證物資送達(dá)的及時(shí)性，還能降低成本，能有效地提高物流效率。中外學(xué)者在這方面已開展了大量的研究。Bozorgi等[1]考慮需求、時(shí)間和運(yùn)輸成本的不確定，引入需求不滿足率為優(yōu)化目標(biāo)，并同時(shí)考慮時(shí)間和成本最小，建立了配送路徑優(yōu)化模型；Shiri等[2]考慮需求時(shí)間的不確定性，利用陸運(yùn)和空運(yùn)兩種運(yùn)輸方式，建立了不確定條件下的混合整數(shù)非線性開放位置路徑優(yōu)化模型；Maharjan等[3]考慮總成本和需求覆蓋率兩個(gè)目標(biāo)，建立了臨時(shí)物流樞紐可靠性分配模型；Maghfiroh等[4]面對(duì)不可預(yù)測(cè)的需求和條件，提出了考慮隨機(jī)和動(dòng)態(tài)情況的路徑優(yōu)化模型；Jeong等[5]考慮時(shí)間重要性，需求信息的不確定性和動(dòng)態(tài)性以及信息傳遞的不確定性建立模型；劉松等[6]考慮運(yùn)輸環(huán)境和速度的不確定性，建立了帶班期限制的魯棒路徑優(yōu)化模型；梁永梅等[7]分別以路徑最短和時(shí)效性最優(yōu)為目標(biāo)求解了應(yīng)急醫(yī)療物資配送模型；曲沖沖等[8]以時(shí)效性與分配公平性為目標(biāo)，建立了多種運(yùn)輸方式、多時(shí)段的配送路徑優(yōu)化模型。上述文獻(xiàn)針對(duì)運(yùn)輸時(shí)間、物資需求的不確定性，以及路徑優(yōu)化的多種目標(biāo)進(jìn)行了研究，但其對(duì)需求不確定性的界定，物資種類的多樣性和路網(wǎng)的破環(huán)性研究有所欠缺。Rawls[9]和Salman等[10]考慮道路受損，建立了成本最小化的路徑優(yōu)化模型；Petroianu等[11]考慮車輛數(shù)量、道路通行性和天氣條件等因素，建立了應(yīng)急物流路徑優(yōu)化模型；狄衛(wèi)民等[12]地震災(zāi)害對(duì)道路的損毀，道路復(fù)雜程度和需求等不確定性因素，提出了物資拆分配送的方法，建立了應(yīng)急物資配送模型；張乃平等[13]考慮震后道路損毀和需求不足等因素，以分配公平性最大和配送總時(shí)間最小為目標(biāo)構(gòu)建了分配-運(yùn)輸模型。上述研究考慮到了地震災(zāi)害中道路的受損情況，但其對(duì)道路受損率的界定和對(duì)運(yùn)輸?shù)挠绊懷芯坎粔蛏钊?，未考慮到道路通行能力和需求點(diǎn)時(shí)間窗約束的影響，這會(huì)對(duì)實(shí)際的救災(zāi)效率產(chǎn)生影響。

Kara等[14]用各種的算法求解了帶時(shí)間窗的TSP問題；韓孟宜等[15]以運(yùn)輸成本和懲罰成本之和最小為目標(biāo)，構(gòu)建了帶時(shí)間窗約束的路徑優(yōu)化模型；陳疇鏞等[16]考慮道路時(shí)間窗及配送次序公平性因素，構(gòu)建了運(yùn)輸時(shí)間最短和懲罰成本最少的雙目標(biāo)模型；姚書婷等[17]建立了多禁止時(shí)間窗的應(yīng)急物資配送路徑優(yōu)化模型；郭詠梅等[18]以物流響應(yīng)能力最大化為目標(biāo)建立了等帶時(shí)間窗的車輛路徑模型；李卓等[19]以系統(tǒng)滿意度最大、系統(tǒng)配送時(shí)間和總成本最小為優(yōu)化目標(biāo)，建立帶軟時(shí)間窗的多目標(biāo)混合車輛路徑優(yōu)化模型。以上研究加入了救災(zāi)點(diǎn)時(shí)間窗的約束，但都是基于單一配送中心的路徑優(yōu)化，實(shí)際的應(yīng)急物流是錯(cuò)綜復(fù)雜的，可能包含多配送中心，多種應(yīng)急物資和不確定信息等情況。在路徑優(yōu)化模型求解方面，由于選址-路徑問題(Location-Routing problem, LRP)的(non-deterministic polynomial hard,NP-hard性質(zhì)，遺傳算法，蟻群算法，多頭絨泡菌算法，智能水滴算法和強(qiáng)化學(xué)習(xí)算法等啟發(fā)式算法具有良好的求解效果[20-21]，但對(duì)算法的求解精度和收斂性還可以進(jìn)一步的研究。

地震災(zāi)害由于其強(qiáng)大的破環(huán)性會(huì)對(duì)道路造成損壞。為此，從運(yùn)輸速度和道路通行能力等方面考慮地震災(zāi)害對(duì)道路的損毀情況，利用多種因素確定道路損毀率，針對(duì)多應(yīng)急物資種類、多配送中心的物流網(wǎng)絡(luò)，以配送時(shí)間和配送成本最小為目標(biāo)，建立了考慮道路受損的帶時(shí)間窗約束的應(yīng)急物資運(yùn)輸路徑優(yōu)化模型，并設(shè)計(jì)遺傳算法和模擬退火算法的混合算法求解該模型，為應(yīng)急救援物資配送提供科學(xué)決策，減少地震災(zāi)害帶來的人員和財(cái)產(chǎn)損失。

1 問題描述

地震發(fā)生后，在應(yīng)急物流網(wǎng)絡(luò)中產(chǎn)生V個(gè)節(jié)點(diǎn)，包括P個(gè)配送中心與M個(gè)需求點(diǎn)，救災(zāi)車輛需要在時(shí)間窗內(nèi)將救災(zāi)物資送往需求點(diǎn)。由于應(yīng)急物流的突發(fā)性和不可預(yù)知性，需求點(diǎn)對(duì)物資的需求量由三角模糊數(shù)表示。每個(gè)需求點(diǎn)規(guī)定兩個(gè)時(shí)間窗，一個(gè)為懲罰時(shí)間窗，另一個(gè)為硬性時(shí)間窗。即當(dāng)車輛在懲罰時(shí)間窗與硬性時(shí)間窗之間到達(dá)時(shí)，會(huì)造成人員或財(cái)產(chǎn)的損失，產(chǎn)生懲罰成本。所有車輛必須在硬性時(shí)間窗內(nèi)到達(dá)。而每條道路由于其地形、與震中的距離、道路等級(jí)等因素的不同也會(huì)有不同的受損情況。問題的目標(biāo)是在考慮道路受損的情況下，盡量在各需求點(diǎn)的時(shí)間窗內(nèi)，選擇合適的配送中心和配送路徑對(duì)需求點(diǎn)進(jìn)行配送，使得總的配送時(shí)間和配送成本最小。

根據(jù)問題的特點(diǎn)，提出如下假設(shè)：①應(yīng)急車輛在不考慮道路受損時(shí)的配送速度為正常速度；②應(yīng)急車輛在需求點(diǎn)的停留時(shí)間可以忽略不計(jì)，假設(shè)停留時(shí)間為0。

2 模型建立

2.1 道路通行能力和行駛速度計(jì)算

(1)通行能力計(jì)算。地震發(fā)生后，道路會(huì)由于其自身的損壞程度和周邊設(shè)施的損壞程度影響通行能力。為了方便研究，道路的損壞程度由道路的損毀率表示，其計(jì)算方法為式(2)，周邊設(shè)施的損壞程度由需求點(diǎn)的受災(zāi)程度表示，根據(jù)文獻(xiàn)[22]得到道路受損后的通行能力計(jì)算公式為

C=C′(1-α)(1-β)

(1)

α=

(2)

式中：C為考慮道路受損時(shí)的通行能力；C′為道路正常情況下的通行能力，可通過查詢公路通行能力手冊(cè)得到；α為道路的損毀率；Dj為需求點(diǎn)j到震中的距離；yj為需求點(diǎn)j的地形；Mou為山地地形；Pla為平原地形；TR為二級(jí)公路；TFR為三級(jí)公路和四級(jí)公路；Rl為路徑l的道路等級(jí)；β為受災(zāi)程度，根據(jù)地震發(fā)生后收集的受災(zāi)信息確定。

(2)行駛速度計(jì)算。震后車輛在有受損情況的道路上的行駛速度與道路損毀率有關(guān)，根據(jù)文獻(xiàn)[23]建立的模型并進(jìn)行改進(jìn)，得到考慮道路受損時(shí)的行駛速度的計(jì)算公式為

(3)

式(3)中：v為救災(zāi)車輛考慮道路受損時(shí)的平均行駛速度；v′為救災(zāi)車輛正常情況下的平均行駛速度。

2.2 模型構(gòu)建

模型的目標(biāo)為應(yīng)急救援的總時(shí)間和總成本最小，總時(shí)間為車輛運(yùn)輸時(shí)間;應(yīng)急救援成本包括車輛固定成本，各節(jié)點(diǎn)之間的運(yùn)輸成本以及違反時(shí)間窗的懲罰成本。模型可表示為

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

模型中，式(4)、式(5)為目標(biāo)函數(shù)，式(4)為運(yùn)輸時(shí)間最?。皇?5)為救援成本最小，主要由車輛的固定成本、運(yùn)輸成本和超出時(shí)間窗的懲罰成本組成；式(6)表示需求量的滿足；式(7)為庫存約束，表示配送中心的應(yīng)急物資運(yùn)輸量總和不超過其最大庫存；式(8)表示每個(gè)需求只對(duì)應(yīng)一個(gè)配送中心；式(9)表示道路通行能力的約束；式(10)表示硬性時(shí)間窗約束；式(11)表示車輛容量約束；式(12)表示車輛開始運(yùn)輸時(shí)的時(shí)間記為0；式(13)～式(16)表示決策變量的約束。

3 模型求解

3.1 不確定約束條件的處理

(17)

3.2 雙目標(biāo)的處理

在模型中，時(shí)間目標(biāo)和成本目標(biāo)是由于時(shí)間與成本的計(jì)量單位不同，對(duì)目標(biāo)進(jìn)行簡單的線性加權(quán)法也不合理。為此我們考慮通過計(jì)算單目標(biāo)的最優(yōu)值來將兩個(gè)目標(biāo)單位消除。因此目標(biāo)函數(shù)f1和f2可表示為

(18)

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

采用遺傳算法-模擬退火算法(genetic algorithm-simulated annealing，GA-SA)混合算法進(jìn)行求解，在遺傳算法的變異操作和適應(yīng)度函數(shù)中加入模擬退火算子，可以解決遺傳算法種群早熟問題，確保結(jié)果向全局最優(yōu)解收斂。

Step 1編碼方法。Mpoint個(gè)需求點(diǎn)，Pcenter個(gè)配送中心，采用雙層編碼，第一層編碼長度為Mpoint，基因?yàn)?-Mpoint，表示節(jié)點(diǎn)的訪問順序。第二層編碼為長度為Mpoint的整數(shù)編碼，基因位為[1,Pcenter]的整數(shù),表示節(jié)點(diǎn)由什么配送中心服務(wù)，其中Pcenter為配送中心數(shù)量。

Step 2遺傳算子設(shè)計(jì)。

(1)變異。采用兩點(diǎn)互易進(jìn)行變異：①產(chǎn)生2個(gè)隨機(jī)自然數(shù)r1、r2；②交換第r1位和r2位的基因。

(2)兩點(diǎn)交叉。①隨機(jī)選擇兩個(gè)染色體作為父本；②產(chǎn)生2個(gè)隨機(jī)自然數(shù)r1和r2；③將兩個(gè)父本染色體r1～r2的基因片段進(jìn)行交換, 得到兩個(gè)子代染色體，并對(duì)得到的兩個(gè)染色體進(jìn)行修訂處理,使得不發(fā)生沖突

(3)修補(bǔ)方法。交叉后, 取交叉片段的補(bǔ)集重新隨機(jī)排列到非交叉片段。

Step 3選擇設(shè)計(jì)。采用輪盤賭選擇。

Step 4模擬退火算子。

在遺傳算法中加入模擬退火算子，模擬退火的基本原理如下：①某個(gè)溫度T下得到一個(gè)解(這個(gè)解用遺傳算法優(yōu)化得到)；②如果這個(gè)解比上一個(gè)溫度的解好，則接受這個(gè)新的解，否則轉(zhuǎn)③；③計(jì)算T下的概率,其計(jì)算公式為

(19)

式(19)中：dE為目標(biāo)函數(shù)變化量；k為冷卻系數(shù)；隨機(jī)產(chǎn)生[0,1]區(qū)間的隨機(jī)數(shù)a，如果a

4 算例分析

4.1 算例描述

已知點(diǎn)A(75,70)為震中，該應(yīng)急物流網(wǎng)絡(luò)內(nèi)有2個(gè)配送中心，20個(gè)需求點(diǎn)以及3種應(yīng)急物資。應(yīng)急物資為帳篷、水和醫(yī)療用品，體積分別為0.2 m3/頂、1.5 m3/箱、0.2 m3/t，車輛容量為40 m3/車，正常情況下的行駛速度為60 km/h，固定成本為每輛300元，配送過程中單位運(yùn)輸成本為5元/km，違背時(shí)間窗單位懲罰成本為4元/min。配送中心以及需求點(diǎn)相關(guān)信息分別如表1、表2所示。

表1 配送中心信息Table 1 Distribution center information

4.2 算法結(jié)果

設(shè)種群規(guī)模N=200，最大迭代次數(shù)Maxgen=200，交叉概率=0.8，變異概率=0.1, 冷卻系數(shù)=0.95，初始溫度T0=2 000，終止溫度Tend=20，T=T0。使用MATLAB軟件，分別用一般遺傳算法與上述設(shè)計(jì)的算法進(jìn)行求解，目標(biāo)值的收斂變化情況如圖1所示。各節(jié)點(diǎn)之間的路徑如圖2所示。具體路徑信息如表3所示。

可以看出，SA-GA比遺傳算法所得結(jié)果的配送總時(shí)間降低5.4%，總成本降低了4.4%，表明了SA-GA比遺傳算法有更好的求解效果。

圖1 算法迭代比較Fig.1 Algorithm iteration comparison

表2 需求點(diǎn)信息Table 2 Demand point information

圖2 優(yōu)化路徑結(jié)果Fig.2 Optimizing path results

表3 路徑信息Table 3 Path information

表4 考慮與不考慮道路受損的結(jié)果對(duì)比Table 4 Comparison of results considering and not considering road damage

為了進(jìn)一步驗(yàn)證構(gòu)建模型的有效性,求解不考慮道路受損的應(yīng)急物資物流車輛路徑，其結(jié)果如表4所示。

通過對(duì)比發(fā)現(xiàn)考慮道路受損的最優(yōu)配送路徑可以更多的在懲罰時(shí)間窗內(nèi)送達(dá),同時(shí)可使總時(shí)間減少7.5%，總費(fèi)用減少5.0%。而在時(shí)間性要求非常高的應(yīng)急物資配送中，更多的物資在時(shí)間窗內(nèi)運(yùn)達(dá)，會(huì)對(duì)災(zāi)害造成的損失有一定的抑制作用。因此，所建立的路徑優(yōu)化模型對(duì)地震災(zāi)害發(fā)生時(shí)的道路受損進(jìn)行了較好地還原,更加符合實(shí)際場(chǎng)景，同時(shí)還對(duì)成本和時(shí)間進(jìn)行優(yōu)化，表明了本文模型的有效性。

5 結(jié)論

(1)考慮了地震災(zāi)害對(duì)道路的損壞，考慮多種應(yīng)急物資種類，并在其需求量不確定的情況下的進(jìn)行應(yīng)急物資配送路徑優(yōu)化，以配送時(shí)間最小和總成本最小為目標(biāo)建立了帶時(shí)間窗的雙目標(biāo)模型。

(2)考慮了在配送過程中物資的需求量具有不確定性，使用三角模糊數(shù)對(duì)應(yīng)急物資需求量進(jìn)行描述；考慮地震災(zāi)害中道路損毀，結(jié)合需求點(diǎn)到震中的距離、地形、公路等級(jí)等因素來確定道路損毀率，利用道路損毀率來描述其對(duì)車輛行駛的影響，更加符合實(shí)際情況，并且提高了路徑優(yōu)化的準(zhǔn)確性。

(3)設(shè)計(jì)了GA-SA算法對(duì)模型進(jìn)行求解，在遺傳算法的變異操作中加入了模擬退火算子，解決遺傳算法種群早熟問題。算例表明，該算法對(duì)收斂速度和求解結(jié)果都有提升，可以解決考慮道路受損的應(yīng)急物資配送路徑優(yōu)化問題。進(jìn)一步對(duì)比考慮與不考慮道路受損的結(jié)果，考慮道路受損在運(yùn)輸總時(shí)間和總費(fèi)用都有減少，產(chǎn)生懲罰成本的時(shí)間減少了41 min，驗(yàn)證了算法與模型的正確性和適用性。

地震災(zāi)害中道路其受損情況會(huì)由于余震和道路修復(fù)產(chǎn)生動(dòng)態(tài)變化。因此，應(yīng)進(jìn)一步考慮道路受損動(dòng)態(tài)變化的情況，使應(yīng)急物資配送路徑優(yōu)化更加考慮實(shí)際，更具科學(xué)性。