多級多受災(zāi)點(diǎn)連續(xù)消耗應(yīng)急物資調(diào)度優(yōu)化策略

張 力 丹， 李 超， 陳 飆 松*， 李 杰

( 1.大連理工大學(xué) 工業(yè)裝備結(jié)構(gòu)分析國家重點(diǎn)實(shí)驗(yàn)室， 遼寧 大連 116024；2.佛山市雅潔源科技有限公司， 廣東 佛山 528200 )

多級多受災(zāi)點(diǎn)連續(xù)消耗應(yīng)急物資調(diào)度優(yōu)化策略

張 力 丹1， 李 超1， 陳 飆 松*1， 李 杰2

( 1.大連理工大學(xué) 工業(yè)裝備結(jié)構(gòu)分析國家重點(diǎn)實(shí)驗(yàn)室， 遼寧 大連 116024；2.佛山市雅潔源科技有限公司， 廣東 佛山 528200 )

災(zāi)后應(yīng)急救助十分關(guān)鍵，特別是多地同時(shí)受災(zāi)情況下．為此，考慮將災(zāi)民安置與物資運(yùn)輸一體化規(guī)劃，建立連續(xù)消耗多級應(yīng)急物資調(diào)配數(shù)學(xué)模型．在此基礎(chǔ)上，以應(yīng)急系統(tǒng)施救成本和施救不及時(shí)損失為目標(biāo)函數(shù)構(gòu)建優(yōu)化模型，并應(yīng)用遺傳算法(GA)和序列線性規(guī)劃(SLP)算法相結(jié)合策略對物資調(diào)配進(jìn)行優(yōu)化．構(gòu)造四級救災(zāi)物資調(diào)配算例模擬救災(zāi)過程．?dāng)?shù)值結(jié)果表明，使用GA全局尋優(yōu)結(jié)合SLP局部尋優(yōu)策略相較單一優(yōu)化算法能有效找到更優(yōu)解．所提出的優(yōu)化策略可為災(zāi)后多級多受災(zāi)點(diǎn)連續(xù)消耗應(yīng)急物資調(diào)度提供可行方案．

應(yīng)急物資分配調(diào)度；遺傳算法(GA)；序列線性規(guī)劃(SLP)算法；多級多受災(zāi)點(diǎn)；連續(xù)消耗

0 引 言

近年來，突發(fā)事件的頻繁發(fā)生對公眾生命與財(cái)產(chǎn)安全造成了嚴(yán)重危害．此類事件持續(xù)時(shí)間越長，受害者受到的威脅就越大．因此，災(zāi)害發(fā)生后，及時(shí)安置受災(zāi)群眾并高效地將分散的應(yīng)急物資集中于有消耗需求的地點(diǎn)具有重要意義，可極大地避免傷亡和損失[1]．

眾多學(xué)者針對物資調(diào)配問題進(jìn)行了相關(guān)的研究．潘郁等[2]運(yùn)用粒子群法求解單一事故爆發(fā)點(diǎn)的應(yīng)急物資調(diào)度問題．Zhang等[3]采用二叉空間分割樹改進(jìn)變異機(jī)制的遺傳算法，解決多種應(yīng)急物資針對單一事故爆發(fā)點(diǎn)分配問題．Ren等[4]在特定交通網(wǎng)絡(luò)中，構(gòu)造多種應(yīng)急物資分配的多周期動態(tài)模型，并用混合遺傳算法進(jìn)行求解．針對日益重要的多級分配問題，陳瑩珍等[5]將進(jìn)化差分方法應(yīng)用于多受災(zāi)點(diǎn)自救互救問題當(dāng)中．龐海云等[6]采用粒子群法以損失最小為單一目標(biāo)，考慮外部物資集散中心與災(zāi)區(qū)附近配送中心相合作進(jìn)行應(yīng)急物資調(diào)配的問題．研究工作已從多點(diǎn)對單點(diǎn)救援發(fā)展到多點(diǎn)對多點(diǎn)救援，問題更復(fù)雜且更面向具體需求．

在算法方面，此類問題多用新式智能算法,但由于其設(shè)計(jì)變量較多，求解規(guī)模較大，單一的智能優(yōu)化算法可能搜索不到令人滿意的結(jié)果，如粒子群法處理較大規(guī)模的問題(尤其是復(fù)雜多峰問題)時(shí)，易陷入早熟收斂并且對學(xué)習(xí)因子與慣性系數(shù)等參數(shù)具有一定的依賴性．遺傳算法求解規(guī)模較大的問題時(shí)需要增加交叉變異概率，但會導(dǎo)致算法局部搜索能力較差[7]．因此，很多學(xué)者致力于改進(jìn)智能算法以求得更優(yōu)解．如潘郁等[2]和龐海云等[6]使用了改進(jìn)的粒子群法；Hu等[8]、Ko等[9]和Gen等[10]將遺傳算法改進(jìn)求解應(yīng)急物資調(diào)度問題；張?zhí)祢湹萚11]將遺傳算法與蟻群算法相結(jié)合，使得前者為后者提供更好的信息素分配．但對于設(shè)計(jì)變量數(shù)目更加龐大的算例，運(yùn)用智能算法需要增加種群數(shù)量[12]，這使得基于種群更替的智能算法迭代過程變得更為冗長且對算法參數(shù)的選擇具有較強(qiáng)的依賴性，有時(shí)易陷入局部收斂．因此，在智能算法中引入局部搜索機(jī)制以增強(qiáng)算法性能是十分必要的[13-14]．

在眾多學(xué)者的研究成果基礎(chǔ)上，本文在模型的構(gòu)建與求解算法的選擇方面進(jìn)行進(jìn)一步的探索，在構(gòu)建模型方面做出如下改進(jìn)：(1)考慮到災(zāi)難通常多點(diǎn)爆發(fā)，構(gòu)建了國家、省、市、縣分級多點(diǎn)的連續(xù)消耗應(yīng)急物資調(diào)配模型．(2)考慮到災(zāi)民安置點(diǎn)應(yīng)當(dāng)為可以乘車輛抵達(dá)，或者靠近交通樞紐，能提供物資和服務(wù)的地方[15]，本文設(shè)置災(zāi)民安置與物資運(yùn)輸一體化的救助點(diǎn)，邊消耗邊出運(yùn)，省去一些物資中轉(zhuǎn)的復(fù)雜流程，從而將應(yīng)急物資快速高效地集中于災(zāi)民手中．(3)救災(zāi)過程中不僅要考慮應(yīng)急過程是否經(jīng)濟(jì)，更重要的是能夠有效地減少生命與財(cái)產(chǎn)損失．為此，本文以應(yīng)急系統(tǒng)施救成本和施救不及時(shí)損失為雙重目標(biāo)來優(yōu)化得出應(yīng)急物資調(diào)配的合理方案．在算法方面，本文考慮將遺傳算法(genetic algorithm，GA)全局尋優(yōu)與序列線性規(guī)劃(sequential linear programming，SLP)算法局部尋優(yōu)相結(jié)合求解此類大型應(yīng)急物資調(diào)配問題．并通過數(shù)值算例表明，使用GA結(jié)合SLP尋優(yōu)策略相較單一優(yōu)化算法能有效找到更優(yōu)解．

1 問題描述與優(yōu)化模型

1.1 多級多受災(zāi)點(diǎn)物資調(diào)配的問題描述

當(dāng)多地爆發(fā)災(zāi)害后，應(yīng)及時(shí)設(shè)立省、市、縣級(一、二、三級)近交通樞紐的災(zāi)民安置救助點(diǎn)(圖1)，為災(zāi)民提供必要的醫(yī)療服務(wù)、水和生活用品等．問題要求全國多地出救點(diǎn)向第一級救助點(diǎn)進(jìn)行物資運(yùn)輸．物資調(diào)配過程中，在滿足每級每點(diǎn)災(zāi)民需求的同時(shí)其余物資向下一級救助點(diǎn)出運(yùn)．在應(yīng)急物資缺失允許事后補(bǔ)足的條件下，盡可能滿足應(yīng)急地點(diǎn)的連續(xù)消耗并使得應(yīng)急出救活動成本與損失最小，從而使應(yīng)急物資層層滿足災(zāi)民需求，并在此基礎(chǔ)上合理安排各出救點(diǎn)以及災(zāi)民安置救助點(diǎn)的物資出運(yùn)量及路線．

圖1 應(yīng)急物資調(diào)配模型

設(shè)Aα(α=1，2，…，p)為全國的出救點(diǎn)，Bβ(β=1，2，…，q)為省級的救助點(diǎn)，Cγ(γ=1，2，…，r)為市級的救助點(diǎn)，Dλ(λ=1，2，…，u)為縣級的救助點(diǎn)．其中p代表全國的出救點(diǎn)個(gè)數(shù)，q、r、u分別代表省、市、縣級的救助點(diǎn)個(gè)數(shù)．物資由A=(A1

A2…Ap-1Ap)向B=(B1B2…Bq-1

Bq)同時(shí)出運(yùn)，當(dāng)有物資到達(dá)Bβ時(shí)，其在自我消耗物資的同時(shí)向市級救助點(diǎn)C=(C1C2…Cr-1Cr)同時(shí)出運(yùn)；當(dāng)有物資到達(dá)Cγ時(shí)，其在自我消耗物資的同時(shí)向縣級救助點(diǎn)D=(D1D2…

Du-1Du)同時(shí)出運(yùn)，Dλ只消耗物資不出運(yùn)．

1.2 多級多受災(zāi)點(diǎn)物資調(diào)配優(yōu)化模型的建立

設(shè)某點(diǎn)相鄰兩批物資到達(dá)的時(shí)間間隔為一個(gè)物資消耗周期(運(yùn)輸周期)．從發(fā)生災(zāi)害到各級救助點(diǎn)第1次有物資到達(dá)時(shí)，因施救不及時(shí)而造成的損失無法避免，因此不予考慮[2]．根據(jù)上文的問題描述建立優(yōu)化模型：

A組有p×q個(gè)設(shè)計(jì)變量，分別表示其向B組每一個(gè)救助點(diǎn)出運(yùn)的物資量，設(shè)xAα，Bβ為A組第α出救點(diǎn)向B組第β救助點(diǎn)運(yùn)輸?shù)奈镔Y量．

xA，Bβ=(xA1，BβxA2，Bβ…xAp-1，BβxAp，Bβ)

B組有p×q×r個(gè)設(shè)計(jì)變量，分別表示當(dāng)有物資到達(dá)B組時(shí)(物資總批次為出救點(diǎn)個(gè)數(shù)p)，B組每一個(gè)救助點(diǎn)向C組每一個(gè)救助點(diǎn)出運(yùn)的物資量，設(shè)xη，Bβ，Cγ(η=1，2，…，p)為B組第β救助點(diǎn)在接到第η次物資補(bǔ)給后，消耗物資同時(shí)向C組第γ救助點(diǎn)運(yùn)輸?shù)奈镔Y量．

C組有p×q×r×u個(gè)設(shè)計(jì)變量，分別表示當(dāng)有物資到達(dá)C組時(shí)(物資總批次為出救點(diǎn)個(gè)數(shù)與B組救助點(diǎn)個(gè)數(shù)乘積p×q)，C組每一個(gè)救助點(diǎn)向D組每一個(gè)救助點(diǎn)出運(yùn)的物資量．設(shè)xξ，Cγ，Dλ(ξ=1，2，…，p×q)為C組第γ救助點(diǎn)在接到第ξ次物資補(bǔ)給后，消耗物資同時(shí)向D組第λ救助點(diǎn)運(yùn)輸?shù)奈镔Y量．

目標(biāo)函數(shù)：

(1)

式中：Z為物資調(diào)配過程中的成本；K為救災(zāi)過程中的總損失費(fèi)用；Ki，A，Bβ為A組出救點(diǎn)向B組第β救助點(diǎn)出救時(shí)在運(yùn)輸周期[ti-1，Bβ，ti，Bβ)(i=1，2，…，p)中物資缺失的損失費(fèi)用；Kj，B，Cγ為B組救助點(diǎn)向C組第γ救助點(diǎn)出救時(shí)在運(yùn)輸周期[tj-1，Cγ，tj，Cγ)(j=1，2，…，p×q)中物資缺失的損失費(fèi)用；Kl，C，Dλ為C組救助點(diǎn)向D組第λ救助點(diǎn)出救時(shí)在運(yùn)輸周期[tl-1，Dλ，tl，Dλ)(l=1，2，…，p×q×r)中物資缺失的損失費(fèi)用；FAα，B為從Aα到B組出救時(shí)的單位成本(包括物資成本、運(yùn)輸成本、采購成本、存儲成本等)，F(xiàn)Bβ，C為從Bβ到C組出救時(shí)的單位成本，F(xiàn)Cγ，D為從Cγ到D組出救時(shí)的單位成本．

物資需求約束條件：

(2)

應(yīng)急時(shí)間約束條件：

(3)

當(dāng)某級某點(diǎn)在以一定的速度消耗應(yīng)急物資并向下一級出運(yùn)時(shí)，考慮到其在某時(shí)刻出現(xiàn)物資缺失應(yīng)加入損失費(fèi)用，用一個(gè)單位價(jià)格物資缺失單位時(shí)間的懲罰費(fèi)用比P提高負(fù)消耗所占比重，將其加入到目標(biāo)函數(shù)中以盡量避免物資缺失．某級某點(diǎn)的損失費(fèi)用如下：

情況1在某運(yùn)輸周期開始時(shí)應(yīng)急物資為負(fù)消耗，物資補(bǔ)給后仍為負(fù)消耗，如圖2所示．圖中G為救助點(diǎn)當(dāng)前物資量，xτ表示任意設(shè)計(jì)變量(補(bǔ)給物資量)．其懲罰費(fèi)用為

圖2 物資補(bǔ)給消耗過程1

A組向B組運(yùn)輸時(shí)：

(4)

B組向C組運(yùn)輸時(shí)：

(5)

C組向D組運(yùn)輸時(shí)：

(6)

情況2在一個(gè)物資消耗周期內(nèi)，某一時(shí)間點(diǎn)出現(xiàn)了應(yīng)急物資為0的情況，如圖3所示，此時(shí)在下一批應(yīng)急物資到達(dá)之前，將出現(xiàn)負(fù)消耗，其損失費(fèi)用為

A組向B組運(yùn)輸時(shí)：

(7)

B組向C組運(yùn)輸時(shí)：

(8)

C組向D組運(yùn)輸時(shí)：

(9)

(10)

(11)

(12)

其中xν，Bβ(ν=1，2，…，p)為A組向B組第β救助點(diǎn)出運(yùn)的第ν個(gè)運(yùn)輸周期中出運(yùn)的物資量，由xA，Bβ按出運(yùn)時(shí)間順序排序得到．xφ，Cγ(φ=1，2，…，p×q)為B組向C組第γ救助點(diǎn)出運(yùn)的第φ個(gè)運(yùn)輸周期中出運(yùn)的物資量，由xB，Cγ按出運(yùn)時(shí)間順序排序得到．xδ，Dλ(δ=1，2，…，p×q×r)為C組向D組第λ救助點(diǎn)出運(yùn)的第δ個(gè)運(yùn)輸周期中出運(yùn)的物資量，由xC，Dλ按出運(yùn)時(shí)間順序排序得到．

G(t)在每個(gè)積分中表示該運(yùn)輸周期的起始量，雖不同時(shí)刻值不同，但在積分公式中均為常量，具體表達(dá)形式如下：

(13)

(14)

(15)

其中Eν，Bβ為B組第β救助點(diǎn)在第ν次有物資到達(dá)時(shí)向C組r個(gè)救助點(diǎn)出運(yùn)物資的總和：

Eφ，Cγ為C組第γ救助點(diǎn)在第φ次有物資到達(dá)時(shí)向D組u個(gè)救助點(diǎn)出運(yùn)物資的總和：

綜上所述，損失費(fèi)用可概括為負(fù)消耗物資的運(yùn)輸成本乘以懲罰費(fèi)用P，其表示當(dāng)一個(gè)單位價(jià)格的物資缺失單位時(shí)間時(shí)，需要運(yùn)輸P倍的物資才能彌補(bǔ)當(dāng)前的損失．

圖3 物資補(bǔ)給消耗過程2

2 GA/SLP求解算法

2.1 求解算法簡介

GA/SLP混合算法通過將0階智能算法與基于梯度的數(shù)學(xué)規(guī)劃法相結(jié)合，二者分別發(fā)揮各自優(yōu)勢，取長補(bǔ)短，使其在求解多變量、大規(guī)模問題時(shí)得到更優(yōu)結(jié)果．本文將GA[16]與SLP相結(jié)合的主要原因有：(1)GA雖然具有較強(qiáng)的全局搜索能力且不依賴于梯度，但在求解后期，容易進(jìn)入早熟收斂．而SLP雖對初值敏感，但初值選取越接近最優(yōu)，其優(yōu)化結(jié)果越令人滿意．因此將GA收斂值代入SLP中繼續(xù)尋優(yōu)恰好可以發(fā)揮二者特長．(2)本文所計(jì)算模型為多級多受災(zāi)點(diǎn)連續(xù)性應(yīng)急物資消耗問題，此類問題具有上百個(gè)設(shè)計(jì)變量，使得GA種群數(shù)目較為龐大，由于傳統(tǒng)GA依賴于設(shè)計(jì)變量編碼解碼，其過程較為冗長，GA迭代次數(shù)較多后，收斂緩慢，此時(shí)引入SLP避免編碼解碼過程，加快迭代速度，并使問題收斂于更優(yōu)解．(3)結(jié)合多種優(yōu)化機(jī)制的混合算法在求解性能上也優(yōu)于采用單一優(yōu)化機(jī)制的原有算法[10]．

2.2 求解算法具體實(shí)現(xiàn)

(1)構(gòu)造設(shè)計(jì)變量數(shù)組xA，Bβ(β=1，2，…，q)，xB，Cγ(γ=1，2，…，r)，xC，Dλ(λ=1，2，…，u)．

(2)將每組的出運(yùn)時(shí)間由已知量計(jì)算后由小到大排列．

A組：tAα，Bβ(α=1，2，…，p；β=1，2，…，q)為A組第α出救點(diǎn)向B組第β救助點(diǎn)運(yùn)輸物資時(shí)所消耗的時(shí)間．將β固定的同時(shí)將tAα，Bβ由小到大排列得到β×α?xí)r間矩陣：

其中ti-1，Bβ

B組：tBβ，Cγ(β=1，2，…，q；γ=1，2，…，r)為B組第β救助點(diǎn)向C組第γ救助點(diǎn)運(yùn)輸物資時(shí)所消耗的時(shí)間．將γ固定，并將B組向C組出救時(shí)間與A組向B組出救時(shí)間分別對應(yīng)相加：

其中tj-1，Cγ

C組：tCγ，Dλ(γ=1，2，…，r；λ=1，2，…，u)為C組第γ救助點(diǎn)向D組第λ救助點(diǎn)運(yùn)輸物資時(shí)所消耗的時(shí)間．將λ固定，并將C組向D組出救時(shí)間與A組向C組出救時(shí)間分別對應(yīng)相加：

其中tl-1，Dλ

xBβ=(x1，Bβx2，Bβ…xp-1，Bβxp，Bβ)

xCγ=(x1，Cγx2，Cγ…xp×q-1，Cγxp×q，Cγ)

xDλ=(x1，Dλx2，Dλ…xp×q×r-1，Dλxp×q×r，Dλ)

(4)由式(13)～(15)計(jì)算各救助點(diǎn)當(dāng)前物資量．

(5)由式(7)～(9)計(jì)算每個(gè)消耗周期物資不足的懲罰成本．

(6)由式(1)構(gòu)造目標(biāo)函數(shù)．

(7)代入如圖4所示算法流程，其中隨機(jī)初始化滿足式(2)條件，xmax表示最大出運(yùn)量．

圖4 GA/SLP算法流程

3 數(shù)值算例與結(jié)果分析

3.1 原始數(shù)據(jù)

表1 A組原始數(shù)據(jù)

表2 B組原始數(shù)據(jù)

表3 C組原始數(shù)據(jù)

3.2 結(jié)果分析

通過優(yōu)化求解，得到A1，A2，…，A10的物資出運(yùn)量，列于表4．結(jié)果表明，此算例的解決方案無須所有出救點(diǎn)全部出救，只需A1、A2、A4、A5、A6、A7共6個(gè)出救點(diǎn)即可滿足要求．

優(yōu)化得到的B1、B2每次有物資到達(dá)后向C組每個(gè)救助點(diǎn)出運(yùn)的物資量列于表5．0表示該點(diǎn)該次只需自行消耗而無須向下一級救助點(diǎn)進(jìn)行出運(yùn)．B1救助點(diǎn)出運(yùn)總量為3 250.35，接收總量為6 018.61；B2救助點(diǎn)出運(yùn)總量為3 767.27，接收總量為5 282.48．由此可知，B組每個(gè)救助點(diǎn)接收總量遠(yuǎn)大于出運(yùn)總量．從表中可以看出，方案保證了每個(gè)消耗周期B組2個(gè)救助點(diǎn)至少有一個(gè)向C組某點(diǎn)進(jìn)行了出運(yùn)以滿足需求，這樣的出救安排較為合理．

優(yōu)化得到C1、C2、C3每次有物資到達(dá)后向D組每個(gè)救助點(diǎn)出運(yùn)的物資量列于表6．C1救助點(diǎn)出運(yùn)總量為1 225.70，接收總量為2 613.79；C2救助點(diǎn)出運(yùn)總量為939.61，接收總量為2 711.24；C3救助點(diǎn)出運(yùn)總量為634.09，接收總量為1 692.59．由此可知，C組每個(gè)救助點(diǎn)在應(yīng)急過程中接收總量遠(yuǎn)大于出運(yùn)總量．從表中可以看出，大多情況下，C組3個(gè)救助點(diǎn)在每個(gè)周期均有一個(gè)向D組某點(diǎn)運(yùn)輸，但由于D組規(guī)模小、人數(shù)少、消耗速率低，且無須向下一級救助點(diǎn)進(jìn)行出運(yùn)，在應(yīng)急中間過程中，D組某點(diǎn)接收到物資滿足自身需求時(shí)，允許C組3個(gè)救助點(diǎn)均不向其出運(yùn)，因此表中出現(xiàn)較多0也是較為合理的．

綜上所述，出救點(diǎn)由最初設(shè)定的10個(gè)優(yōu)化為6個(gè)，且B組、C組救助點(diǎn)在每個(gè)運(yùn)輸周期是否出運(yùn)及其出運(yùn)量也進(jìn)行了優(yōu)化安排，形成了邊消耗邊出運(yùn)的多級應(yīng)急救助模型，既節(jié)約了成本減少了物資的浪費(fèi)，又盡量將損失降低以達(dá)到物資滿足災(zāi)民需求的目的．此外，對于應(yīng)急物資調(diào)度模型優(yōu)化得到的所有設(shè)計(jì)變量均未超出約束范圍，優(yōu)化結(jié)果較為合理．圖5描述了各點(diǎn)在各自第1個(gè)消耗周期的出運(yùn)過程：所有出救點(diǎn)同時(shí)出運(yùn)，但到達(dá)先后順序不同，其中A1、A4分別為到達(dá)B1、B2的第1批物資．

表4 A組優(yōu)化結(jié)果

表5 B組優(yōu)化結(jié)果

表6 C組優(yōu)化結(jié)果

圖5 第1個(gè)消耗周期物資運(yùn)輸流程

本文就GA迭代1～1 000次的結(jié)果作為初值代入SLP進(jìn)行求解，如圖6所示，圖中n表示迭代次數(shù)，Yo表示目標(biāo)函數(shù)．在GA迭代次數(shù)較少時(shí)，其提供的初值離目標(biāo)值最優(yōu)解較遠(yuǎn)，SLP求解出的結(jié)果跳躍性較大．當(dāng)GA趨于收斂時(shí)，SLP的結(jié)果趨于穩(wěn)定，求解的效果較優(yōu)．因此表明，使用GA的收斂值作為SLP的初值是合理的．

圖6 GA對SLP的影響

本文將單純使用GA、SLP與GA/SLP進(jìn)行求解對比，如圖7所示．本文針對的模型為多級多受災(zāi)點(diǎn)應(yīng)急物資調(diào)度問題，問題求解開始時(shí)由于所有出救點(diǎn)均進(jìn)行出救活動其初始成本較高，優(yōu)化過程中逐漸略去不經(jīng)濟(jì)的出救點(diǎn)，成本逐漸降低，期間優(yōu)化過程跨度較大，優(yōu)化復(fù)雜程度較高．

單純使用GA時(shí)(圖7(a))，GA在前300次迭代時(shí)優(yōu)化效率較高，下降坡度較大，其后便趨于平穩(wěn)，從800次迭代開始，目標(biāo)函數(shù)變化幅度已很小，此時(shí)繼續(xù)使用GA，雖然目標(biāo)函數(shù)有繼續(xù)下降趨勢，但其坡度較緩、效率較低，由于模型設(shè)計(jì)變量較多，其耗費(fèi)大量的時(shí)間卻無法得到滿意的結(jié)果．單純使用SLP時(shí)(圖7(a))，其優(yōu)化趨勢為階梯型，在前800次迭代時(shí)目標(biāo)函數(shù)下降幅度較大，但其后在迭代次數(shù)約為1 000時(shí)，便達(dá)到收斂不再變化．此種收斂狀態(tài)只是得到局部最優(yōu)，由于多級多救災(zāi)點(diǎn)問題具有大規(guī)模性與復(fù)雜性，其初值選取往往離最優(yōu)值較遠(yuǎn)，因此單純的SLP在此種優(yōu)化模型下，很難得到較為滿意的解．當(dāng)GA與SLP聯(lián)合進(jìn)行求解時(shí)，GA迭代1 000次(已趨于收斂)代入SLP繼續(xù)求解，由圖7(b)可以看出，在引入SLP后本來已趨于平緩的曲線產(chǎn)生階梯式下降，其值與之前收斂值相比具有明顯差異．這表明混合算法可以得到更優(yōu)解，且符合模型已知條件，其最終優(yōu)化結(jié)果為2 930.62．

(a) 算法迭代過程1

(b) 算法迭代過程2

圖7 算法迭代結(jié)果

Fig.7 The result of algorithm iteration

4 結(jié) 論

(1)本文提出了以設(shè)置集災(zāi)民安置點(diǎn)與物資運(yùn)輸于一體的多層級救助點(diǎn)的方式來進(jìn)行應(yīng)急物資連續(xù)消耗分配調(diào)度的數(shù)學(xué)模型，以應(yīng)急系統(tǒng)施救成本和施救不及時(shí)損失為目標(biāo)函數(shù)構(gòu)建了優(yōu)化模型．

(2)應(yīng)用GA和SLP相結(jié)合策略對上百個(gè)設(shè)計(jì)變量的大規(guī)模物資調(diào)配測試算例進(jìn)行優(yōu)化，合理地安排出救點(diǎn)及各級災(zāi)民安置點(diǎn)的物資出運(yùn)量與路線．

(3)算例證明了GA與SLP聯(lián)合尋優(yōu)可以得到更優(yōu)解．本文提出的優(yōu)化策略能為災(zāi)后多級多受災(zāi)點(diǎn)連續(xù)消耗應(yīng)急物資調(diào)度提供更好的方案．

[1] YU Xianyu, ZHANG Yulin. The emergency scheduling engineering in single resource center [J].SystemsEngineeringProcedia, 2012,5:107-112.

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

PAN Yu, YU Jia, DA Qingli. Emergency resources scheduling on continuous consumption system based on particle swarm optimization [J].JournalofSystemsEngineering, 2007,22(5):556-560. (in Chinese)

[3] ZHANG Liming, LIN Yuhua, YANG Guofeng,etal. Emergency resources scheduling based on adaptively mutate genetic algorithm [J].ComputersinHumanBehavior, 2011,27(5):1493-1498.

[4] REN Xide, ZHU Jiangming, HUANG Jun. Multi-period dynamic model for emergency resource dispatching problem in uncertain traffic network [J].SystemsEngineeringProcedia, 2012,5:37-42.

[5] 陳瑩珍,趙秋紅. 基于公平原則的應(yīng)急物資分配模型與算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2015,35(12):3065-3073.

CHEN Yingzhen, ZHAO Qiuhong. The model and algorithm for emergency supplies distribution based on fairness [J].SystemsEngineering—Theory&Practice, 2015,35(12):3065-3073. (in Chinese)

[6] 龐海云,劉 南,吳 橋. 應(yīng)急物資運(yùn)輸與分配決策模型及其改進(jìn)粒子群優(yōu)化算法[J]. 控制與決策, 2012,27(6):871-874, 880.

PANG Haiyun, LIU Nan, WU Qiao. Decision-making model for transportation and distribution of emergency materials and its modified particle swarm optimization algorithm [J].ControlandDecision, 2012,27(6):871-874, 880. (in Chinese)

[7] DE JONG K A. An analysis of the behavior of a class of genetic adaptive systems [D]. Ann Arbor: University of Michigan Ann Arbor, 1975.

[8] HU Feihu, BAI Weihao, TIAN Chaohui. Research on scheduling emergency supplies featuring hierarchical linkage based on genetic algorithm [C] //InternationalConferenceonMaterialsEngineeringandInformationTechnologyApplications(MEITA2015). Paris: Atlantis Press, 2015.

[9] KO Y D, SONG B D, HWANG H. Location, capacity and capability design of emergency medical centers with multiple emergency diseases [J].ComputersandIndustrialEngineering, 2016,101:10-20.

[10] GEN M, GAO J, LIN L. Multistage-based genetic algorithm for flexible job-shop scheduling problem[M]//IntelligentandEvolutionarySystems. Berlin: Springer Berlin Heidelberg, 2009:183-196.

[11] 張?zhí)祢?李濟(jì)生,李 晶,等. 基于混合蟻群優(yōu)化的天地一體化調(diào)度方法[J]. 系統(tǒng)工程與電子技術(shù), 2016,38(7):1555-1562.

ZHANG Tianjiao, LI Jisheng, LI Jing,etal. Space-ground integrated scheduling based on the hybrid ant colony optimization [J].SystemsEngineeringandElectronics, 2016,38(7):1555-1562. (in Chinese)

[12] PONNAMBALAM S G, JAWAHAR N, KUMAR B. Estimation of optimum genetic control parameters for job shop scheduling [J].InternationalJournalofAdvancedManufacturingTechnology, 2002,19(3):224-234.

[13] KARTHIKEYAN S, ASOKAN P, NICKOLAS S,etal. A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems [J].InternationalJournalofBio-InspiredComputation, 2015,7(6):386-401.

[14] LI Junqing, PAN Quanke, LIANG Y C. An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems [J].ComputersandIndustrialEngineering, 2010,59(4):647-662.

[15] 中國地震應(yīng)急搜救中心. 災(zāi)民安置[M] // 地震安全手冊. 北京:地震出版社, 2009.

National Earthquake Response Support Service. Resettlement of displaced persons [M] //EarthquakeSafetyCheckList. Beijing: Seismological Press, 2009. (in Chinese)

[16] GOLDBERG D E.GeneticAlgorithmsinSearch,OptimizationandMachineLearning[M]. Boston: Addison-Wesley Longman Publishing Co., Inc., 1989.

[17] 張鼎逆,劉 毅. 基于改進(jìn)遺傳算法和序列二次規(guī)劃的再入軌跡優(yōu)化[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 2014,48(1):161-167.

ZHANG Dingni, LIU Yi. Reentry trajectory optimization based on improved genetic algorithm and sequential quadratic programming [J].JournalofZhejiangUniversity(EngineeringScience), 2014,48(1):161-167. (in Chinese)

Optimizationstrategyofemergencyresourcesschedulingofhierarchicalmultipledisastersitesduringcontinuousconsumption

ZHANG Lidan1, LI Chao1, CHEN Biaosong*1, LI Jie2

( 1.State Key Laboratory of Structural Analysis for Industrial Equipment, Dalian University of Technology, Dalian 116024, China； 2.Foshan Yajieyuan Science and Technology Co., Ltd., Foshan 528200, China )

After disaster,the emergency rescue is the key problem, especially when multiple sites are attacked. Considering an integrated scheduling issue of the victim shelter and the resources transportation, a mathematical model of scheduling and distribution of hierarchical emergency resources during continuous consumption is established. And then, an optimization model is presented, in which the objective is comprised of the rescue costs and the losses from lacking timely succor. Subsequently the genetic algorithm (GA) combined with sequential linear programming (SLP) algorithm is employed to solve the optimization model. A numerical example of a four-level resources scheduling is generated to simulate the progress of relieving the disaster. The numerical example verifies that GA combined with SLP can find a better solution, for the global search ability of GA is refined by the local search ability of SLP. The optimization strategy presented can provide a suitable resource scheduling solution in this field.

scheduling and distribution of emergency resources; genetic algorithm (GA);sequential linear programming (SLP)algorithm; hierarchical multiple disaster sites; continuous consumption

1000-8608(2017)05-0501-10

2016-10-19；

2017-04-18．

高等學(xué)校學(xué)科創(chuàng)新引智計(jì)劃資助項(xiàng)目(B14013)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(DUT15JJ(G)03).

張力丹(1992-)，女，碩士生，E-mail:zhangld@mail.dlut.edu.cn；陳飆松*(1973-)，男，教授，E-mail:chenbs@dlut.edu.cn.

N945.25

A

10.7511/dllgxb201705010