不確定環(huán)境下救災(zāi)部隊(duì)駐地選址及搜救路徑優(yōu)化

黃 茜， 王書勤， 鄧少鴻， 范林軍

(1.武警警官學(xué)院 基礎(chǔ)部，四川 成都 610213； 2.武警警官學(xué)院 分隊(duì)指揮系，四川 成都 610213； 3.長沙理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，湖南 長沙 410114； 4.武警警官學(xué)院 部隊(duì)管理系，四川 成都 610213)

0 引言

搶險(xiǎn)救災(zāi)中，災(zāi)區(qū)道路往往受到破壞，救災(zāi)分隊(duì)行進(jìn)時(shí)間不確定，受災(zāi)點(diǎn)所需救援時(shí)間也難以把握，不確定因素給部隊(duì)救災(zāi)行動(dòng)帶來了較大困難。在資源有限、時(shí)間緊迫的情況下，科學(xué)地進(jìn)行部隊(duì)駐地選址、救災(zāi)任務(wù)分配，規(guī)劃救災(zāi)分隊(duì)搜救線路，實(shí)現(xiàn)救災(zāi)效果總體最優(yōu)尤為重要?，F(xiàn)有文獻(xiàn)研究中地方應(yīng)急物流系統(tǒng)中的LRP(location-routing problem)優(yōu)化研究較多，但對(duì)不確定環(huán)境下救災(zāi)部隊(duì)駐地選址及救援路徑優(yōu)化研究較少。鄭斌等[1]以應(yīng)急物資運(yùn)達(dá)總時(shí)間最短和系統(tǒng)總成本最小為目標(biāo)，建立了LRP優(yōu)化模型；徐琴等[2]針對(duì)城市突發(fā)公共事件應(yīng)急物流系統(tǒng)中的LRP，建立了一個(gè)應(yīng)急救援時(shí)間滿意度最大的LRP模型；Boyer等[3]提出一個(gè)關(guān)于工業(yè)危險(xiǎn)廢物的LRP雙目標(biāo)混合整數(shù)規(guī)劃模型?；诖耍疚目紤]受災(zāi)點(diǎn)帶時(shí)間窗，受災(zāi)點(diǎn)所需救災(zāi)時(shí)間與救災(zāi)分隊(duì)行進(jìn)時(shí)間均服從正態(tài)分布，救災(zāi)分隊(duì)有有效救援時(shí)間約束等條件，建立了救災(zāi)總成本和總時(shí)間最短的LRP多目標(biāo)隨機(jī)規(guī)劃模型，并設(shè)計(jì)改進(jìn)遺傳算法成功求解。

1 問題建模

1.1 問題的提出

搶險(xiǎn)救災(zāi)中，在受災(zāi)點(diǎn)間的行進(jìn)時(shí)間及其所需救援時(shí)間隨機(jī)、各種資源有限的條件下，救災(zāi)部隊(duì)如何根據(jù)受災(zāi)點(diǎn)信息選擇駐地，確定救災(zāi)分隊(duì)數(shù)量及其搜救路線。

1.2 模型假設(shè)

(1)有多個(gè)備選駐地，各駐地的建設(shè)費(fèi)用已知。

(2)救災(zāi)分隊(duì)數(shù)已知，救災(zāi)分隊(duì)救災(zāi)效率、救災(zāi)固定成本和有效救災(zāi)時(shí)間相同，運(yùn)輸成本與運(yùn)輸距離成正比。

(3)每個(gè)受災(zāi)點(diǎn)只由一個(gè)救災(zāi)分隊(duì)救援(若需多個(gè)將其分割)，救災(zāi)難度可用救災(zāi)時(shí)間衡量。

(4)每個(gè)救災(zāi)分隊(duì)完成任務(wù)后返回原駐地。

(5)受災(zāi)點(diǎn)所需救災(zāi)時(shí)間及兩受災(zāi)點(diǎn)間的行進(jìn)時(shí)間均服從正態(tài)分布。

1.3 變量與符號(hào)說明

A={r|r=m+1,m+2,…,m+n}：受災(zāi)點(diǎn)集；

B={i|i=1,2,…,m}：備選駐地集；

S=A∪B：受災(zāi)點(diǎn)及備選駐地集；

V={k|k=1,2,…,K}：救災(zāi)分隊(duì)集；

Fi：駐地i的建設(shè)成本；

c：救災(zāi)分隊(duì)單位運(yùn)輸成本；

dij：i與j間的距離；

D：?jiǎn)⒂镁葹?zāi)分隊(duì)的固定成本；

tij：i到j(luò)的時(shí)間，為正態(tài)分布隨機(jī)變量；

T：救災(zāi)分隊(duì)有效救災(zāi)時(shí)間；

tr：r點(diǎn)所需救災(zāi)時(shí)間，當(dāng)r∈A，tr為正態(tài)分布隨機(jī)變量，當(dāng)r∈B，tr為0；

Tkr：救災(zāi)分隊(duì)k到達(dá)點(diǎn)r的時(shí)間；

[0,LTr]：受災(zāi)點(diǎn)r的救災(zāi)時(shí)間窗；

M：足夠大的正整數(shù)；

α1、α2：概率取值；

xi：0-1變量，備選駐地啟用時(shí)為1，否則為0；

zik：0-1變量，備選駐地i的救災(zāi)分隊(duì)k啟用時(shí)為1，否則為0；

ykij：0-1變量，救災(zāi)分隊(duì)k由i到j(luò)時(shí)為1，否則為0。

1.4 模型建立

根據(jù)以上思路，建立救災(zāi)問題中LRP多目標(biāo)隨機(jī)規(guī)劃模型如下。

(1)

(2)

s.t.

(3)

p{0≤Tkr+tr≤TLr}≥α2,?r∈A,?k∈V；

(4)

(5)

ykij=0,?i,j∈B,?k∈V；

(6)

zik≤xi,?i∈B,?k∈V；

(7)

(8)

(9)

(10)

ykij(Tkj-Tki)≥0,?i,j∈S,?k∈V；

(11)

xi={0,1},?i∈B；

(12)

ykij={0,1},?i,j∈S,?k∈V；

(13)

zik={0,1},?i∈B,?k∈V。

(14)

其中，式(1)為要求成本總和達(dá)到最?。皇?2)為要求救災(zāi)總時(shí)間最短；式(3)表示救災(zāi)分隊(duì)總救災(zāi)時(shí)間小于有效救災(zāi)時(shí)間的概率不小于α1；式(4)表示救災(zāi)分隊(duì)救災(zāi)完成時(shí)間位于受災(zāi)點(diǎn)時(shí)間窗內(nèi)的概率不小于α2；式(5)表示啟用的備選駐地就有救災(zāi)分隊(duì)進(jìn)行救災(zāi)；式(6)表示救災(zāi)分隊(duì)不在駐地間來往；式(7)表示啟用的備選駐地才有救災(zāi)分隊(duì)派出；式(8)表示救災(zāi)分隊(duì)從被分到的駐地出發(fā)；式(9)表示救災(zāi)分隊(duì)進(jìn)入某受災(zāi)點(diǎn)，也從該點(diǎn)出去；式(10)表示受災(zāi)點(diǎn)只由一個(gè)救災(zāi)分隊(duì)救災(zāi)；式(11)表示到達(dá)受災(zāi)點(diǎn)的時(shí)間具有先后順序；式(12)、(13)、(14)為0-1變量約束[4]。

2 改進(jìn)遺傳算法設(shè)計(jì)

為求解模型，基于基本遺傳算法，提出了一種改進(jìn)遺傳算法。與基本遺傳算法相比，該算法主要在染色體編碼、遺傳操作設(shè)計(jì)及適應(yīng)度函數(shù)的構(gòu)造方面根據(jù)問題實(shí)際進(jìn)行了針對(duì)性改進(jìn)。在適應(yīng)度函數(shù)上，基本遺傳算法使用式(15)，而改進(jìn)遺傳算法使用式(16)：

f=z1+z2+z3+z4；

(15)

(16)

2.1 編碼設(shè)計(jì)

染色體由3段基因組成，利用救災(zāi)分隊(duì)、受災(zāi)點(diǎn)、備選駐地編號(hào)編碼，具體編碼方式如表1所示。

表1 染色體編碼方式Table 1 Chromosome coding method

表1中，n為受災(zāi)點(diǎn)個(gè)數(shù)，K為救災(zāi)分隊(duì)數(shù)量，m為備選駐地?cái)?shù)，第1段由自然數(shù)1～K排列而成，第2段由自然數(shù)(m+1)～(m+n)排列而成，第3段由1～m中隨機(jī)選擇自然數(shù)排列而成。如：若K為4(1～4)，m為3個(gè)，n為6個(gè)(4～9)，則染色體244431-479856-2121表示1、2號(hào)備選駐地啟用，2、4、3、1號(hào)救災(zāi)分隊(duì)的搜救路線分別為2-4-2、1-7-9-8-1、2-5-2、1-6-1[6-7]。

2.2 適應(yīng)度函數(shù)構(gòu)造

(1)隨機(jī)約束處理。利用罰函數(shù)思想，將模型中的隨機(jī)約束處理如下。

(17)

從而有

(18)

所以式(2)可以轉(zhuǎn)化為

(19)

式中：Φ-1(α1)可由標(biāo)準(zhǔn)正態(tài)分布表查得。

由此可以構(gòu)造罰函數(shù)：

(20)

式中：M1是一個(gè)足夠大的數(shù)。

(21)

式中：L是分隊(duì)k搜救線路上的點(diǎn)(駐點(diǎn)及受災(zāi)點(diǎn))集，L′是線路上點(diǎn)r前的點(diǎn)集，M2是一個(gè)足夠大的數(shù)。[8-9]

此時(shí)，目標(biāo)函數(shù)可轉(zhuǎn)化為

(22)

(2)適應(yīng)度函數(shù)構(gòu)造。改進(jìn)遺傳算法的適應(yīng)度函數(shù)為f。

2.3 遺傳操作的設(shè)計(jì)

求解過程中，采用了選擇、交叉、變異3種遺傳操作。

選擇操作中主要采取精英法與輪盤賭法相結(jié)合的方法。用適應(yīng)度函數(shù)的倒數(shù)構(gòu)造輪盤賭法，每次依概率隨機(jī)選擇種群中的染色體；同時(shí)采用精英法，保留每次迭代的最好染色體，保證算法收斂。而基本遺傳算法往往只采用輪盤賭法。

交叉操作分3個(gè)基因段進(jìn)行，在選中的2個(gè)父代中分段隨機(jī)選擇2點(diǎn)k1、k2確定交叉點(diǎn)或匹配交叉基因串，然后再雙點(diǎn)交叉與部分匹配交叉。若交叉后不合法，變更未參與交叉的基因使其合法，保存優(yōu)秀染色體，具體操作如圖1及圖2所示。

圖1 雙點(diǎn)交叉示意圖Figure 1 Diagram of two points crossing

圖2 部分匹配交叉示意圖Figure 2 Diagram of partial matching crossing

變異操作在同一條染色體中分段進(jìn)行，先隨機(jī)選擇2點(diǎn)，選址基因采用對(duì)換變異法，路徑基因采用逆轉(zhuǎn)變異法，具體操作如圖3及圖4所示[10-12]。

圖3 選址基因?qū)Q變異法示意圖Figure 3 Diagram of swap mutation

圖4 路徑基因逆轉(zhuǎn)變異法示意圖Figure 4 Diagram of reverse mutation

2.4 改進(jìn)遺傳算法流程

改進(jìn)遺傳算法設(shè)計(jì)流程如圖5所示。

圖5 改進(jìn)遺傳算法設(shè)計(jì)流程圖Figure 5 Flow chart of the improved genetic algorithm

3 算例分析

3.1 算例陳述

某部隊(duì)在抗震救災(zāi)中的救災(zāi)部隊(duì)備選駐地坐標(biāo)及建設(shè)成本如表2所示，受災(zāi)點(diǎn)信息如表3所示，受災(zāi)點(diǎn)間行進(jìn)時(shí)間的均值和方差如表4和表5所示。救災(zāi)分隊(duì)最大救災(zāi)時(shí)間為10 h，固定成本為0.5萬元，單位運(yùn)輸成本為0.01萬元，懲罰系數(shù)M1、M2均設(shè)為30，救災(zāi)分隊(duì)到達(dá)受災(zāi)點(diǎn)的時(shí)間位于受災(zāi)點(diǎn)救災(zāi)時(shí)間窗的概率及救災(zāi)分隊(duì)耗時(shí)位于最大有效救災(zāi)時(shí)間內(nèi)的概率均為95%。

表2 救災(zāi)部隊(duì)備選駐地?cái)?shù)據(jù)Table 2 Data of alternative stations of earthquake relief troops

表3 受災(zāi)點(diǎn)數(shù)據(jù)Table 3 Data of disaster sites

3.2 改進(jìn)遺傳算法求解

在MATLAB中設(shè)置交叉概率pc=0.8，變異概率pm=0.35，置信度為0.95，最大迭代次數(shù)nc=50，種群規(guī)模popsize=50，計(jì)算耗時(shí)487.313 3 s，得到如下結(jié)果。

表4 部分受災(zāi)點(diǎn)間行駛期望時(shí)間/hTable 4 Expected travel time between some disaster sites

表5 部分受災(zāi)點(diǎn)間行駛時(shí)間方差/h2Table 5 Variance of travel time between some disaster sites

最優(yōu)路徑為3-21-18-3，3-19-5-3，1-22-15-1，1-6-1，1-17-7-20-1，3-14-23-3，3-10-11-16-3，3-12-3，1-8-9-1，3-4-13-3；費(fèi)用成本為108.027 3萬元；2種懲罰值為0；總救災(zāi)時(shí)間值為73.268 3 h；最小歸一化目標(biāo)函數(shù)值為7.715e-23。部隊(duì)選擇了1號(hào)和3號(hào)駐地，救災(zāi)任務(wù)分配給10個(gè)救災(zāi)分隊(duì)，各分隊(duì)均能在受災(zāi)點(diǎn)的時(shí)間窗內(nèi)完成救災(zāi)，且不超過其最大有效救災(zāi)時(shí)間。

3.3 基本遺傳算法及改進(jìn)蟻群算法的求解

為檢驗(yàn)改進(jìn)遺傳算法的優(yōu)越性，本文同時(shí)利用基本遺傳算法及文獻(xiàn)[13]中的改進(jìn)蟻群算法對(duì)問題進(jìn)行求解，結(jié)果如表6及圖6～9所示。

表6 本文算法與其他算法結(jié)果比較Table 6 Comparison results with other algorithms

圖6 改進(jìn)遺傳算法救災(zāi)分隊(duì)搜救路徑圖Figure 6 Roads of disaster relief teams of the improved genetic algorithm

圖7 基本遺傳算法救災(zāi)分隊(duì)搜救路徑圖Figure 7 Roads of disaster relief teams of the basic genetic algorithm

圖8 2種遺傳算法最優(yōu)值進(jìn)化圖Figure 8 Evolution graph of optimal value of the two genetic algorithms

圖9 改進(jìn)蟻群算法救災(zāi)分隊(duì)搜救路徑圖Figure 9 Roads of disaster relief teams of the improved ant colony algorithm

3.4 結(jié)果分析

由結(jié)果可知，改進(jìn)遺傳算法總救災(zāi)時(shí)間較短且懲罰值為0，而基本遺傳算法的總救災(zāi)時(shí)間稍長，改進(jìn)蟻群算法救災(zāi)總時(shí)間短，救災(zāi)費(fèi)用成本低，但其2種懲罰值較大，難以完成救災(zāi)任務(wù)。綜上所述，改進(jìn)遺傳算法與其他2種算法相比，具有較好的性能。

4 結(jié)論

本文分析了救災(zāi)環(huán)境中的不確定因素，建立了救災(zāi)部隊(duì)駐地選址和救災(zāi)分隊(duì)搜救路徑問題的隨機(jī)多目標(biāo)規(guī)劃模型，通過構(gòu)造適應(yīng)度函數(shù)、設(shè)計(jì)編碼方法等手段，提出了一種改進(jìn)遺傳算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)遺傳算法能在稍微增加費(fèi)用成本的前提下，實(shí)現(xiàn)懲罰值為0且救災(zāi)總時(shí)間較短(73.268 3 h)的優(yōu)越綜合性能。研究結(jié)果對(duì)抗震救災(zāi)行動(dòng)組織具有一定的參考價(jià)值。