應急系統中多資源多目標優化模型研究＊

王兆玲

(濰坊學院,山東 濰坊 261061)

0 引言

眾所周知,時間緊迫性是應急問題的一個最顯著的特性,決策者需要在最短的時間內完成應急救援方案和資源調度決策。但是,由于參與應急的出救點數目會直接影響方案的可靠性以及會產生額外費用,因而出救點數目也應是值得重視的因素,在很多情況下,系統的穩定性和費用都相當重要。因而,這類問題的本質是一個多目標的優化問題。

目前,國內外學者對應急問題單資源情況下“應急開始時間最早條件下,出救點數目最少”的兩階段優化模型以及“時間最短,出救點數目最少”的多目標問題的研究已經有了一些較好的結果[1-5]。但實際過程中,許多情況下都不可避免的涉及多資源問題,而對多資源情況下考慮“時間最短,出救點數目最少”的多目標問題,至今未見簡便的解決辦法。本研究將對之進行深入討論。

1 模型描述

設 A1,A2,…,An為n個應急物資供應點(可出救點),A為應急地點,x=(x1,x2,…,xw)為應急物資需求(向)量,xj表示對j種資源的需求量j=1,2,…,ω,Ai到A需要的時間為ti(＞0),不妨設t1≤t2≤…≤tn,T(＞0)為應急限制期,要求給出一方案(確定參與應急的出救點及各自提供的應急資源數量)在滿足約束條件下,使得應急開始時間最早,出救點數目最少。

j=1,2,…,n;i=1,2,…,ω。xij表示Aj的第i種資源可用量;xij′表示采用方案φ時Aj參與應急的第i種資源可用量。可以看出,第j列表示出救點Aj參與應急的資源向量;第i行表示各出救點參與應急的第i種資源數量。

用 T(φ)表示最早應急時間,用 N(φ)表示出救點數目,并讓?表示所有方案的集合,于是問題變為

2 模型分析與求解

定義1 如果不存在另一方案φ′,使得 T(φ)≥Tφ′N(φ)≥N(φ′),并且有一個不等式嚴格成立,則稱方案φ是非劣的。

定義2 非劣方案φ對應的目標值[T(φ),N(φ)],稱為非劣目標值;所存可能非劣目標值的范圍,稱為非劣目標值域。

算法思想:

由于應急問題中,對每種資源的需求程度不同,所以可利用層次分析法,專家打分法等給出每種資源相對應的權重,分別記為:α1,α2,…,αω。容易看出,最早應急時間 T(φ)與出救點數目 N(φ)是相互矛盾的目標。由于 T(φ)最多不超過 n中可能的選擇{tn,tn-1,…,t1},讓 T(φ)從大到小取值(φ為變量),N(φ)關于φ是遞減的。這種現象的直觀解釋是如果一個非劣方案φ′,T(φ′)=ti,那么對任意一個在“時間”優于它的方案φ″,即 T(φ″)＜ti,一定滿足 N(φ″)≥N(φ′)。因為 T(φ′)∈{tn,tn-1,…,t1},讓 T(φ)取遍所有可能的值,對 N(φ)做優化,即求解這樣一系列的優化問題:

定理 根據(2)求出的一系列方案φi,i=1,2,…,v,其對應的目標值[Tφi,Nφi],i=1,2,…,v,構成的集合(平面上的點集,記為 F)一定包含非劣目標值域。

算法步驟:

記 X=(X1,X2,…,XN),α=(α1,α2,…,αω)則 X=αφ

(1)j=n,v=0

(3)j=j=1;

(4)若tj=tj+1,轉步驟(3),否則轉步驟(2)

(5)v=0時無解;否則用步驟(2)求解

如果決策者本身能給出他們的偏好函數即效用函數,那么只需對n個偏好函數值進行比較以確定最優方案。設 g(y,z)表示效用函數,y表示 T(φ),z表示N(φ),g是關于y,z的嚴格減函數。可以用下式求解多目標的最優解φ＊:

3 算例(以兩種資源為例,數據見表1,計算過程見表2、表3)

效用函數

表1 數據(該數據來自某市的一次火災救援)

表2 計算過程1

表3 計算過程2

結果及分析:對于效用函數(3),多目標問題的最優方案為φ1(即選擇A6A7A8A9作為出救點)。在對公安消防支隊的操作過程進行深入調研后,針對消防支隊只是根據預警級別,盲目動用人力、物力;沒有統籌規劃,不能把資源合理利用到最大化等問題,筆者提出了上述模型及求解方法,該問題的結果得到了消防支隊的認可。在上例中,當時公安消防支隊出動了周邊八個出救點進行救援,10分鐘后,火勢得到了有效控制。而從筆者計算的結果看,只出動四個出救點,就能滿足滅火的需要,大大節省了人力、物力。

4 結束語

本文給出了多資源、多目標應急問題的數學模型,筆者以單資源的研究為基礎,將多資源的情形通過加權轉化為單資源的情形來解決,使得該問題簡便易行。最主要的是該算法現經一年的試驗運行,取得了令人滿意的結果。而對需求和時間為模糊情況的運輸問題更具有實際意義,這種情況下的應急問題是否也存在比較好的算法將成為該領域有待完成的工作。

[1]Tzeng G H,Cheng H J,Huang T D.M ulti-objective op tinal p lannting for designing relief delivery systems[J].Transpotrtation Research Part E:Logistics and Transpo rtation Review,2007,43(6):673-686.

[2]Shen J B.An emergency logistics distribution app roach fo r quick response to urgent relief dem and in disasters[J].Transpo rtation Research Part E:Lgistics and Transpo rtation Review,2007,43(6):687-709.

[3]Renaud J.A tabu search heuristic for the multi-depot vehicle routing p roblem[J].Computers&Operations Research, 1996,23(3):229-235.

[4]Tufekei S,Wallace W A.The emerging area of emergency management and engineering[J].IEEE Transactions on Engineering M anagement,2001,45(2):141-152.

[5]Andersen H B.MM S:an electroniemessagemanagement system for emergency response[J].IEEE Transactionson Engineering Managemnet,2005,45(2):132-140.