孫欣欣 李珊紅

(合肥學院計算機科學與技術(shù)系， 合肥 230601)

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

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

1 應急物資調(diào)度問題建模

1.1 問題描述

針對多儲備庫、多受災點、多種應急物資的情況，定義如下變量：

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

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

s.t.

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

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

(1)

其中：Sdrq表示儲備庫r中物資q的存儲量；Rpq表示受災點p需要的物資q的數(shù)量；trp表示儲備庫r運輸物資到受災點p需要的時間。

1.2 問題轉(zhuǎn)化

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

按照理想點法的原理，先要找出評價目標函數(shù)的最劣值和最優(yōu)值，也就是負理想點和正理想點。在求最優(yōu)解時，計算各個方案與正理想點和負理想點的相對接近值。與正理想點越接近，則說明該方案越接近最優(yōu)解[3]。

定義Rv和rv分別為目標函數(shù)的正理想點和負理想點，則

(2)

(3)

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

min{hv}

s.t.

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

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

(4)

1.3 約束條件處理

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

按懲罰函數(shù)法的原理，當某個方案不滿足約束條件時，就在目標函數(shù)中為其添加一個懲罰項，使該方案對應的目標函數(shù)值變得極差，進而將該方案淘汰[4]。

本問題有2個約束條件：每個儲備庫的所有物資的分配量，均不得超過其儲備量；各受災點得到的各種物資量，均滿足其需求量。以xrpq表示儲備庫r發(fā)送給受災點p的物資q的數(shù)目，2個約束條件對應的懲罰函數(shù)分別為g1(x)和g2(x)。

(5)

(6)

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

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

(7)

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

2 基于遺傳算法求解

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

針對應急物資調(diào)度問題，建立的適應度函數(shù)公式：

(8)

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

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

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

(9)

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

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

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

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

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

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

3 實驗結(jié)果

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

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

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

4 結(jié) 語

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