后勤應急保障資源調度模型動態多目標算法研究

，，，

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

后勤應急保障資源調度模型動態多目標算法研究

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

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

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

后勤應急保障；資源調度；動態多目標算法

0 引言

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

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

1 后勤應急保障資源調度問題

為貼合應急保障任務實際，考慮應急保障資源種類多樣、資源需求連續、資源調度實時、軍地聯合保障點及任務點眾多等特點，提出基于模型的動態多目標決策算法，為更加詳細描述模型及便于理解，對相關問題作以下假設：

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

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

3)運輸工具在運輸過程中避免重復調度及運輸路線重合，保證每次運輸的有效性；

模型中相關的定義如下所示:

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

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

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

R={Rq|q=1,2,···NR}：后勤應急保障調度資源集合，Rq表示第q種資源，NR表示任務點需求資源總量。

2 動態多目標決策算法目標分析

2.1 應急保障資源調度效用

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

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

(1)

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

(2)

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

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

(3)

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

2.2 資源調度成本

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

(4)

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

1)優化方案后應急響應時間與理論最早應急響應時間相差時延產生的損失。

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

(5)

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

2)優化方案應急響應時間超過允許響應時間最大值而產生的損失。

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

(6)

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

2.3 任務點保障資源均衡

在救援過程中，如果在保障資源調度中將資源效用最優和成本最低作為調度中的目標，則可能導致不同地區保障資源分配差距過大情況，會影響到部隊完成救援任務的進度和標準，因此在應急保障資源調度過程中任務點的保障資源調度均衡是需要考慮目標之一。

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

(7)

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

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

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

(8)

3 動態多目標后勤應急保障資源調度模型算法及求解

3.1 模型公式

動態多目標后勤應急保障資源調度決策算法描述如式：

(3)

(4)

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

(8)

(9)

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

3.2 求解算法

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

(18)

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

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

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

Step3：重復Step2：，直到滿足結束條件為止。

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

圖1 動態多目標后勤應急保障資源調度模型算法流程

4 案例驗證

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

表1 初始保障需求

表2 各資源供應點在t時刻的存儲量

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

表4 任務受災點嚴重程度wj

表5 應急保障資源需求線性增長參數值ejq

表6 資源成本及運輸成本

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

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

表7 10次迭代D1、D2調度方案

表8 300次迭代D1、D2調度方案

表9 500次迭代D1、D2調度方案

三種迭代方式所得方案各相關指標比較如表10所示。

表10 三種迭代次數所得方案各相關指標比較

以上不同迭代次數所得應急保障資源調度方案表明，受災任務點的需求隨時間的變化、災情的發展而發生改變，體現了模型的動態變化，使資源保障更加精確、有效。由表可得出以下結論：

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

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

5 結論

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

[1] 崔國山，王鍇梁，湯新民．基于MAS的水上應急資源動態調配研究[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] 姜 卉，黃 鈞．罕見重大突發事件應急實時決策中的情景演變[J]．華中科技大學學報(社會科學版)．2009，23：104-108．

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

[5] 潘 郁，余 佳，達慶利．基于粒子群算法的連續性消耗應急資源調度[J]．系統工程學報，2007，22(5)：556-560．

[6] 陳 杰．基于遺傳算法的應急物資運輸調度[D]．哈爾濱：哈爾濱工業大學，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] 李華昌，謝淑蘭，易忠勝．遺傳算法的原理與應用[J]．礦冶，2005，14(1)：87-90．

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

[11] 余舟毅，陳宗基，周 銳．基于遺傳算法的動態資源調度問題研究[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-)，女，陜西西安人，教授，研究生導師，主要從事信息化方向的研究。

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

1671-4598(2017)09-0273-05

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

TP391.9

A