基于改進(jìn)飛蛾撲火算法求解多需求點(diǎn)的應(yīng)急物資調(diào)度

賀體龍，樓文高，2

1(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院，上海200093)

2(上海商學(xué)院校長辦公室，上海200235)

1 引 言

當(dāng)今，近年來，災(zāi)害性事件頻發(fā)，給人民群眾的生命財(cái)產(chǎn)帶來了嚴(yán)重的威脅［1］.在突發(fā)地震的緊急處理過程中，最重要的工作之一就是供給相應(yīng)的應(yīng)急物資，所以開展快速而又有效的物資調(diào)度與配送變得至關(guān)重要.因此，研究應(yīng)急物資調(diào)度問題具有重要的理論和實(shí)踐意義.Kemball-Cook［2］在1984年首次提出該問題——對(duì)于救援物資的供應(yīng)和運(yùn)輸需要進(jìn)行針對(duì)性的管理.此后，國內(nèi)外學(xué)者對(duì)應(yīng)急物資調(diào)度問題進(jìn)行了深入探討，做了大量研究.現(xiàn)有文獻(xiàn)［3-11］的研究主要是基于未考慮道路發(fā)生損壞情況下的應(yīng)急物資調(diào)度問題，未考慮到道路實(shí)際損毀情況.

事實(shí)上，地震等災(zāi)害發(fā)生后，當(dāng)?shù)氐缆吠鶗?huì)遭到損壞，物資運(yùn)載過程中所消耗的時(shí)間以及成本也會(huì)隨道路的損壞程度產(chǎn)生相應(yīng)的變化.此前很少有學(xué)者研究此類問題，王晶等［12］考慮了道路毀壞程度對(duì)運(yùn)行時(shí)間的修正，并利用網(wǎng)絡(luò)流的方法求解;姜春霞等［13］考慮了道路損壞情況、損毀程度及可修復(fù)性對(duì)車輛運(yùn)行時(shí)間的影響，并引入應(yīng)急物資調(diào)度限制，以最小化配送延遲為目標(biāo)建立優(yōu)化模型.陳鋼鐵［14］等建立道路搶修和應(yīng)急物資調(diào)度模型并采用啟發(fā)式算法對(duì)模型進(jìn)行求解.Jiang Jincheng［15］等考慮出行時(shí)間、道路通行能力和物資供求情況，提出的應(yīng)急物資車輛調(diào)度模型來解決物資調(diào)度問題.雖然他們考慮了道路受損的情況，但是事實(shí)上，在實(shí)施調(diào)度之前，通過無人機(jī)圖像識(shí)別技術(shù)進(jìn)行災(zāi)害評(píng)估和明確道路狀態(tài)［16-18］，所以本文根據(jù)道路通行的狀態(tài)，選擇相應(yīng)的路線，并建立相應(yīng)的調(diào)度模型.

再則已有研究大多采用粒子群算法［5］、遺傳算法［6］、蟻群算法［19］等求解應(yīng)急物資調(diào)度最優(yōu)化問題.文獻(xiàn)［20，21］表明，Mirijalili 等提出的飛蛾撲火優(yōu)化算法(MFO)其全局搜索能力和局部收斂速度方面明顯優(yōu)于上述最優(yōu)化算法.但是在高維情況下，MFO 算法會(huì)陷入局部最優(yōu)解，因此本文將使用Trivedi I N［22］等提出的 Levy—MFO 算法(IMFO)進(jìn)行求解應(yīng)急物資調(diào)度方案.

因此，本文研究運(yùn)輸路網(wǎng)結(jié)構(gòu)存在不同毀壞情況下的應(yīng)急物資調(diào)度問題，以運(yùn)輸過程中物資裝載總時(shí)間最少、所消耗成本最少為優(yōu)化目標(biāo)函數(shù)，用IMFO 算法求解最優(yōu)應(yīng)急物資調(diào)配方案，并與MFO 算法求解的結(jié)果進(jìn)行對(duì)比.

2 問題描述與模型建立

2.1 問題描述

設(shè)有 m 個(gè)災(zāi)害需求點(diǎn) B1，B2，…，Bm，需要 n 個(gè)應(yīng)急物資救援點(diǎn) A1，A2，…，An，提供 p 種物資 C1，C2，…，Cp，假定 aqi表示第q 種物資在第i 個(gè)救援點(diǎn)的儲(chǔ)存量，bqi表示第j 個(gè)需求點(diǎn)對(duì)第 q 種物資的需求量，其中:1≤q≤p，1≤i≤n，1≤j≤m.tqi表示第i 個(gè)救援點(diǎn)裝載第q 種物資所需要的單位時(shí)間.設(shè)從第i 物資救援點(diǎn)到第j 個(gè)災(zāi)害需求可能存在著道路損毀，設(shè)道路損毀的路程為Xij，單位距離修復(fù)道路的時(shí)間為T0，根據(jù)路段不同的損毀情況，分配施工隊(duì)進(jìn)行施工，0≤α＜β 表示道路可行，無需派遣施工隊(duì)，表示道路可修復(fù)，派遣施工隊(duì)進(jìn)行修復(fù)，并加以修復(fù)時(shí)間最晚為Tend進(jìn)行約束，若修復(fù)時(shí)間大于Tend，則表示此次路線不通;δ≤α≤1 表示道路不可修復(fù)，無需派遣施工隊(duì)，此次路線不通.要求以運(yùn)輸過程中物資裝載總時(shí)間最少和所消耗成本最少為優(yōu)化目標(biāo)，給出一個(gè)最優(yōu)的調(diào)度方案.

2.2 條件假設(shè)

假設(shè)1.車輛在運(yùn)輸過程中的速度恒定，不考慮出發(fā)與到達(dá)的速度變化.

假設(shè)2.每一種需求(應(yīng)急)物資的需求(應(yīng)急)程度相同.

假設(shè)3.所有救援點(diǎn)的各種物資數(shù)量之和能滿足所有需求點(diǎn)所需的各種物資數(shù)量之和.

假設(shè)4.從Ai到Bj有且僅有一條最短路線.

假設(shè)5.每條道路只可能存在一種情況的損壞，即:無損壞、損壞可通行、損壞可修復(fù)或者損壞不可通行.

假設(shè)6.暫不考慮派遣施工隊(duì)所消耗的成本.

2.3 模型建立

以運(yùn)輸過程中物資裝載總時(shí)間最少和所消耗成本最少為優(yōu)化目標(biāo)，模型建立如下:因?yàn)闀r(shí)間和成本為不同量綱，蔣杰輝［23］提出引入時(shí)間成本系數(shù)ω，將時(shí)間看成成本的一部分，本文再引入權(quán)重因子w1、w2，將上述多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù).從應(yīng)急物資調(diào)度現(xiàn)實(shí)需求角度看，時(shí)間的權(quán)重應(yīng)大于成本的權(quán)重，從而得:

其中:公式(1)和公式(2)分別表示運(yùn)輸成本以及時(shí)間成本，cij表示從第i 個(gè)救援點(diǎn)到第j 個(gè)需求點(diǎn)運(yùn)輸單位物資量所消耗的成本，xqij表示從第i 個(gè)救援點(diǎn)到第j 個(gè)需求點(diǎn)運(yùn)輸?shù)趒種物資量，rij表示從第i 個(gè)救援點(diǎn)到第j 個(gè)需求點(diǎn)是否可以通行，tqi表示第i 個(gè)救援點(diǎn)裝載第q 種物資所需要的單位時(shí)間;公式(3)表示救援點(diǎn)的第q 種物資量不小于需求點(diǎn)所需求的第q 種物資量，Aqi表示第i 個(gè)救援點(diǎn)的第q 種物資量，Bqj表示第j 個(gè)需求點(diǎn)需求的第q 種物資量;公式(4)表示從第i 個(gè)救援點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn)的第q 種物資量不大于第i 個(gè)救援點(diǎn)的所含有第q 種物資量;公式(5)表示從救援點(diǎn)運(yùn)輸?shù)降趈 個(gè)需求點(diǎn)的第q 種物資量不小于第j 個(gè)需求點(diǎn)所需求的第q 種物資量.公式(6)表示第i 個(gè)救援點(diǎn)到第j 個(gè)需求點(diǎn)的道路是否可行，0 表示道路不可行，1 表示道路可行.

3 算 法

飛蛾撲火優(yōu)化(MFO)算法是一種新穎的群智能優(yōu)化算法，該算法的主要靈感來源于飛蛾在自然界中被稱為橫向定位的飛行方式.MFO 算法的尋優(yōu)過程可以抽象的理解為飛蛾尋焰與棄焰兩種行為.在尋優(yōu)迭代運(yùn)算過程中，飛蛾和火焰分別有獨(dú)特的公式來進(jìn)行的迭代運(yùn)算更新自己的位置.其中飛蛾是在搜索空間里的實(shí)際搜索主體，而火焰是飛蛾到目前為止搜索到的最好位置.因此，如果飛蛾找到一個(gè)更好的解，則每只飛蛾便在標(biāo)記火焰附近搜索并更新火焰.飛蛾通過這種過程就可以得到它的最優(yōu)解.通過實(shí)驗(yàn)研究發(fā)現(xiàn)，MFO 算法在低維情況下有著顯著的全局搜索能力，但是隨著維度的不斷增加，MFO 算法的全局搜索能力會(huì)不斷的減小，易陷入局部最優(yōu).

Trivedi I N 等提出將標(biāo)準(zhǔn)的MFO 算法與Levy 飛行策略相結(jié)合，可以提高飛蛾撲火優(yōu)化算法的求解精度和收斂速率.因此本文將驗(yàn)證改進(jìn)后的飛蛾撲火優(yōu)化算法(標(biāo)準(zhǔn)的MFO算法與Levy 飛行策略相結(jié)合)—IMFO 算法在高維情況下的全局搜索能力、收斂速率以及求解精度.

為測試IMFO 算法的性能，本文選取 Sphere、Step、Sum-Different、SumSquares、Zakharov、Levy，6 個(gè)基準(zhǔn)測試函數(shù)，使用不同維度(dim=10，30，50，三種維度)對(duì)算法測試.設(shè)置算法的種群規(guī)模40，最大迭代次數(shù)為1000.因?yàn)榇嬖谌N不同的維數(shù)和6 種測試函數(shù)共18 種情況，所以基于每一種情況，都需獨(dú)立運(yùn)行MFO 和IMFO 算法各50 次.不同維度下，兩種算法的函數(shù)最優(yōu)值的平均值如表1 所示.從表1 可以看出不同維度下的IMFO 算法的求解精度均高于MFO 算法的求解精度;當(dāng)維度為50 維時(shí)，實(shí)驗(yàn)發(fā)現(xiàn)MFO 算法易于陷入局部最優(yōu)，其全部搜索能力小于IMFO 的全局搜索能力.本文選擇SumDifferent，Levy、Zakharov 三種測試函數(shù)的迭代過程圖進(jìn)行分析如圖1、圖2、圖3 所示(縱軸表示目標(biāo)函數(shù)值，橫軸表示迭代次數(shù))，從圖1、圖2、圖3 中可以看出，改進(jìn)后的 MFO算法在高維空間的全局搜索能力增強(qiáng)顯著，易于跳出局部最 優(yōu)解.

表1 2 種算法不同維度的最優(yōu)值比較Table 1 Optimal value comparison of two algorithms in different dimension

圖1 SumDifferent 函數(shù)迭代過程圖Fig.1 Performance for SumDifferent

圖2 Zakharov 函數(shù)迭代過程圖Fig.2 Performance for Zakharov

圖3 Levy 函數(shù)迭代過程圖Fig.3 Performance for Levy

4 算例應(yīng)用

假設(shè)在某次地震應(yīng)急救援中有5 個(gè)應(yīng)急物資救援點(diǎn)A1，A2，…A5和2 個(gè)災(zāi)害需求點(diǎn)B1和B2，且災(zāi)害需求點(diǎn)需求應(yīng)急物資救援點(diǎn)提供3 種物資，如急救藥品(單位:千克)、食品(單位:噸)和帳篷(單位:千頂)分別用 C1，C2，C3表示.其中應(yīng)急物資救援點(diǎn)可提供的各個(gè)物資數(shù)量和災(zāi)害需求點(diǎn)需求應(yīng)急物資的數(shù)量如表2 所示.

合理假設(shè)應(yīng)急物資救援點(diǎn)到災(zāi)害需求點(diǎn)的單位運(yùn)輸量成本c(單位:百元)和應(yīng)急物資救援點(diǎn)各種物資的單位裝載時(shí)間(單位:分鐘)如表3 所示.

當(dāng)各個(gè)救援點(diǎn)與救援點(diǎn)之間的道路存在損壞時(shí)，應(yīng)急物資救援點(diǎn)到災(zāi)害需求點(diǎn)的損壞距離X(單位:千米)以及相應(yīng)的程度系數(shù) α 如表4 所示(X/α)，且設(shè)當(dāng) 0≤α＜0.2 表示道路可行，無需施工隊(duì)修復(fù);0.2≤α＜0.75 表示道路可修復(fù);0.75≤α≤1 表示道路不可修復(fù).假設(shè)修復(fù)時(shí)間為0.5 小時(shí)/千米，最長可修復(fù)時(shí)間不得超過3.5 小時(shí)，當(dāng)修復(fù)時(shí)間超過3.5 小時(shí)表示救援點(diǎn)與需求點(diǎn)之間不可通行，反之表示兩者之間可以通行.(本文表2 到表4 的數(shù)據(jù)均為合理性假設(shè)得到的隨機(jī)數(shù)據(jù))

表2 救援點(diǎn)提供物資的數(shù)量和災(zāi)害點(diǎn)需求物資的數(shù)量Table 2 Quantity of supplies provided at the relief point and the quantity of materials needed at the disaster site

表3 單位運(yùn)輸量成本和應(yīng)急物資裝載時(shí)間Table 3 Unit transportation cost and the unit loading time of various materials in emergency material supply point

表4 損壞距離和相應(yīng)程度系數(shù)Table 4 Damage distance and corresponding coefficient

通過實(shí)驗(yàn)對(duì)比運(yùn)算，IMFO 算法的參數(shù)設(shè)置如下:飛蛾群體數(shù)為500 個(gè)，最大迭代次數(shù)為2000，個(gè)體位置信息的維度是根據(jù)算例的5 個(gè)救援點(diǎn)分別提供3 種物資到2 個(gè)需求點(diǎn)而確定，其維度為30.參考蔣杰輝［23］一文，本文設(shè)置時(shí)間成本系數(shù)ω 為1，權(quán)重滿足w1+w2=1，本例中根據(jù)專家評(píng)價(jià)法設(shè)置權(quán)重w1、w2分別為1/4 和3/4，即對(duì)于應(yīng)急物資優(yōu)化調(diào)度來講，物資裝載時(shí)間成本比運(yùn)輸成本更重要.

當(dāng)各個(gè)救援點(diǎn)與救援點(diǎn)之間的道路存在損壞時(shí)，在相同的迭代次數(shù)和相同的種群條件下，使用MFO 算法和IMFO 算法進(jìn)行15 次的求解運(yùn)算，得出的最優(yōu)目標(biāo)函數(shù)適應(yīng)值的結(jié)果如表5 所示.算出兩種算法的最優(yōu)目標(biāo)函數(shù)適應(yīng)值的最大值、最小值、平均值，其中IMFO 算法的最優(yōu)目標(biāo)函數(shù)適應(yīng)值的最大值、最小值、平均值依次為:328.875，323.625，323.975;MFO 算法的最優(yōu)目標(biāo)函數(shù)適應(yīng)值的最大值、最小值、平均值依次為 398.475，340.25，357.59.從表5 可知，在 15 次求解中，每次IMFO 算法求解出的目標(biāo)函數(shù)最優(yōu)值均小于MFO 算法求解的結(jié)果，且IMFO 算法求解出的目標(biāo)函數(shù)最優(yōu)值均在323.625 附近，且求解結(jié)果是 323.625 出現(xiàn)了 14 次，占總次數(shù)的93.3%.對(duì)比 IMFO 算法和 MFO 算法的最大值、最小值、平均值，明顯IMFO 算法求解結(jié)果優(yōu)于MFO 算法求解結(jié)果.

當(dāng)各個(gè)救援點(diǎn)與救援點(diǎn)之間的道路不存在損壞時(shí)，通過IMFO 求解出的目標(biāo)函數(shù)的最小值為305.625，其相應(yīng)的應(yīng)急物資調(diào)度方案如表6 所示.

表5 兩種算法下的最優(yōu)目標(biāo)函數(shù)適應(yīng)值Table 5 Optimal fitness of objective function under two algorithms

選擇15 次實(shí)驗(yàn)中的一次實(shí)驗(yàn)數(shù)據(jù)，通過IMFO 求解得到目標(biāo)函數(shù)的最小值為323.625，目標(biāo)函數(shù)適應(yīng)值的變化過程如圖4 所示，其相應(yīng)的應(yīng)急物資調(diào)度方案如表6 所示.對(duì)比兩種情況下的目標(biāo)函數(shù)適應(yīng)值以及調(diào)度方案表明:在道路損壞情況下，物資裝載過程中所消耗的時(shí)間以及運(yùn)載成本明顯增加，對(duì)于本例條件下，增加約5.9%.

圖4 目標(biāo)適應(yīng)值的迭代圖像Fig.4 Iterative image of target fitness

圖5 MFO、IMFO 最優(yōu)化迭代過程示意圖Fig.5 Schematic diagram of optimization iteration process of MFO and IMFO

采用MFO 算法求解道路損壞情況下的應(yīng)急物資調(diào)度方案如表6 所示，最優(yōu)化迭代曲線如圖5 所示，虛線為MFO 算法的目標(biāo)函數(shù)值迭代曲線，實(shí)線為IMFO算法的目標(biāo)函數(shù)值迭代曲線.MFO 算法的最小目標(biāo)函數(shù)值為 352.625，大于IMFO 算法求解得到的最優(yōu)目標(biāo)函數(shù)適應(yīng)值.從圖5 可知，IMFO 算法的迭代速率快于MFO 的迭代速率，也較MFO 算法在迭代中最先達(dá)到最優(yōu)解，由此可見，IMFO 算法在高維情況下的全局搜索能力方面比MFO 更強(qiáng)，不易陷入局部最 優(yōu)解.

表6 IMFO 和MFO 算法求解應(yīng)急物資調(diào)度方案Table 6 IMFO and MFO algorithms for emergency material scheduling

5 結(jié)束語

本文研究基于道路損壞情況下的道路可行、道路可修復(fù)和道路不可通行三種條件下的多救援點(diǎn)對(duì)多需求點(diǎn)的多種應(yīng)急物資調(diào)度問題，通過數(shù)據(jù)的預(yù)處理判辨救援點(diǎn)到需求點(diǎn)是否存在物資運(yùn)輸，建立同時(shí)兼顧運(yùn)輸過程中物資裝載總時(shí)間最少和所消耗成本最低的優(yōu)化目標(biāo)函數(shù)，使用改進(jìn)的飛蛾撲火優(yōu)化算法——IMFO 求解最優(yōu)應(yīng)急物資調(diào)配方案.通過測試函數(shù)測試和算例以及仿真實(shí)驗(yàn)驗(yàn)證了IMFO 算法在應(yīng)急物資調(diào)度的有效性以及可用性，并通過改進(jìn)后飛蛾撲火優(yōu)化算法求解出了一個(gè)基于道路損壞情況下的緊急物資調(diào)度方案，具有一定的實(shí)用性的、較好的社會(huì)應(yīng)用價(jià)值，與MFO 的結(jié)果進(jìn)行對(duì)比說明，IMFO 具有更優(yōu)的全局搜索能力和局部收斂速度.本文的不足之處是通過具體的算例而不是采用真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)分析，以及道路可行、道路可修復(fù)和道路不可通行三種條件都是靜態(tài)情況下的，在實(shí)際運(yùn)輸過程中，道路情況往往是會(huì)有變化的.基于道路損壞對(duì)應(yīng)急物資調(diào)度的影響是未來研究的主要方向，應(yīng)用性能更優(yōu)(收斂速度更快、全局搜索能力更強(qiáng))的群智能最優(yōu)化算法進(jìn)行結(jié)果求解可以解決更復(fù)雜的真實(shí)物資調(diào)度最優(yōu)化問題.