消耗速率為函數的應急調度模型及算法＊

李梅霞，潘愛霞

（濰坊學院，山東 濰坊 261061）

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

1 問題描述

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

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

設s為應急起始時間，fj為第j 種應急資源的應急結束時間，則

為了求解具有最早應急開始時間的方案，首先給出如下定義。

定義1 設消耗速率νj（y），j=1，2，…，l，滿足假設1，如果對?t∈［s，fj］，均有

則稱方案φ 關于起始時間s是j 資源連續可行的。

設所有關于起始時間s是連續可行的方案的集合為χs，此時問題就變為求解下述最優化問題

當j=1，即為單資源的應急問題。文獻［8］中給出了單資源問題最早應急時間的求解算法，如下述幾個定理所述。

定理1 假設t1≤t2≤…≤tn，應急時間最早的最優方案為

定理2 φ＊對應的最早應急時間為

其中，Tk由以下方式確定

2 單資源問題應急時間最早時出救點個數最少的兩階段算法

文獻［8］給出了對應最早應急時間的最優方案和最早應急時間的求解算法，但是給出的最優方案φ＊中可能包含了太多的出救點，從系統的穩定性和費用角度出發，我們更希望求出的方案在不延遲應急開始時間的前提下包含出救點的個數盡可能少，因為出救點的多少直接關系到系統的穩定性和可靠性，并且從費用角度看，出救點的多少又直接關系到系統的總設置費用。許多文獻在設計應急點的分布時也十分強調這一因素。

設N（φ）表示方案φ 中出救點的數目，在文獻［8］中，N（φ＊）=p，希望求解如下問題

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

算法1

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

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

類似于文獻［1］中的處理方法，為了方便討論，對算法1的步驟（2）稍作修改，得到如下的算法。

算法2 （χs≠φ）

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

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

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

設算法2產生的所有可能的方案的集合為χs′。

類似于文獻［1］中相關定理的證明可以得到如下的幾個引理和定理，在此將證明過程省略。

引理1 當χs≠φ時，通過算法2求得的任一方案是連續可行的，即χs′?χs。

引理2 當χs≠φ時，存在一方案φ∈χs′使得問題（2）達到最優。

定理3 當χs≠φ時，設通過算法1求得的方案為

并且假定

是通過算法2求得的任意一個方案，則k≤d。

定理4 算法1給出的解是問題（2）的最優解。

例1 對于文獻［1］中的例1，各出救點的物資量及出救時間見表1。

表1 各出救點的物資量及出救時間

假設物資需求量為300，物資消耗速率

根據文獻［1］中的計算可知

按照本文給出的算法1，在最早應急開始時間不變的情況下，得到最優方案為

因此只需要5個出救點就可以了，這樣減少了出救點的數目，既可以達到經濟的目的，又可以增加出救的可靠性。

3 多資源問題應急時間最早出救點個數最少的算法探討

本節將探討多資源問題的調度模型。文獻［9］中給出了多資源應急問題最早應急時間的求取方法。首先針對每一種資源求解下面的優化問題：

令

其對應的最優方案為

其中，pj滿足

易知，對任意的j，有φ＊j∈

令

由文獻［9］中的相關定理可知下述定理成立。

定理5 （3）式表示的方案φ＊是問題（1）的最優方案，并且最優目標值為s。

定理5給出了多種資源最早應急時間的求解方法。在保證應急時間最早的情況下，出救點個數的多少直接影響出救的成本。因此在求出最早應急時間后，可以根據第3節中的方法，針對每種資源確定出救點數目最少的調度方案，然后適當地調整每一種物資的出救點，使得在最早應急時間不變的情況下，出救點的個數盡可能的少。

下面通過幾個例子探討多資源物資調度問題在應急時間最早的情況下，出救點個數最少的調度方法。

例2 設事故發生點A 需要三種物資，需求量為x=（20，30，92），各出救點Ai的資源可用量xij及到達A 的行走時間ti見表2。

物資的消耗速率

表2 各出救點的物資量及行走時間

按照第2節的計算方法，首先計算每一種物資的出救方案和最早應急時間

所以最早應急時間為s＊=20.2，共需要7個出救點。

按照第3節給出的方法，在保證最早應急時間s＊=20.2不變的情況下，將出救方案進行調整，目標是使各種資源的出救點數目盡可能得少。調整方案如下

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

例3 設事故發生點A 對三種物資的需求量分別為60，100，120，各出救點Ai的資源可用量xij及到達A 的行走時間ti見表3。

表3 各出救點的物資量及行走時間

物資的消耗速率

按照第2節的計算方法，首先計算每一種物資的最優出救方案為

每一種資源的最早應急時間為s1＊=1.8，s2＊=1，s3＊=1，所以最早應急時間為s＊=1.8，共需要8個出救點。

按照第3節給出的方法，類似于例2的分析，可以在保證最早應急時間s＊=1.8不變的情況下，將出救方案調整如下

根據上述方案可以看出，只需要7個出救點就可以完成救援。

4 結論與展望

本文針對應急系統多點出救的特點，首先研究了單資源應急調度模型中應急時間最早、出救點個數最少的兩階段模型，然后探究了消耗速率為函數的連續型多資源應急調度模型。該模型是通過計算每種資源的最早應急時間得出多資源模型的最早應急時間，進而探討了應急時間最早、出救點數目最少的多資源調度方法。數值算例表明了算法的有效性和實用性。對于多資源的連續消耗的應急問題，應急時間最早、出救點數目最少的系統算法的設計是我們亟需研究的重要問題。

參考文獻：

［1］劉春林，何建敏，施建軍.一類應急物資調度的優化模型研究［J］.中國管理科學，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］趙林度，劉明，戴東甫.面向脈沖需求的應急資源調度問題研究［J］.東南大學學報：自然科學版，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］李梅霞，車海濤.應急資源調度模型及算法［J］.運籌與管理，2011，20（3）：72-76.

［9］鄭昊，高巖.多資源消耗應急系統調度模型及算法［J］.上海理工大學學報，2013，35（5）：415-419.