何　勇，溫潔嫦，黃美華

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

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

何勇，溫潔嫦，黃美華

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

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

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

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

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

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

1數(shù)學(xué)模型

1.1問題背景描述

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

圖1　物資配送網(wǎng)絡(luò)的簡化結(jié)構(gòu)

1.2模型建立

(1)

(2)

(3)

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

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

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

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

(4)

約束條件：

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

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

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

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

2算法設(shè)計(jì)

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

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

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

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

2.2算法具體步驟

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

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

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

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

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

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

3算例仿真

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

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn)：

[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] 鄭斌,馬祖軍,方濤.應(yīng)急物流系統(tǒng)中的模糊多目標(biāo)定位路徑問題的研究[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] 徐玖平,馬艷嵐,段雪玲.汶川特大地震災(zāi)后民營企業(yè)重建的優(yōu)選統(tǒng)籌模式[J].中國管理科學(xué),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] 陳剛,張錦,彭永濤.震后應(yīng)急物資敏捷保障體系模型及算法[J].自然災(zāi)害學(xué)報(bào),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] 詹沙磊,劉南.基于災(zāi)情信息更新的應(yīng)急物資配送多目標(biāo)隨機(jī)規(guī)劃模型[J].系統(tǒng)工程理論與實(shí)踐,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ī)模應(yīng)急救援物資運(yùn)輸模型的構(gòu)建與求解[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] 楊勃,杜冰,李小林.多受災(zāi)點(diǎn)救災(zāi)物資分配調(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基于多目標(biāo)遺傳算法的配送路徑問題研究[D].杭州:浙江工業(yè)大學(xué)機(jī)械工程學(xué)院,2007.

[13] 王紹仁,馬祖軍.震后隨機(jī)動態(tài)LRP多目標(biāo)優(yōu)化模型及算法[J].計(jì)算機(jī)應(yīng)用研究,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].中國公路學(xué)報(bào),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].北京:北京航空航天大學(xué)出版社,2011.

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

[17] 張軍,詹志軍.計(jì)算智能[M].北京:清華大學(xué)出版社,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

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

作者簡介:何勇(1990-),男，碩士研究生，主要研究方向?yàn)樽顑?yōu)化方法與應(yīng)用. 通信作者: 溫潔嫦(1964-),女，教授，碩士生導(dǎo)師，主要研究方向?yàn)樽顑?yōu)化方法與應(yīng)用、智能計(jì)算.E-mail:wjcpig@126.com

doi:10.3969/j.issn.1007-7162.2016.02.007

中圖分類號:F252; TP301

文獻(xiàn)標(biāo)志碼:A

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