應(yīng)急系統(tǒng)中多資源多目標(biāo)優(yōu)化模型研究＊

王兆玲

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

0 引言

眾所周知,時(shí)間緊迫性是應(yīng)急問(wèn)題的一個(gè)最顯著的特性,決策者需要在最短的時(shí)間內(nèi)完成應(yīng)急救援方案和資源調(diào)度決策。但是,由于參與應(yīng)急的出救點(diǎn)數(shù)目會(huì)直接影響方案的可靠性以及會(huì)產(chǎn)生額外費(fèi)用,因而出救點(diǎn)數(shù)目也應(yīng)是值得重視的因素,在很多情況下,系統(tǒng)的穩(wěn)定性和費(fèi)用都相當(dāng)重要。因而,這類問(wèn)題的本質(zhì)是一個(gè)多目標(biāo)的優(yōu)化問(wèn)題。

目前,國(guó)內(nèi)外學(xué)者對(duì)應(yīng)急問(wèn)題單資源情況下“應(yīng)急開(kāi)始時(shí)間最早條件下,出救點(diǎn)數(shù)目最少”的兩階段優(yōu)化模型以及“時(shí)間最短,出救點(diǎn)數(shù)目最少”的多目標(biāo)問(wèn)題的研究已經(jīng)有了一些較好的結(jié)果[1-5]。但實(shí)際過(guò)程中,許多情況下都不可避免的涉及多資源問(wèn)題,而對(duì)多資源情況下考慮“時(shí)間最短,出救點(diǎn)數(shù)目最少”的多目標(biāo)問(wèn)題,至今未見(jiàn)簡(jiǎn)便的解決辦法。本研究將對(duì)之進(jìn)行深入討論。

1 模型描述

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

j=1,2,…,n;i=1,2,…,ω。xij表示Aj的第i種資源可用量;xij′表示采用方案φ時(shí)Aj參與應(yīng)急的第i種資源可用量?？梢钥闯?第j列表示出救點(diǎn)Aj參與應(yīng)急的資源向量;第i行表示各出救點(diǎn)參與應(yīng)急的第i種資源數(shù)量。

用 T(φ)表示最早應(yīng)急時(shí)間,用 N(φ)表示出救點(diǎn)數(shù)目,并讓?表示所有方案的集合,于是問(wèn)題變?yōu)?/p>

2 模型分析與求解

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

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

算法思想:

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

定理 根據(jù)(2)求出的一系列方案φi,i=1,2,…,v,其對(duì)應(yīng)的目標(biāo)值[Tφi,Nφi],i=1,2,…,v,構(gòu)成的集合(平面上的點(diǎn)集,記為 F)一定包含非劣目標(biāo)值域。

算法步驟:

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

(1)j=n,v=0

(3)j=j=1;

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

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

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

3 算例(以兩種資源為例,數(shù)據(jù)見(jiàn)表1,計(jì)算過(guò)程見(jiàn)表2、表3)

效用函數(shù)

表1 數(shù)據(jù)(該數(shù)據(jù)來(lái)自某市的一次火災(zāi)救援)

表2 計(jì)算過(guò)程1

表3 計(jì)算過(guò)程2

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

4 結(jié)束語(yǔ)

本文給出了多資源、多目標(biāo)應(yīng)急問(wèn)題的數(shù)學(xué)模型,筆者以單資源的研究為基礎(chǔ),將多資源的情形通過(guò)加權(quán)轉(zhuǎn)化為單資源的情形來(lái)解決,使得該問(wèn)題簡(jiǎn)便易行。最主要的是該算法現(xiàn)經(jīng)一年的試驗(yàn)運(yùn)行,取得了令人滿意的結(jié)果。而對(duì)需求和時(shí)間為模糊情況的運(yùn)輸問(wèn)題更具有實(shí)際意義,這種情況下的應(yīng)急問(wèn)題是否也存在比較好的算法將成為該領(lǐng)域有待完成的工作。

[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.