，，，

(武警工程大學(xué)信息工程系, 西安 710086)

后勤應(yīng)急保障資源調(diào)度模型動態(tài)多目標(biāo)算法研究

鞏青歌，譚海佩，趙鵬皓，楊曦

(武警工程大學(xué)信息工程系,西安710086)

為更加貼合實際情況，更好地體現(xiàn)應(yīng)急保障資源調(diào)度過程中的實時性、調(diào)度目標(biāo)的多樣性，對應(yīng)急保障資源調(diào)度效用、資源調(diào)度成本和任務(wù)點保障資源均衡等目標(biāo)進行分析，研究了這三個目標(biāo)對應(yīng)急保障資源調(diào)度模型的影響，解決單目標(biāo)無法滿足調(diào)度需求的問題；引入時間變量t，使模型能夠依據(jù)實際需求實時改變資源調(diào)度策略，解決了無法體現(xiàn)應(yīng)急保障實施后的反饋作用及資源調(diào)度的動態(tài)性問題，并建立了后勤應(yīng)急保障資源調(diào)度模型，最后通過具有實際應(yīng)用背景的算例進行驗證，結(jié)果證明算法能夠表現(xiàn)模型的動態(tài)及多目標(biāo)兩個特點，符合保障任務(wù)實際情況，能夠為應(yīng)急保障方案的形成提供決策支持。

后勤應(yīng)急保障；資源調(diào)度；動態(tài)多目標(biāo)算法

0 引言

當(dāng)發(fā)生突發(fā)事件后，部隊根據(jù)受領(lǐng)任務(wù)的等級、屬性等信息進行應(yīng)急保障，為完成部隊第一時間到達任務(wù)地的目標(biāo)，保障決策需要快速調(diào)動保障物資。目前應(yīng)急資源調(diào)度中，已經(jīng)形成較為完整的理論，同時在實踐的基礎(chǔ)上建立模型，例如Agent理論、基于MAS資源動態(tài)調(diào)度模型[1]、DEA模型[2]等。

目前對資源調(diào)度方案主要考慮單需求點和多需求點兩種情形，如姜卉[3]研究了實時情況隨時間的變化規(guī)律及決策主體把握時間的發(fā)展規(guī)律，來達到對事件發(fā)展進行預(yù)測。陳達強[4]等在研究中加入了成本動態(tài)核算和災(zāi)難不完全撲滅兩個狀態(tài)，增加了影響決策的動態(tài)變化因素。潘郁等人[5]對持續(xù)性資源消耗的調(diào)度問題利用了粒子群算法進行求解。陳杰[6]設(shè)計了適合求解應(yīng)急物資運輸調(diào)度模型的遺傳算法，傳統(tǒng)遺傳算法進行了改進。Cheung[7]等人提出兩階段隨機規(guī)劃模型，解決救援初期供需失衡及物資運輸問題。Fiedrich[8]等人開發(fā)出地震災(zāi)害后資源調(diào)度決策系統(tǒng)。由于在實際情況中，隨著突發(fā)事件的發(fā)展，如群體性事件不斷升級、地震余震增強、洪災(zāi)中暴雨持續(xù)等情況，使得部隊執(zhí)行維穩(wěn)、救援任務(wù)的難度增加，投入的兵力及部署會做出調(diào)整，因而保障物資的調(diào)度模式、配置的數(shù)量及方式隨之改變，形成動態(tài)需求—供應(yīng)關(guān)系。以上模型沒有充分體現(xiàn)保障目標(biāo)的多樣性及救援工作的動態(tài)性，因此，本文提出了后勤應(yīng)急保障資源調(diào)度模型，考慮到模型具有多目標(biāo)及時間依賴性的特點，本文提出了一個基于遺傳算法的動態(tài)求解。

1 后勤應(yīng)急保障資源調(diào)度問題

為貼合應(yīng)急保障任務(wù)實際，考慮應(yīng)急保障資源種類多樣、資源需求連續(xù)、資源調(diào)度實時、軍地聯(lián)合保障點及任務(wù)點眾多等特點，提出基于模型的動態(tài)多目標(biāo)決策算法，為更加詳細描述模型及便于理解，對相關(guān)問題作以下假設(shè)：

1)對應(yīng)急保障資源正確、有效評估決定應(yīng)急保障任務(wù)的成敗，因此假設(shè)制定保障方案時各保障任務(wù)點所需資源可根據(jù)方案及部隊任務(wù)安排進行有效獲??；

2)對本部隊、友鄰部隊及地方單位資源儲備情況充分了解，因此資源屬性的相關(guān)信息均可掌握；

3)運輸工具在運輸過程中避免重復(fù)調(diào)度及運輸路線重合，保證每次運輸?shù)挠行裕?/p>

模型中相關(guān)的定義如下所示:

S={Si|i=1,2,···NS}：后勤應(yīng)急保障資源調(diào)度過程中提供資源點的集合(包括本部隊，友鄰部隊，地方單位等)，其中Si表示第i個資源提供點，NS表示資源供應(yīng)點的個數(shù)。

D={Dj|j=1,2,···ND}：后勤應(yīng)急保障任務(wù)點也是資源需求點集合，Dj表示第j個任務(wù)點，ND表示任務(wù)點個數(shù)。

C={Cp|p=1,2,···NC}：調(diào)度資源使用的交通工具集合，Cp表示第p個交通工具，NC表示工具個數(shù)。

R={Rq|q=1,2,···NR}：后勤應(yīng)急保障調(diào)度資源集合，Rq表示第q種資源，NR表示任務(wù)點需求資源總量。

2 動態(tài)多目標(biāo)決策算法目標(biāo)分析

2.1 應(yīng)急保障資源調(diào)度效用

資源效用值uijpq(t)指在應(yīng)急保障任務(wù)中資源發(fā)揮的保障效果，分為時間效用和使用效用，計算公式如式(1)：

uijpq(t)=usijq(t)·fijpq(t)

(1)

其中:usijq(t)表示t時刻從保障點Si運輸應(yīng)急保障資源Rq到資源使用地Dj時的使用效用，fijpq(t)表示將資源Rq從Si點利用Cp運輸工具送到Dj點的時間效用，計算公式如式(2)：

(2)

其中:ft(t)為時間效用函數(shù)，lij指資源保障點Si到部隊任務(wù)點Dj的距離；vp是指在理想狀態(tài)(不考慮干擾及道路擁堵狀態(tài))下Cp運輸速度；αp?[0,1]表示在資源運輸中，指揮車、救護車、多功能加油車、宿營車、炊事車、宣傳車、直升機等工具的可調(diào)用程度系數(shù)，值越大表明可用程度越高；βij?[0,1]表示運輸路線是否暢通，0表示不通，1表示暢通；

由以上可得從資源分配到運輸至任務(wù)點的效用hu(t)最大化公式為式(3)：

(3)

xijpq(t)指t時刻從資源保障點Si利用Cp運往部隊任務(wù)點Dj的應(yīng)急保障資源Rq的資源總量。

2.2 資源調(diào)度成本

應(yīng)急保障資源成本包括運輸成本、資源自身成本和應(yīng)急響應(yīng)時延造成的損失，資源調(diào)度成本最小化公式如式(4)：

(4)

aq指Rq單位資源的價值成本，bpq表示運輸工具Cp在單位距離運送Rq單位資源產(chǎn)生的運輸成本(包括運輸過程中的保存成本和損失成本)，Z(t)表示當(dāng)受領(lǐng)任務(wù)時準(zhǔn)備物資應(yīng)急響應(yīng)時延產(chǎn)生的損失，可分為兩部分：

1)優(yōu)化方案后應(yīng)急響應(yīng)時間與理論最早應(yīng)急響應(yīng)時間相差時延產(chǎn)生的損失。

tijpq為優(yōu)化方案后的應(yīng)急響應(yīng)時間，假設(shè)理論中受災(zāi)點最早的應(yīng)急響應(yīng)時間為tnjq，所謂理論值，是指本次保障任務(wù)能滿足保障條件的資源中，最快到達目的地的資源所用時間。因此，滿足資源需求的最佳方案的應(yīng)急響應(yīng)時間必然大于理論響應(yīng)時間，這是無法避免的時間損失。那么，第一部分損失是由于優(yōu)化方案后的最早應(yīng)急響應(yīng)時間與理論值相比的延長量而產(chǎn)生的，如式(5)：

(5)

wj為受災(zāi)點Dj受災(zāi)嚴重程度，δjq表示最佳方案應(yīng)急響應(yīng)時間超過理論最早應(yīng)急響應(yīng)時間的懲罰參數(shù)，其意義也表示受災(zāi)點Dj對Rq資源的緊急程度。

2)優(yōu)化方案應(yīng)急響應(yīng)時間超過允許響應(yīng)時間最大值而產(chǎn)生的損失。

假設(shè)受災(zāi)點對每一類必要的資源設(shè)定一個允許響應(yīng)的時間最大值tmiq(tmiq是個定值，對于不同的突發(fā)事件，其值有所不同)目的是希望這類資源都能夠在規(guī)定的時間內(nèi)趕到目的地，因此，最優(yōu)方案的應(yīng)急響應(yīng)時間不應(yīng)超過允許響應(yīng)時間最大值，對于超過的情況，可以乘以一個懲罰系數(shù)(其意義表示受災(zāi)點對資源的緊急程度)表示其對應(yīng)急響應(yīng)帶來的損失。那么，第二部分損失是應(yīng)急響應(yīng)時間超過允許響應(yīng)時間最大值而產(chǎn)生的，如式(6)：

(6)

gijq表示判定最早應(yīng)急響應(yīng)時間是否超過允許響應(yīng)最大時間，如果超過最大可容忍響應(yīng)時間，則gijq=1;否則gijq=0，ηjq表示最佳方案應(yīng)急響應(yīng)時間超過允許響應(yīng)時間最大值的懲罰參數(shù)。

2.3 任務(wù)點保障資源均衡

在救援過程中，如果在保障資源調(diào)度中將資源效用最優(yōu)和成本最低作為調(diào)度中的目標(biāo)，則可能導(dǎo)致不同地區(qū)保障資源分配差距過大情況，會影響到部隊完成救援任務(wù)的進度和標(biāo)準(zhǔn)，因此在應(yīng)急保障資源調(diào)度過程中任務(wù)點的保障資源調(diào)度均衡是需要考慮目標(biāo)之一。

為更確切表述資源調(diào)度均衡函數(shù)，本文給出應(yīng)急資源效用度SAj的定義：各任務(wù)點的有效資源總量與該任務(wù)點應(yīng)急保障資源總需求之比，如式(7)。

(7)

djq(t)為t時刻資源需求點Dj對資源Rq總需求，當(dāng)uijpq(t)=1，表示xijpq(t)為有效資源，當(dāng)uijpq(t)=0，表示xijpq(t)為無效資源。

我們以最大化各任務(wù)點最小滿意度作為應(yīng)急資源配置均衡的目標(biāo)表達式如式(8)：

hSA=maxmin{SA1,SA2,...SAj,...SAND}

(8)

3 動態(tài)多目標(biāo)后勤應(yīng)急保障資源調(diào)度模型算法及求解

3.1 模型公式

動態(tài)多目標(biāo)后勤應(yīng)急保障資源調(diào)度決策算法描述如式：

(3)

(4)

hSA=maxmin{SA1,SA2,...SAj,...SAND}

(8)

(9)

其中:siq(t)表示資源提供點Si存儲應(yīng)急保障存儲量，約束(10)資源需求總量不能超過該資源提供點存儲該資源的總量；約束(11)表示資源Rq分配到Dj點的總量需滿足其需求量，保證應(yīng)急保障的開展；約束(12)指擔(dān)負運輸任務(wù)的運輸工具Cp在必須屬于可用運輸工具集合C={Cp|p=1,2,...NC}；約束(13)表示任務(wù)點所需資源和調(diào)度的資源總量不能為負；(14)表示運輸工具Cp的承載能力，運輸工具承載資源的總量不能超過其承載力；(15)把受災(zāi)點Dj嚴重程度的權(quán)重系數(shù)歸一化，把受災(zāi)點Dj對Rq資源的緊急程度的權(quán)重系數(shù)歸一化；(16)用來判定最早應(yīng)急響應(yīng)時間是否超過允許響應(yīng)時間最大值，如果超過則gijq(t)=1，否則gijq(t)=0；(17)表示理論中受災(zāi)點最早的應(yīng)急響應(yīng)時間為tnjq計算公式。為了表示模型的實時動態(tài)性，模型中參數(shù)xijpq(t)、資源存儲量siq(t)、資源需求量diq(t)以及應(yīng)急行程時間tijpq均隨著時間t而改變。為了簡化模型，參數(shù)各受災(zāi)點緊急系數(shù)wj、應(yīng)急響應(yīng)時間超過允許響應(yīng)時間最大值的懲罰參數(shù)ηjq、最佳方案應(yīng)急響應(yīng)時間超過理論最早應(yīng)急響應(yīng)時間的懲罰參數(shù)δjq為設(shè)定的常數(shù)，其值可以根據(jù)當(dāng)?shù)氐膶嶋H情況設(shè)定經(jīng)驗值。

3.2 求解算法

遺傳算法是一種“適者生存”的算法，具有自適應(yīng)性、隨機等特點[9-10]，可以較好地體現(xiàn)本文模型的動態(tài)及多目標(biāo)的特點。為便于計算，采用0-1編碼隨機產(chǎn)生N個初始個體，在保證適應(yīng)度的前提下，進行遺傳操作從而完成進化。在分析模型特點后，運用選擇算子、交叉算子及變異算子，對于選擇算子，采用輪盤賭復(fù)制法[11]，如式(18)所示，被選中概率為個體的相對適應(yīng)度:

(18)

為貼合應(yīng)急保障實際情況，實現(xiàn)保障資源實時調(diào)度，迭代設(shè)置的時間變量t，進行計算。將最佳保障方案中最早應(yīng)急響應(yīng)時間sk(t0)作為模型新輸入，對保障方案相應(yīng)調(diào)整。具體步驟如下：

Step1：設(shè)當(dāng)前時間為t0，令t=t0,求該條件下的最佳保障方案φ(t0)和最早應(yīng)急響應(yīng)時間為sk(t0)。

Step2：令t=t0+sk(t0)，更新任務(wù)點對保障資源的需求、資源供應(yīng)點在t時刻的存儲量等輸入條件，重新計算t0+sk(t0)時刻的最佳調(diào)度方案φ[t0+sk(t0)]以及最早應(yīng)急響應(yīng)時間為sk[t0+sk(t0)]。

Step3：重復(fù)Step2：，直到滿足結(jié)束條件為止。

上述算法流程如圖1所示。

圖1 動態(tài)多目標(biāo)后勤應(yīng)急保障資源調(diào)度模型算法流程

4 案例驗證

2016年6月30日以來，長江中下游沿江地區(qū)及江淮、西南東部等地出現(xiàn)入汛以來最強降雨過程，其中湖北、安徽等省受災(zāi)最嚴重。湖北黃石市是此次洪水受災(zāi)最嚴重的市之一，黃石市陽新縣因暴雨造成2個受災(zāi)任務(wù)點D1、D2，一個受災(zāi)任務(wù)點需要轉(zhuǎn)移受災(zāi)群眾，另一受災(zāi)任務(wù)點是玉湖截流港潰口需在短時間內(nèi)將潰口合攏，現(xiàn)武警黃石支隊接上級命令出動兩組兵力向兩個任務(wù)點開進執(zhí)行抗洪搶險及救災(zāi)任務(wù)現(xiàn)有包括本支隊和地方單位在內(nèi)的4個保障物資供應(yīng)點，為簡化計算，采用以下保障物資：單兵食品、飲用水、帳篷、救生衣、推土機、挖掘機(租用)、醫(yī)療藥品七種資源。設(shè)受災(zāi)點對各類資源在t時刻的需求為djq(t)需求呈線性增長djq(t)=djq(0)·(1+ejqt),初始需求如表1。各資源供應(yīng)點在t的存儲量sjq(t)如表2。任務(wù)點對資源的緊急程度δjq的值如表3。任務(wù)點受災(zāi)嚴重程度的值如表4。應(yīng)急保障資源需求線性增長參數(shù)ejq值如表5。資源成本及運輸成本如表6。供應(yīng)點到任務(wù)點路程如表7，要求保證資源調(diào)度實時性情況下，得到使三個目標(biāo)綜合最優(yōu)化的調(diào)度方案。

表1 初始保障需求

表2 各資源供應(yīng)點在t時刻的存儲量

表3 任務(wù)點對保障資源的緊急程度δjq

表4 任務(wù)受災(zāi)點嚴重程度wj

表5 應(yīng)急保障資源需求線性增長參數(shù)值ejq

表6 資源成本及運輸成本

注：挖掘機租用每天為3000元

根據(jù)洪災(zāi)及部隊救援任務(wù)的實際情況可知：受災(zāi)點D1、D2理論最早應(yīng)急響應(yīng)時間分別為20 min、27 min，其允許響應(yīng)時間最大值分別為27 min、38 min。利用遺傳算法進行初次計算，可以得到最初的保障方案，鑒于實際應(yīng)急保障的動態(tài)特點，進過多次迭代后，所得方案才能符合實際需要。本文對動態(tài)多目標(biāo)決策算法在C#環(huán)境下編程實現(xiàn)，經(jīng)過10次、300次、500次(結(jié)果趨于穩(wěn)定)的迭代，受災(zāi)點D1、D2調(diào)度方案如表7～9。

表7 10次迭代D1、D2調(diào)度方案

表8 300次迭代D1、D2調(diào)度方案

表9 500次迭代D1、D2調(diào)度方案

三種迭代方式所得方案各相關(guān)指標(biāo)比較如表10所示。

表10 三種迭代次數(shù)所得方案各相關(guān)指標(biāo)比較

以上不同迭代次數(shù)所得應(yīng)急保障資源調(diào)度方案表明，受災(zāi)任務(wù)點的需求隨時間的變化、災(zāi)情的發(fā)展而發(fā)生改變，體現(xiàn)了模型的動態(tài)變化，使資源保障更加精確、有效。由表可得出以下結(jié)論：

1)從表7、8、9看出迭代為10次、300次、500次所得保障方案中，任務(wù)點D1的最早應(yīng)急響應(yīng)時間分別為23 min、24 min、22 min；D2最早應(yīng)急響應(yīng)時間分別為28 min、30 min、29 min，均超過D1、D2的理論最早應(yīng)急響應(yīng)時間，能夠貼合應(yīng)急保障任務(wù)的實際。

(2)由表10得出迭代10次的保障資源調(diào)度成本最低，保障資源調(diào)度效用和保障資源調(diào)度均衡值也小；迭代300次的保障資源調(diào)度效用和保障資源調(diào)度均衡值較高，同時成本也較高；迭代500次的保障資源調(diào)度效用和保障資源調(diào)度均衡值最高，成本也高，相較于迭代10次和300次的方案，成本高出3.2%和1.9%，但保障資源調(diào)度效用高出45%和23%，保障資源調(diào)度均衡高出28%和14%，因此迭代500次方案結(jié)果為最優(yōu)化保障方案。以上結(jié)果證明算法在保證動態(tài)調(diào)度資源的同時，也保證了模型多目標(biāo)的優(yōu)化。

5 結(jié)論

本文分析了基于實時信息的動態(tài)后勤應(yīng)急保障資源調(diào)度問題的輸入輸出條件，為體現(xiàn)應(yīng)急保障中資源調(diào)度的實時性及調(diào)度目標(biāo)的多樣性，引入時間變量t，對應(yīng)急保障資源調(diào)度效用、資源調(diào)度成本和任務(wù)點保障資源均衡多個目標(biāo)進行分析，將實際問題抽象為數(shù)學(xué)模型，提出適用于模型的動態(tài)多目標(biāo)求解算法，最后通過具有實際應(yīng)用背景的算例進行驗證，結(jié)果證明算法能夠表現(xiàn)模型的動態(tài)及多目標(biāo)兩個特點，具有良好的收斂性，符合保障任務(wù)實際情況，可以為應(yīng)急保障方案的形成提供決策支持。

[1] 崔國山，王鍇梁，湯新民．基于MAS的水上應(yīng)急資源動態(tài)調(diào)配研究[J]．物流工程與管理．2010，32：54-56．

[2] Church R, Velle C R. The Maximal Covering Location Problem[J]. Papers In Regional Science. 1974, 32(1): 101-118.

[3] 姜 卉，黃 鈞．罕見重大突發(fā)事件應(yīng)急實時決策中的情景演變[J]．華中科技大學(xué)學(xué)報(社會科學(xué)版)．2009，23：104-108．

[4] 陳達強，劉 南，廖亞萍．基于成本修正的應(yīng)急物流物資響應(yīng)決策模型[J]．東南大學(xué)學(xué)報(哲學(xué)社會科學(xué)版)．2009，11：67-70．

[5] 潘 郁，余 佳，達慶利．基于粒子群算法的連續(xù)性消耗應(yīng)急資源調(diào)度[J]．系統(tǒng)工程學(xué)報，2007，22(5)：556-560．

[6] 陳 杰．基于遺傳算法的應(yīng)急物資運輸調(diào)度[D]．哈爾濱：哈爾濱工業(yè)大學(xué)，2006．

[7] Cheung R K, Chen C Y. A two-stage stochastic network model znd solution methods for the dynamic empty container allocation problem[J]. Transportation Science, 1998, 32(2): 142-162.

[8] Fiedrich F, Gehbauer F, Rickers U. Optimized resource allocation for emergency response after earthquake disasters[J]. Safety Science, 2000, 35(1-3): 41-57.

[9] 李華昌，謝淑蘭，易忠勝．遺傳算法的原理與應(yīng)用[J]．礦冶，2005，14(1)：87-90．

[10] 葛繼科，邱玉輝，吳春明,等．遺傳算法研究綜述[J]．計算機應(yīng)用研究，2008，25(10)：2911-2916．

[11] 余舟毅，陳宗基，周 銳．基于遺傳算法的動態(tài)資源調(diào)度問題研究[J]．控制與決策，2004，19(11)：1308-1311．

ResearchonDynamicMulti-objectiveAlgorithmofLogisticsEmergencyResourceSchedulingModel

Gong Qingge，Tan Haipei，Zhao Penghao，Yang Xi

(Engineering University of PAPDepartment of Information Engineering Shaanxi Province Xi’an 710086,China)

To closer to realistic situation, better reflected the real-time and multi-objective characteristics of logistics emergency resource scheduling, analysis of the target of emergency resource scheduling utility, the cost of resource scheduling and security resources balanced. Researched the impact of three targets for logistics emergency resource scheduling model, to solve the problem of a single target poor meet the demand of scheduling. Introducing time variabletto implementation strategy of according to the demand to change resource scheduling, to solve the problem which reflect feedback of implement emergency safeguard and dynamic resource scheduling. Logistics emergency resource scheduling model was builded, through example validation, showed that algorithm can reflect dynamic and multi-objective performance of model, which is conformable to reality, to provide decision support for the formation of the emergency protection programs.

logistics emergency security; resource scheduling; dynamicmulti-objective algorithm

2017-05-26；

2017-07-13。

武警后勤科研立項基金(WHKL15-17)。

鞏青歌(1967-)，女，陜西西安人，教授，研究生導(dǎo)師，主要從事信息化方向的研究。

譚海佩(1991-)，男，湖北襄陽人，碩士研究生，主要從事武警信息化方向的研究。

1671-4598(2017)09-0273-05

10.16526/j.cnki.11-4762/tp.2017.09.070

TP391.9

A