孫欣欣 李珊紅

(合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系， 合肥 230601)

救災(zāi)應(yīng)急物資調(diào)度是應(yīng)急管理工作的重要環(huán)節(jié)，直接關(guān)系到救災(zāi)工作的效率。及時(shí)而有效地將災(zāi)區(qū)急需的各種應(yīng)急物資送到各個(gè)受災(zāi)點(diǎn)，可以減少甚至避免人員傷亡，降低災(zāi)害可能帶來(lái)的損失和影響。因此，救災(zāi)應(yīng)急物資調(diào)度與普通的物資調(diào)度不同，它對(duì)物資調(diào)度方案的合理性、科學(xué)性有著更高的要求。具體來(lái)講，就是要使救災(zāi)物資在盡可能短的時(shí)間內(nèi)運(yùn)達(dá)災(zāi)區(qū)，分配的物資要能夠最大程度地滿足各個(gè)受災(zāi)點(diǎn)的需求，同時(shí)還要考慮將調(diào)度運(yùn)輸成本盡可能控制在合理范圍內(nèi)。這是一個(gè)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化的問(wèn)題。

20世紀(jì)90年代以來(lái)，許多學(xué)者對(duì)此問(wèn)題進(jìn)行了研究。甘勇等人以最小化運(yùn)輸成本和時(shí)間成本的總和為目標(biāo)，建立了混合整數(shù)規(guī)模模型，并設(shè)計(jì)了一種啟發(fā)式算法對(duì)模型進(jìn)行求解[1]，但他們的研究只是針對(duì)單個(gè)受災(zāi)點(diǎn)的情況。胡飛虎等人針對(duì)多供應(yīng)點(diǎn)、多受災(zāi)點(diǎn)的應(yīng)急物資調(diào)度問(wèn)題建立了模型，并運(yùn)用遺傳算法進(jìn)行求解，但他們只研究了運(yùn)輸時(shí)間最小化的單目標(biāo)優(yōu)化問(wèn)題[2]。本次研究，將探討在一次性消耗條件下，涉及多個(gè)儲(chǔ)備庫(kù)、多個(gè)受災(zāi)點(diǎn)、多種應(yīng)急物資的復(fù)雜問(wèn)題組合優(yōu)化調(diào)度方案，在應(yīng)急物資需求種類及數(shù)量約束下，構(gòu)建基于運(yùn)輸時(shí)間最短、出救儲(chǔ)備庫(kù)最少的多目標(biāo)調(diào)度模型，并基于遺傳算法進(jìn)行問(wèn)題求解。

1 應(yīng)急物資調(diào)度問(wèn)題建模

1.1 問(wèn)題描述

針對(duì)多儲(chǔ)備庫(kù)、多受災(zāi)點(diǎn)、多種應(yīng)急物資的情況，定義如下變量：

N個(gè)儲(chǔ)備庫(kù)，S={A1，A2，A3，…，AN}；M個(gè)受災(zāi)點(diǎn)，D={D1，D2，D3，…，DM}；K種物資，G={G1，G2，G3，…，GK}。w為一種物資的分配方案，w={wrpq}N×M×K，wrpq表示儲(chǔ)備庫(kù)r到受災(zāi)點(diǎn)p調(diào)度物資q的數(shù)量。

災(zāi)區(qū)應(yīng)急物資調(diào)度問(wèn)題的目標(biāo)是運(yùn)輸時(shí)間最短、出救應(yīng)急點(diǎn)最少。此問(wèn)題還涉及滿足以下約束條件：每個(gè)儲(chǔ)備庫(kù)的所有物資的分配量，均不得超過(guò)其儲(chǔ)備量；各個(gè)受災(zāi)點(diǎn)得到的所有物資的數(shù)量，均能分別滿足其需求量。因此，可以建立如下數(shù)學(xué)模型：

s.t.

wrpq≥0,trp≥0,?r∈S,?p∈D,?q∈G

Sdrq≥0,?r∈S,?q∈G

(1)

其中：Sdrq表示儲(chǔ)備庫(kù)r中物資q的存儲(chǔ)量；Rpq表示受災(zāi)點(diǎn)p需要的物資q的數(shù)量；trp表示儲(chǔ)備庫(kù)r運(yùn)輸物資到受災(zāi)點(diǎn)p需要的時(shí)間。

1.2 問(wèn)題轉(zhuǎn)化

討論解決的應(yīng)急物資調(diào)度問(wèn)題是多目標(biāo)優(yōu)化問(wèn)題，即要求運(yùn)輸時(shí)間(Tw)最短、參與救災(zāi)的物資儲(chǔ)備庫(kù)(Nw)最少。為方便求解，需要將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題。我們采用理想點(diǎn)法進(jìn)行問(wèn)題轉(zhuǎn)化。

按照理想點(diǎn)法的原理，先要找出評(píng)價(jià)目標(biāo)函數(shù)的最劣值和最優(yōu)值，也就是負(fù)理想點(diǎn)和正理想點(diǎn)。在求最優(yōu)解時(shí)，計(jì)算各個(gè)方案與正理想點(diǎn)和負(fù)理想點(diǎn)的相對(duì)接近值。與正理想點(diǎn)越接近，則說(shuō)明該方案越接近最優(yōu)解[3]。

定義Rv和rv分別為目標(biāo)函數(shù)的正理想點(diǎn)和負(fù)理想點(diǎn)，則

(2)

(3)

其中：w1和w2分別表示物資運(yùn)輸時(shí)間及參與救災(zāi)的儲(chǔ)備庫(kù)數(shù)量的權(quán)重，兩者之和等于1。由于在此問(wèn)題中，兩個(gè)目標(biāo)同等重要，所以將w1和w2都設(shè)置為0.5。從以上公式可以看出，當(dāng)Tw和Nw越小時(shí)，則Rv越大、rv越小，hv也越小。hv=(Rv+rv)Rv。由此可以將原來(lái)的多目標(biāo)問(wèn)題轉(zhuǎn)化為以下單目標(biāo)問(wèn)題：

min{hv}

s.t.

wrpq≥0,trp≥0,?r∈S,?p∈D,?q∈G

Sdrq≥0,?r∈S,?q∈G

(4)

1.3 約束條件處理

在本問(wèn)題中，約束條件包括等式約束和不等式約束2種情況。需要將這些復(fù)雜約束條件進(jìn)行處理，并將其體現(xiàn)在目標(biāo)函數(shù)中。我們采用懲罰函數(shù)法進(jìn)行約束條件處理。

按懲罰函數(shù)法的原理，當(dāng)某個(gè)方案不滿足約束條件時(shí)，就在目標(biāo)函數(shù)中為其添加一個(gè)懲罰項(xiàng)，使該方案對(duì)應(yīng)的目標(biāo)函數(shù)值變得極差，進(jìn)而將該方案淘汰[4]。

本問(wèn)題有2個(gè)約束條件：每個(gè)儲(chǔ)備庫(kù)的所有物資的分配量，均不得超過(guò)其儲(chǔ)備量；各受災(zāi)點(diǎn)得到的各種物資量，均滿足其需求量。以xrpq表示儲(chǔ)備庫(kù)r發(fā)送給受災(zāi)點(diǎn)p的物資q的數(shù)目，2個(gè)約束條件對(duì)應(yīng)的懲罰函數(shù)分別為g1(x)和g2(x)。

(5)

(6)

其中：L=100，代表懲罰系數(shù)。

對(duì)帶約束條件的多目標(biāo)問(wèn)題，利用理想點(diǎn)法和懲罰函數(shù)法進(jìn)行問(wèn)題轉(zhuǎn)化和建模，得到以下目標(biāo)函數(shù)：

(7)

通過(guò)以上方法，便將求解基于約束條件的Tw和Nw最小值的問(wèn)題，轉(zhuǎn)化為求解f(x)的最大值問(wèn)題，使復(fù)雜問(wèn)題得到了大大簡(jiǎn)化。

2 基于遺傳算法求解

遺傳算法是求解最優(yōu)化問(wèn)題的經(jīng)典算法，它通過(guò)模擬自然界生物優(yōu)勝劣汰的進(jìn)化機(jī)制，尋找適應(yīng)度最高的最優(yōu)解[5]。

針對(duì)應(yīng)急物資調(diào)度問(wèn)題，建立的適應(yīng)度函數(shù)公式：

(8)

利用遺傳算法求解應(yīng)急物資調(diào)度問(wèn)題，步驟如下。

采用實(shí)數(shù)編碼，初始化種群中的染色體：

(i=1,2,3,…，Sw)

(9)

第2步：開(kāi)始迭代。迭代次數(shù)Set_iter=100 000。

第3步：選擇。采用輪盤(pán)賭法進(jìn)行染色體選擇。每個(gè)染色體被選中的概率與其適應(yīng)度有一定關(guān)系，但并不是說(shuō)適應(yīng)度函數(shù)值高就一定會(huì)被選中，適應(yīng)度函數(shù)值低就一定不會(huì)被選中，選擇過(guò)程中存在一定的隨機(jī)性。按輪盤(pán)賭法原理，根據(jù)每個(gè)染色體的適應(yīng)度大小，畫(huà)出一張圓盤(pán)。適應(yīng)度越大的，在圓盤(pán)上所占的角度和面積就越大。每次通過(guò)轉(zhuǎn)動(dòng)輪盤(pán)，選出一個(gè)被保留的染色體。多次操作之后，選出新的被保留的種群。這種算法既考慮到了每個(gè)染色體的適應(yīng)度的大小，又保留了一定的隨機(jī)性。

第4步：交叉。采用中間重組交叉算子完成染色體交叉。將所有染色體分成若干組，每組包含2條染色體。在每組染色體上，隨機(jī)選擇需要進(jìn)行交叉的基因位置。在需要交叉的同一基因位置上，對(duì)應(yīng)的2個(gè)基因進(jìn)行交叉重組。

第5步：變異。采用非均勻變異算子。每條染色體隨機(jī)選擇需要變異的基因位置，將該基因在其取值范圍內(nèi)重新隨機(jī)生成一個(gè)新的基因，完成變異。

第6步：檢查染色體合法性。檢查每條新的染色體是否符合本問(wèn)題的等式約束條件和不等式約束條件，如果不符合約束條件，則根據(jù)約束條件重新調(diào)整染色體的值。

第7步：迭代結(jié)束。如果滿足收斂條件或達(dá)到最大迭代次數(shù)，運(yùn)行結(jié)束，輸出結(jié)果。

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)運(yùn)用2009年我國(guó)多個(gè)地震災(zāi)區(qū)的應(yīng)急物資調(diào)度數(shù)據(jù)。通過(guò)建模和求解，得到救災(zāi)應(yīng)急物資分配調(diào)度最優(yōu)方案。在該問(wèn)題中，儲(chǔ)備庫(kù)數(shù)量N=16，其編號(hào)由A到P；受災(zāi)點(diǎn)數(shù)量M=5，需要的物資種類K=5。已知每個(gè)儲(chǔ)備庫(kù)中所有物資的儲(chǔ)存量、每個(gè)受災(zāi)點(diǎn)對(duì)每種物資的需求量、每個(gè)儲(chǔ)備庫(kù)到各個(gè)受災(zāi)點(diǎn)的運(yùn)輸時(shí)間。應(yīng)急物資調(diào)度方案要實(shí)現(xiàn)的目標(biāo)為：從儲(chǔ)備庫(kù)到各受災(zāi)點(diǎn)的運(yùn)輸時(shí)間最短、參與救災(zāi)的儲(chǔ)備庫(kù)數(shù)量最少。這是典型的多目標(biāo)優(yōu)化問(wèn)題。

原始數(shù)據(jù)量太大，在此不便一一列出。以應(yīng)急物資中的帳篷為例，運(yùn)用遺傳算法求解。每個(gè)儲(chǔ)備庫(kù)需要向每個(gè)受災(zāi)點(diǎn)運(yùn)輸?shù)膸づ駭?shù)量如表1所示。

根據(jù)上述建立的模型，通過(guò)遺傳算法求解。按照計(jì)算的結(jié)果，在所有可行方案中，最優(yōu)方案是：需要參與救災(zāi)的儲(chǔ)備庫(kù)數(shù)量Nw=8個(gè)，最少運(yùn)輸時(shí)間Tw=2 960 min。

4 結(jié) 語(yǔ)

救災(zāi)應(yīng)急物資調(diào)度安排問(wèn)題，在多儲(chǔ)備庫(kù)、多受災(zāi)點(diǎn)、多種類物資的情況下，是一個(gè)典型的多目標(biāo)優(yōu)化問(wèn)題。其中，要求實(shí)現(xiàn)的主要目標(biāo)是參與救災(zāi)的物資儲(chǔ)備庫(kù)最少和物資運(yùn)輸過(guò)程中花費(fèi)的時(shí)間最少；同時(shí)要求符合2個(gè)條件，即每個(gè)儲(chǔ)備庫(kù)的所有物資的分配量不得超過(guò)其儲(chǔ)備量，每個(gè)受災(zāi)點(diǎn)得到的各種物資量均能夠滿足其需求量。對(duì)此，我們采用理想點(diǎn)法將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題，采用懲罰函數(shù)法對(duì)約束條件進(jìn)行處理，完成了建模，并給出了利用遺傳算法進(jìn)行求解的步驟。本次研究提出的多目標(biāo)救災(zāi)應(yīng)急物資調(diào)度模型及求解方法，適用于大規(guī)模突發(fā)的多目標(biāo)、多約束條件的災(zāi)區(qū)物資調(diào)度問(wèn)題，有助于提高救災(zāi)效率。