消耗速率為函數(shù)的應(yīng)急調(diào)度模型及算法＊

李梅霞，潘愛(ài)霞

（濰坊學(xué)院，山東 濰坊 261061）

本文針對(duì)突發(fā)事件發(fā)生時(shí)，應(yīng)急物資的調(diào)度問(wèn)題進(jìn)行深入研究。眾所周知，應(yīng)急問(wèn)題最顯著的特點(diǎn)表現(xiàn)在時(shí)間的緊迫性，決策者應(yīng)以較短的時(shí)間完成調(diào)度方案。如何合理地調(diào)度救援物資成為國(guó)內(nèi)外學(xué)者的一個(gè)重要研究課題［1-3］。在應(yīng)急問(wèn)題中，救援一旦開(kāi)始，就有物資消耗，并且要盡量確保物資的充足供應(yīng)。連續(xù)性條件就是要保證在任何時(shí)刻已到達(dá)物資量滿(mǎn)足物資持續(xù)消耗，即不能出現(xiàn)因物資供應(yīng)不足引起的應(yīng)急活動(dòng)的停止，這類(lèi)問(wèn)題普遍適合于諸如連續(xù)性應(yīng)急生產(chǎn)系統(tǒng)，電力供應(yīng)系統(tǒng)，供暖供氣系統(tǒng)，消防系統(tǒng)以及其它復(fù)雜的社會(huì)系統(tǒng)。關(guān)于應(yīng)急系統(tǒng)的研究成果已經(jīng)廣泛運(yùn)用于森林火災(zāi)［4］、地震［5］、礦井塌陷［6］、輻射性廢料泄漏事故［7］等具體災(zāi)害領(lǐng)域，但是這些研究都是在消耗速率為常數(shù)的情況下進(jìn)行的。文獻(xiàn)［8］中給出了消耗速率為函數(shù)的連續(xù)型應(yīng)急資源調(diào)度模型，給出了最早應(yīng)急時(shí)間的求解算法，但是沒(méi)有考慮使得出救點(diǎn)的個(gè)數(shù)盡可能得少，而出救點(diǎn)個(gè)數(shù)的多少直接關(guān)系到出救成本，所以本文將在以上文獻(xiàn)的基礎(chǔ)上，首先給出應(yīng)急時(shí)間最早時(shí)出救點(diǎn)個(gè)數(shù)最少的兩階段算法，并通過(guò)數(shù)值算例說(shuō)明算法的應(yīng)用。另外，在大型應(yīng)急活動(dòng)中，應(yīng)急資源的需求是多樣的，所以研究消耗速率為函數(shù)的連續(xù)型多資源應(yīng)急調(diào)度模型具有更重要的實(shí)際意義，本文探討了應(yīng)急時(shí)間最早、出救點(diǎn)數(shù)目最少的多資源應(yīng)急調(diào)度模型。該模型利用單資源最早應(yīng)急時(shí)間的求解公式，得到了多資源最早應(yīng)急時(shí)間的求解方法，進(jìn)一步探討了出救點(diǎn)數(shù)目最少的調(diào)度方案，并用數(shù)值算例驗(yàn)證了算法的有效性和實(shí)用性。

1 問(wèn)題描述

設(shè)νj（y）為第j種應(yīng)急資源的消耗速率，j=1，2，…，l。

假設(shè)1 νj（y）為可積函數(shù)且νj（y）≥0，j=1，2，…，l。

設(shè)s為應(yīng)急起始時(shí)間，fj為第j 種應(yīng)急資源的應(yīng)急結(jié)束時(shí)間，則

為了求解具有最早應(yīng)急開(kāi)始時(shí)間的方案，首先給出如下定義。

定義1 設(shè)消耗速率νj（y），j=1，2，…，l，滿(mǎn)足假設(shè)1，如果對(duì)?t∈［s，fj］，均有

則稱(chēng)方案φ 關(guān)于起始時(shí)間s是j 資源連續(xù)可行的。

設(shè)所有關(guān)于起始時(shí)間s是連續(xù)可行的方案的集合為χs，此時(shí)問(wèn)題就變?yōu)榍蠼庀率鲎顑?yōu)化問(wèn)題

當(dāng)j=1，即為單資源的應(yīng)急問(wèn)題。文獻(xiàn)［8］中給出了單資源問(wèn)題最早應(yīng)急時(shí)間的求解算法，如下述幾個(gè)定理所述。

定理1 假設(shè)t1≤t2≤…≤tn，應(yīng)急時(shí)間最早的最優(yōu)方案為

定理2 φ＊對(duì)應(yīng)的最早應(yīng)急時(shí)間為

其中，Tk由以下方式確定

2 單資源問(wèn)題應(yīng)急時(shí)間最早時(shí)出救點(diǎn)個(gè)數(shù)最少的兩階段算法

文獻(xiàn)［8］給出了對(duì)應(yīng)最早應(yīng)急時(shí)間的最優(yōu)方案和最早應(yīng)急時(shí)間的求解算法，但是給出的最優(yōu)方案φ＊中可能包含了太多的出救點(diǎn)，從系統(tǒng)的穩(wěn)定性和費(fèi)用角度出發(fā)，我們更希望求出的方案在不延遲應(yīng)急開(kāi)始時(shí)間的前提下包含出救點(diǎn)的個(gè)數(shù)盡可能少，因?yàn)槌鼍赛c(diǎn)的多少直接關(guān)系到系統(tǒng)的穩(wěn)定性和可靠性，并且從費(fèi)用角度看，出救點(diǎn)的多少又直接關(guān)系到系統(tǒng)的總設(shè)置費(fèi)用。許多文獻(xiàn)在設(shè)計(jì)應(yīng)急點(diǎn)的分布時(shí)也十分強(qiáng)調(diào)這一因素。

設(shè)N（φ）表示方案φ 中出救點(diǎn)的數(shù)目，在文獻(xiàn)［8］中，N（φ＊）=p，希望求解如下問(wèn)題

［1］中的方法，給出如下的算法，依據(jù)是在相同的出救時(shí)間的前提下，為了減少出救點(diǎn)的數(shù)目，盡量的挑選物資量多的出救點(diǎn)進(jìn)行出救。

算法1

（1）u=s＊，k=1，total=0，I=Φ。

（4）φΛ=｛（Ai1，xi1），（Ai2，xi2），…，（Aik-1，xik-1），（Aik，xik′）｝。

類(lèi)似于文獻(xiàn)［1］中的處理方法，為了方便討論，對(duì)算法1的步驟（2）稍作修改，得到如下的算法。

算法2 （χs≠φ）

（1）u=s＊，d=1，total=0，I=Φ。

（2）?jd∈｛j｜tj≤u，j?I｝，I=I+｛jd｝，轉(zhuǎn)（3）。

（4）φ=｛（Aj1，xj1），（Aj2，xj2），…，（Ajd-1，xjd-1），（Ajd，xjd）｝。

設(shè)算法2產(chǎn)生的所有可能的方案的集合為χs′。

類(lèi)似于文獻(xiàn)［1］中相關(guān)定理的證明可以得到如下的幾個(gè)引理和定理，在此將證明過(guò)程省略。

引理1 當(dāng)χs≠φ時(shí)，通過(guò)算法2求得的任一方案是連續(xù)可行的，即χs′?χs。

引理2 當(dāng)χs≠φ時(shí)，存在一方案φ∈χs′使得問(wèn)題（2）達(dá)到最優(yōu)。

定理3 當(dāng)χs≠φ時(shí)，設(shè)通過(guò)算法1求得的方案為

并且假定

是通過(guò)算法2求得的任意一個(gè)方案，則k≤d。

定理4 算法1給出的解是問(wèn)題（2）的最優(yōu)解。

例1 對(duì)于文獻(xiàn)［1］中的例1，各出救點(diǎn)的物資量及出救時(shí)間見(jiàn)表1。

表1 各出救點(diǎn)的物資量及出救時(shí)間

假設(shè)物資需求量為300，物資消耗速率

根據(jù)文獻(xiàn)［1］中的計(jì)算可知

按照本文給出的算法1，在最早應(yīng)急開(kāi)始時(shí)間不變的情況下，得到最優(yōu)方案為

因此只需要5個(gè)出救點(diǎn)就可以了，這樣減少了出救點(diǎn)的數(shù)目，既可以達(dá)到經(jīng)濟(jì)的目的，又可以增加出救的可靠性。

3 多資源問(wèn)題應(yīng)急時(shí)間最早出救點(diǎn)個(gè)數(shù)最少的算法探討

本節(jié)將探討多資源問(wèn)題的調(diào)度模型。文獻(xiàn)［9］中給出了多資源應(yīng)急問(wèn)題最早應(yīng)急時(shí)間的求取方法。首先針對(duì)每一種資源求解下面的優(yōu)化問(wèn)題：

令

其對(duì)應(yīng)的最優(yōu)方案為

其中，pj滿(mǎn)足

易知，對(duì)任意的j，有φ＊j∈

令

由文獻(xiàn)［9］中的相關(guān)定理可知下述定理成立。

定理5 （3）式表示的方案φ＊是問(wèn)題（1）的最優(yōu)方案，并且最優(yōu)目標(biāo)值為s。

定理5給出了多種資源最早應(yīng)急時(shí)間的求解方法。在保證應(yīng)急時(shí)間最早的情況下，出救點(diǎn)個(gè)數(shù)的多少直接影響出救的成本。因此在求出最早應(yīng)急時(shí)間后，可以根據(jù)第3節(jié)中的方法，針對(duì)每種資源確定出救點(diǎn)數(shù)目最少的調(diào)度方案，然后適當(dāng)?shù)卣{(diào)整每一種物資的出救點(diǎn)，使得在最早應(yīng)急時(shí)間不變的情況下，出救點(diǎn)的個(gè)數(shù)盡可能的少。

下面通過(guò)幾個(gè)例子探討多資源物資調(diào)度問(wèn)題在應(yīng)急時(shí)間最早的情況下，出救點(diǎn)個(gè)數(shù)最少的調(diào)度方法。

例2 設(shè)事故發(fā)生點(diǎn)A 需要三種物資，需求量為x=（20，30，92），各出救點(diǎn)Ai的資源可用量xij及到達(dá)A 的行走時(shí)間ti見(jiàn)表2。

物資的消耗速率

表2 各出救點(diǎn)的物資量及行走時(shí)間

按照第2節(jié)的計(jì)算方法，首先計(jì)算每一種物資的出救方案和最早應(yīng)急時(shí)間

所以最早應(yīng)急時(shí)間為s＊=20.2，共需要7個(gè)出救點(diǎn)。

按照第3節(jié)給出的方法，在保證最早應(yīng)急時(shí)間s＊=20.2不變的情況下，將出救方案進(jìn)行調(diào)整，目標(biāo)是使各種資源的出救點(diǎn)數(shù)目盡可能得少。調(diào)整方案如下

由上述結(jié)果知，三種資源中均需要A2，A4，A5三個(gè)出救點(diǎn)，所以該三點(diǎn)不必進(jìn)行調(diào)整。為了減少出救點(diǎn)的數(shù)目，盡量去除運(yùn)送時(shí)間大的出救點(diǎn)，因此首先考慮去掉第三種資源中的A7點(diǎn)，而A3點(diǎn)的供應(yīng)量為4，小于φ3′中A7點(diǎn)的供應(yīng)量8，所以不能將A7點(diǎn)換為A3點(diǎn)。既然第三種資源中的A7點(diǎn)不能去掉，下面考慮在第一種資源中將A6點(diǎn)換為A7點(diǎn)。通過(guò)計(jì)算可知，從s＊=20.2至A7點(diǎn)的運(yùn)送時(shí)間23時(shí)的消耗量為23.5，大于A1至A5的供應(yīng)量之和16，所以也不能將A6點(diǎn)換為A7點(diǎn)。由以上分析知，以上的調(diào)運(yùn)方案無(wú)法進(jìn)行優(yōu)化，仍然需要7個(gè)出救點(diǎn)。

例3 設(shè)事故發(fā)生點(diǎn)A 對(duì)三種物資的需求量分別為60，100，120，各出救點(diǎn)Ai的資源可用量xij及到達(dá)A 的行走時(shí)間ti見(jiàn)表3。

表3 各出救點(diǎn)的物資量及行走時(shí)間

物資的消耗速率

按照第2節(jié)的計(jì)算方法，首先計(jì)算每一種物資的最優(yōu)出救方案為

每一種資源的最早應(yīng)急時(shí)間為s1＊=1.8，s2＊=1，s3＊=1，所以最早應(yīng)急時(shí)間為s＊=1.8，共需要8個(gè)出救點(diǎn)。

按照第3節(jié)給出的方法，類(lèi)似于例2的分析，可以在保證最早應(yīng)急時(shí)間s＊=1.8不變的情況下，將出救方案調(diào)整如下

根據(jù)上述方案可以看出，只需要7個(gè)出救點(diǎn)就可以完成救援。

4 結(jié)論與展望

本文針對(duì)應(yīng)急系統(tǒng)多點(diǎn)出救的特點(diǎn)，首先研究了單資源應(yīng)急調(diào)度模型中應(yīng)急時(shí)間最早、出救點(diǎn)個(gè)數(shù)最少的兩階段模型，然后探究了消耗速率為函數(shù)的連續(xù)型多資源應(yīng)急調(diào)度模型。該模型是通過(guò)計(jì)算每種資源的最早應(yīng)急時(shí)間得出多資源模型的最早應(yīng)急時(shí)間，進(jìn)而探討了應(yīng)急時(shí)間最早、出救點(diǎn)數(shù)目最少的多資源調(diào)度方法。數(shù)值算例表明了算法的有效性和實(shí)用性。對(duì)于多資源的連續(xù)消耗的應(yīng)急問(wèn)題，應(yīng)急時(shí)間最早、出救點(diǎn)數(shù)目最少的系統(tǒng)算法的設(shè)計(jì)是我們亟需研究的重要問(wèn)題。

參考文獻(xiàn)：

［1］劉春林，何建敏，施建軍.一類(lèi)應(yīng)急物資調(diào)度的優(yōu)化模型研究［J］.中國(guó)管理科學(xué)，2001，9（3）：29-36.

［2］Barbarosoglu G，Arda Y A.Two-stage stochastic programming framework for transportation planning in disaster response［J］.Journal of the Operational Research Society，2004，55：43-53.

［3］趙林度，劉明，戴東甫.面向脈沖需求的應(yīng)急資源調(diào)度問(wèn)題研究［J］.東南大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，38（6）：1116-1120.

［4］Jean-Luc，Wybo.FM IS：a decision support system for forest fire prevent ion and fighting［J］.IEEE Transactions on Engineering，1998，45（2）：127-131.

［5］Walter W.Hays.Reduction of earthquake risk in the United States：bridging the gap between research and practice［J］.IEEE Transact ions on Engineering Management，1998，45（2）：176-180.

［6］Henry P，Cole.Decision making during a simulated mine fire escape［J］.IEEE Transactions on Engineering Management，1998，45（2）：153-162.

［7］George F，List.Routing and emergency-response-team siting for high-level radioactive waste shipments［J］.IEEE Transactions on Engineering Management，1998，45（2）：141-152.

［8］李梅霞，車(chē)海濤.應(yīng)急資源調(diào)度模型及算法［J］.運(yùn)籌與管理，2011，20（3）：72-76.

［9］鄭昊，高巖.多資源消耗應(yīng)急系統(tǒng)調(diào)度模型及算法［J］.上海理工大學(xué)學(xué)報(bào)，2013，35（5）：415-419.