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

賀體龍，樓文高，2

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

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

1 引 言

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

事實(shí)上，地震等災(zāi)害發(fā)生后，當(dāng)?shù)氐缆吠鶗?huì)遭到損壞，物資運(yùn)載過(guò)程中所消耗的時(shí)間以及成本也會(huì)隨道路的損壞程度產(chǎn)生相應(yīng)的變化.此前很少有學(xué)者研究此類問(wèn)題，王晶等［12］考慮了道路毀壞程度對(duì)運(yùn)行時(shí)間的修正，并利用網(wǎng)絡(luò)流的方法求解;姜春霞等［13］考慮了道路損壞情況、損毀程度及可修復(fù)性對(duì)車(chē)輛運(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)急物資車(chē)輛調(diào)度模型來(lái)解決物資調(diào)度問(wèn)題.雖然他們考慮了道路受損的情況，但是事實(shí)上，在實(shí)施調(diào)度之前，通過(guò)無(wú)人機(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)化問(wèn)題.文獻(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)度問(wèn)題，以運(yùn)輸過(guò)程中物資裝載總時(shí)間最少、所消耗成本最少為優(yōu)化目標(biāo)函數(shù)，用IMFO 算法求解最優(yōu)應(yīng)急物資調(diào)配方案，并與MFO 算法求解的結(jié)果進(jìn)行對(duì)比.

2 問(wèn)題描述與模型建立

2.1 問(wèn)題描述

設(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í)間為T(mén)0，根據(jù)路段不同的損毀情況，分配施工隊(duì)進(jìn)行施工，0≤α＜β 表示道路可行，無(wú)需派遣施工隊(duì)，表示道路可修復(fù)，派遣施工隊(duì)進(jìn)行修復(fù)，并加以修復(fù)時(shí)間最晚為T(mén)end進(jìn)行約束，若修復(fù)時(shí)間大于Tend，則表示此次路線不通;δ≤α≤1 表示道路不可修復(fù)，無(wú)需派遣施工隊(duì)，此次路線不通.要求以運(yùn)輸過(guò)程中物資裝載總時(shí)間最少和所消耗成本最少為優(yōu)化目標(biāo)，給出一個(gè)最優(yōu)的調(diào)度方案.

2.2 條件假設(shè)

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

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

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

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

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

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

2.3 模型建立

以運(yùn)輸過(guò)程中物資裝載總時(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)化算法，該算法的主要靈感來(lái)源于飛蛾在自然界中被稱為橫向定位的飛行方式.MFO 算法的尋優(yōu)過(guò)程可以抽象的理解為飛蛾尋焰與棄焰兩種行為.在尋優(yōu)迭代運(yùn)算過(guò)程中，飛蛾和火焰分別有獨(dú)特的公式來(lái)進(jìn)行的迭代運(yùn)算更新自己的位置.其中飛蛾是在搜索空間里的實(shí)際搜索主體，而火焰是飛蛾到目前為止搜索到的最好位置.因此，如果飛蛾找到一個(gè)更好的解，則每只飛蛾便在標(biāo)記火焰附近搜索并更新火焰.飛蛾通過(guò)這種過(guò)程就可以得到它的最優(yōu)解.通過(guò)實(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 算法在高維情況下的全局搜索能力、收斂速率以及求解精度.

為測(cè)試IMFO 算法的性能，本文選取 Sphere、Step、Sum-Different、SumSquares、Zakharov、Levy，6 個(gè)基準(zhǔn)測(cè)試函數(shù)，使用不同維度(dim=10，30，50，三種維度)對(duì)算法測(cè)試.設(shè)置算法的種群規(guī)模40，最大迭代次數(shù)為1000.因?yàn)榇嬖谌N不同的維數(shù)和6 種測(cè)試函數(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 三種測(cè)試函數(shù)的迭代過(guò)程圖進(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ù)迭代過(guò)程圖Fig.1 Performance for SumDifferent

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

圖3 Levy 函數(shù)迭代過(guò)程圖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 表示道路可行，無(wú)需施工隊(duì)修復(fù);0.2≤α＜0.75 表示道路可修復(fù);0.75≤α≤1 表示道路不可修復(fù).假設(shè)修復(fù)時(shí)間為0.5 小時(shí)/千米，最長(zhǎng)可修復(fù)時(shí)間不得超過(guò)3.5 小時(shí)，當(dāng)修復(fù)時(shí)間超過(guò)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

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

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

圖5 MFO、IMFO 最優(yōu)化迭代過(guò)程示意圖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)解，由此可見(jiàn)，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é)束語(yǔ)

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