基于遺傳算法的三層大規(guī)模應急救援物資配置策略

何　勇，溫潔嫦，黃美華

(廣東工業(yè)大學 應用數(shù)學學院，廣東 廣州 510520)

基于遺傳算法的三層大規(guī)模應急救援物資配置策略

何勇，溫潔嫦，黃美華

(廣東工業(yè)大學 應用數(shù)學學院，廣東 廣州 510520)

摘要:在考慮受災地區(qū)對應救援物資需求量大的基礎上，研究了包括備選省級應急救援物資供應地、備選市縣級應急救援物資中轉(zhuǎn)地、救援物資急需地三層結構的車輛安排、路徑選擇、物資配送的應急救援物資配置問題；以應急救援物資配置的總成本最小、總的運輸時間最短、供應地和中轉(zhuǎn)地啟用個數(shù)最少為目標，建立數(shù)學優(yōu)化模型.使用遺傳算法求解獲得近似最優(yōu)的三層應急救援物資配置方案.

關鍵詞:應急救援；物資配送；車輛安排；路徑優(yōu)化；遺傳算法

近年來，國內(nèi)外各類大規(guī)模自然災害頻繁發(fā)生，因其具有嚴重次生災害等特點,給受災地區(qū)帶來了極大的人員傷亡以及嚴重的經(jīng)濟損失，同時在災后救援過程中的不計成本、盲目救援造成了嚴重浪費.大規(guī)模自然災害發(fā)生后，如何有效地在救援物資供應地安排車輛進行裝載，如何選擇車輛路徑快速運輸、分配應急救援物資，成了大規(guī)模應急救援物資配置的關鍵問題，是快速挽救生命、減少災民損失、降低經(jīng)濟損耗的基本途徑.

針對如何優(yōu)化應急物資配送這一問題，國內(nèi)外學者進行了大量有意義的研究.Sheu[l]探討總結了當前應急物資配置面臨的挑戰(zhàn)，并針對救援關鍵時期研究了面向大規(guī)模災難的應急救援物資的配送方法；Chang和Tseng等[2]針對洪災發(fā)生后，受災地區(qū)應急物資需求量不確定的問題，提出了適應不同災情信息的應急救援物資配送的模型；鄭斌和馬祖軍等[3]建立了一個應急救援物資需求量不精確的多目標LRP優(yōu)化策略；徐玖平等[4]對汶川特大地震災后應急救援物資配置問題進行了重建物資分配、運輸、配送中轉(zhuǎn)地選擇等一系列的實證研究；陳剛和張錦等[5]考慮了以應急物資保障過程為單目標的應急物資運輸—配送模型；詹沙磊和劉南[6]研究了多個物資供應點、多個受災點的應急救援車輛選址、路徑優(yōu)化、物資配送的多目標隨機規(guī)劃模型；廖成等[7]構建了大規(guī)模的應急救援模型，并考慮了更有效的求解方法.

綜上所述，國內(nèi)外學者對受災情況多變的應急救援物資配置問題，已經(jīng)進行了各種意義深遠的建模研究，并對相應模型提出了松弛的拉格朗日算法[8]、啟發(fā)式算法[9-10]、遺傳優(yōu)化智能算法[11-12]等多種適應不同環(huán)境的算法.但是由于突發(fā)的大規(guī)模事件這一類問題往往會造成災后應急救援物資配送的情況復雜多變，很難研發(fā)出應急救援物資配置通用的數(shù)學優(yōu)化模型與算法，且仍然有許多急需解決的問題.為此，本文基于應急物資急需量大的情況下，考慮把受災點物資包裝成標準單元物資，研究三層大規(guī)模應急救援物資配送策略，并使用遺傳算法對模型求解獲得近似最優(yōu)的方案.

1數(shù)學模型

1.1問題背景描述

救援應急物資配送在受災地區(qū)救援中最為關鍵，主要考慮問題是如何對受災地區(qū)急需的物資包裝分配以及如何安排裝載車輛、選擇運輸路徑對受災地區(qū)進行救災物資輸送.因突發(fā)災害復雜特殊、變化萬千，對這一類情況特殊的救援應急物資配送問題，很難探討出普遍適用的數(shù)學優(yōu)化模型與算法.結合實際問題，本文考慮的網(wǎng)絡簡化結構如圖1所示.

圖1　物資配送網(wǎng)絡的簡化結構

1.2模型建立

(1)

(2)

(3)

其中,目標函數(shù)(1)為應急救援物資配置的總成本，目標函數(shù)(2)為應急救援物資總的運輸時間，目標函數(shù)(3)為啟用的供應地和中轉(zhuǎn)地個數(shù).

目標轉(zhuǎn)化：為了達到更好的救援效果，結合應急救援物資配置的實際問題，在現(xiàn)實應急救援物資配置中，決策者一般更加注重目標函數(shù)(2).采用基于加權排序的方法，根據(jù)應急救援物資配置的總成本、總的運輸時間、啟用的供應地和中轉(zhuǎn)地個數(shù)這三者的重要性，取權重為λ1=0.3，λ2=0.5，λ3=0.2.將以上3個目標聚集成一個單目標.

轉(zhuǎn)化后目標函數(shù)：

f=λ1f1+λ2f2+λ3f3.

(4)

約束條件：

眾所周知，物質(zhì)交換原理由法國著名偵查學家埃德蒙·洛卡德提出，該理論主要說明了任何犯罪行為只要有客體之間的接觸都會發(fā)生物質(zhì)相互轉(zhuǎn)移。將這一學說的原理與信息化調(diào)查相結合，就形成了信息轉(zhuǎn)移原理。該理論強調(diào)犯罪過程中信息轉(zhuǎn)移現(xiàn)象與犯罪行為是共同體，是客觀存在的，監(jiān)察調(diào)查人員在尋找線索證據(jù)的時候不能忽視任何蛛絲馬跡。

(5)

uji≤xj,rkj≤yk?j∈M,i∈L,k∈N；

(6)

(7)

αiθ≤XjiΩ，?j∈M；

(8)

(9)

其中：L={i|i=1,2,…,l}為救援應急物資急需地集合；M={j|j=1,2,…,m}為備選市縣級應急救援物資中轉(zhuǎn)地集合；N={k|k=1,2,…,n}為備選省級應急救援物資供應地集合；αi(i=1,2,…,l)表示第i個應急救援物資急需地的物資數(shù)量；cji表示第j(j=1,2,…,m)個備選市縣級應急救援物資中轉(zhuǎn)地到第i(i=1,2,…,l)個應急救援物資急需地的距離；dkj表示由第k(k=1,2,…,n)個備選省級應急救援物資供應地到第j(j=1,2,…,m)個備選市縣級應急救援物資中轉(zhuǎn)地的距離.

xj,yk,uji,rkj(其中i=1,2,…,l;j=1,2,…,m;k=1,2,…,n)為0-1決策變量；如果啟用第j個市縣級救援物資中轉(zhuǎn)地時xj=1，否則xj=0；如果啟用第k個省級應急救援物資供應地時yk=1，否則yk=0；如果第i個應急救援物資急需地由第j個市縣級應急救援物資中轉(zhuǎn)地運輸物資時uji=1，否則uji=0；如果第j個市縣級應急救援物資中轉(zhuǎn)地由第k個省級應急救援物資供應地供應物資時rkj=1，否則rkj=0.

Xji,Ykj,Zk(其中i=1,2,…,l;j=1,2,…,m;k=1,2,…,n)為整數(shù)決策變量.Xji表示負責第j個市縣級應急救援物資中轉(zhuǎn)地到第i個應急救援物資急需地的車輛數(shù)量；Ykj表示負責第k個省級應急救援物資供應地到第j個市縣級應急救援物資中轉(zhuǎn)地的車輛數(shù)量；Zk表示安排在第k個省級應急救援物資供應地的車輛數(shù)量.

2算法設計

遺傳算法是一種仿效自然界“物競天擇、適者生存”的進化算法.根據(jù)問題，將目標設計成一個適應度函數(shù)，把問題所有可能取的解編碼為染色體，一系列的染色體構成一個種群.利用迭代的方式讓各個染色體經(jīng)過若干代的選擇、交叉、變異等運算來交換種群染色體的信息，并根據(jù)適應度評估染色體，優(yōu)勝劣汰，使其逐漸趨向問題的近似最優(yōu)解.本文參考文獻[13-17]，結合應急救援物資配置模型，提出算法流程如下.

2.1算法參數(shù)設置與編碼

(1) 設置最大的迭代代數(shù)Gen_max，種群規(guī)模K、交叉率pc和變異率pm.

(2) 對種群個體使用二進制遺傳編碼.每個染色體都由兩個子串組成，長度為m+n；其中第1個子串的長度為對應的備選市縣級應急救援物資中轉(zhuǎn)地的個數(shù)m，基因位為0-1，1表示對應備選的中轉(zhuǎn)地被啟用，0表示對應的中轉(zhuǎn)地不被啟用；第2個子串的長度為對應的備選省級應急救援物資供應地的個數(shù)n；基因位為0-1，1表示對應備選的供應地被啟用，0表示對應的供應地不被啟用.給出算法流程如下.

2.2算法具體步驟

(1) 初始群體的生成.本文采用英國Sheffield遺傳算法工具箱的crtbase函數(shù)創(chuàng)建任意種群規(guī)模為K=100，個體長度為m+n的二進制離散隨機種群，將其定義為一個矩陣，至此得到初始種群P(0).

(2) 適應度評估，根據(jù)適應度函數(shù)大小區(qū)分優(yōu)劣，評估每個染色體的適應度，優(yōu)勝劣汰.本文直接考慮模型轉(zhuǎn)化后的單目標函數(shù)式，取Fitness(i)=1/f(i)為適應度函數(shù)，其中f(i)為第i條染色體的目標函數(shù)值.

(3) 采用輪盤賭法進行選擇操作，從P(n)(其中n為迭代代數(shù))中選擇K個染色體進入下一代P(n+1).

(4) 采用單斷點交叉進行交叉操作，根據(jù)交叉概率pc=0.7判斷各個染色體是否進行交叉，以促進遺傳算法對解空間的搜索.

(5) 采用離散變異法進行變異操作，對(4)交叉后的染色體根據(jù)變異概率pm=0.02判斷該基因是否進行變異，產(chǎn)生新一代P(n+1).

(6) 算法結束，如果代數(shù)n>Gen_max，輸出最優(yōu)解；如果代數(shù)n≤Gen_max，重復(2).

3算例仿真

隨機抽取7個備選省級應急救援物資供應地，10個備選市縣級應急救援物資中轉(zhuǎn)地，30個應急救援物資急需地以及所需的應急救援物資數(shù)量.其中平均救援物資的單位質(zhì)量：θ=3 kg/件，每輛車單位距離的運輸時間：ε=0.015 h/km，單位距離運輸單位物資質(zhì)量的費用：δ=0.25元/(kg.km)，啟用每個供應地、中轉(zhuǎn)地的增設費用：ω=0.12百萬元/個，每輛車的最大裝載重：Ω=35 000 kg/輛.

采用matlab軟件，根據(jù)以上設計的遺傳算法編寫相應的程序，求解近似最優(yōu)的算例結果為應急救援物資配置的總成本為6 691.8百萬元，總的運輸時間為20 635 h，啟用的供應地和中轉(zhuǎn)地數(shù)量為12個.其中車輛安排、路徑選擇、物資配送的近似最優(yōu)結果見表1、表2和圖2.

表1　啟用的省級救援物資供應地以及物資配置策略

表2　啟用的市縣級應急救援中轉(zhuǎn)地以及物資配置策略

圖2　算例目標函數(shù)近似最優(yōu)的三層應急救援物資配置方案

Fig.2The three-layer emergency material allocation strategy of approximate optimal objective function of example

4結論

本文是在受災地區(qū)對應急救援物資急需量較大的基礎上，基于全國范圍這一大區(qū)域，以應急救援物資總的運輸時間最短、配置的總成本最小、供應地和中轉(zhuǎn)地啟用個數(shù)最少為目標，考慮了包括備選省級應急救援物資供應地、備選市縣級應急救援物資中轉(zhuǎn)地、救援物資急需地三層結構的應急救援物資配置模型，研究了應急救援車輛安排、路徑選擇、救援物資配送的應急救援物資配置問題.最后結合遺傳工具箱設計遺傳算法求解獲得近似最優(yōu)的三層應急救災物資配置方案.

參考文獻：

[1] SHEU J B.Challenges of emergency logistics management[J].Transportion Research Part E:Logistics and Transportation Review,2007,43(6):655-659.

[2] CHANG M S,TSENG Y L,CHEN J W.A scenario planning approach for the flood emergency logistics preparation problem under uncertainty[J].Transportation Research Part E: Logistics and Transportation Review,2007,43(6):737-754.

[3] 鄭斌,馬祖軍,方濤.應急物流系統(tǒng)中的模糊多目標定位路徑問題的研究[J].系統(tǒng)工程,2009.27(8):21-25.

ZHENG B,MA Z J,FANG T.Fuzzy muti-objective location routing problem in emergency logistics systems[J].Systems Engineering,2009,27(8):21-25.

[4] 徐玖平,馬艷嵐,段雪玲.汶川特大地震災后民營企業(yè)重建的優(yōu)選統(tǒng)籌模式[J].中國管理科學,2008,16(4):1-11.

XU J P,MA Y L,DUAN X L. The optimum seeking and overall planning model of the reconstructions of private enterprises in Wen Chuan post-earthquake[J].Chinese Journal of Management Science,2008,16(4):1-11.

[5] 陳剛,張錦,彭永濤.震后應急物資敏捷保障體系模型及算法[J].自然災害學報,2013,22(3):47-53.

CHEN G,ZHANG J,PENG Y T.Agile security system model and algorithm for post-earthquake urgent relief provisons[J].Journal of Natural Disasters,2013,22(3):47-53.

[6] 詹沙磊,劉南.基于災情信息更新的應急物資配送多目標隨機規(guī)劃模型[J].系統(tǒng)工程理論與實踐,2013,33(1):159-166.

ZHAN S L,LIU N.Multi-objective stochastic programming model for relief allocation based on disaster scenario information updates[J].Systems Enginerring Theory & Practice,2013,33(1):159-166.

[7] 廖成,許維勝,吳啟迪.大規(guī)模應急救援物資運輸模型的構建與求解[J].系統(tǒng)工程,2006,24(11):6-12.

MIAO C,XU W S,WU Q D.A transportation modal and solution of large-scale emergency relief commodeties[J].Systems Engineering,2006,24(11): 6-12.

[8] ?ZDAMAR L,EKINCI E,KüξüKY-AZICI B. Emergency logistics planing in natural disasters[J].Annals of Operation Research,2004,129(1):217-245.

[9] HAGHARNT A,YAN S,SHIN Y L.Optimal scheduling of emergency roadway repair and subsequent relief distribution[J].Computers & Operations Research,2009,36(6):2049-2065.

[10] 楊勃,杜冰,李小林.多受災點救災物資分配調(diào)度問題啟發(fā)式算法[J].系統(tǒng)工程,2012,30(1)97-103.

YANG B,DU B,LI X L. Euristics for distribution and scheduling of relief supplies among multiple disaster sites[J].Systems Engineering, 2012,30(1):97-103.

[11] MITSUO G,ADMI S.Hybrid genetic algorithm for multi-time period production/distribution planning[J].Computers & Industrial Engineering, 2005(48):799-809.

[12] 畢娜.0基于多目標遺傳算法的配送路徑問題研究[D].杭州:浙江工業(yè)大學機械工程學院,2007.

[13] 王紹仁,馬祖軍.震后隨機動態(tài)LRP多目標優(yōu)化模型及算法[J].計算機應用研究,2010,27(9):3283-3286.

WANG S R,MA Z J.Stochastic dynamic multi objective optimization location-routing model and algorithm in post-earthquake[J].Application Research of Computers,2010,27(9): 3283-3286.

[14] 郎茂祥.基于遺傳算法的物流配送路徑優(yōu)化問題研究[J].中國公路學報,2002,15(3):76-79.

LANG M X.Study of the optimizing of physical distribution routing problem based on genetic algorithm[J].China Journal of Highway and Transport,2002,15(3):76-79.

[15] 史峰,王輝,郁磊.MATLAB智能算法30個案例分析[M].北京:北京航空航天大學出版社,2011.

[16] DAVIS L.Handbook of Genetic Algorithm[M]. NewYork:Nostrand Reinhold,1991.

[17] 張軍,詹志軍.計算智能[M].北京:清華大學出版社,2009.

The Three Layers of Large-scale Emergency Material Allocation Strategy Based on the

GAHe Yong, Wen Jie-chang, Huang Mei-hua

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

Abstract:Based on the concern that the affected areas are in an urgent need of a large quantity of emergency relief materials, a study is conducted on the problems of vehicle arrangement, path selection, distribution in emergency material allocation in three layers including alternative provincial supplying spot, alternative municipal and county-level transitional place and the area in urgent need. An optimized mathematical model is figured out with the goals of minimum total cost, the shortest transport time and minimum supplying spots and transitional places in emergency material allocation. Finally, using GA, an optimized three-layer large-scale emergency material allocation scheme is proposed.

Key words:emergency relief; material distribution; vehicle arrangement; path optimization; genetic algorithms(GA)

收稿日期:2015-01-15

基金項目:廣東省特色創(chuàng)新項目(2014KTSCX055)

作者簡介:何勇(1990-),男，碩士研究生，主要研究方向為最優(yōu)化方法與應用. 通信作者: 溫潔嫦(1964-),女，教授，碩士生導師，主要研究方向為最優(yōu)化方法與應用、智能計算.E-mail:wjcpig@126.com

doi:10.3969/j.issn.1007-7162.2016.02.007

中圖分類號:F252; TP301

文獻標志碼:A

文章編號:1007-7162(2016)02-0037-05