鄭 昊， 高 巖

（上海理工大學(xué)管理學(xué)院，上海 200093）

多資源消耗應(yīng)急系統(tǒng)調(diào)度模型及算法

鄭 昊， 高 巖

（上海理工大學(xué)管理學(xué)院，上海 200093）

結(jié)合應(yīng)急系統(tǒng)多點(diǎn)出救的特征，研究了在資源消耗速率為非負(fù)可積函數(shù)的情況下，構(gòu)建基于應(yīng)急時(shí)間最早的連續(xù)型應(yīng)急資源調(diào)度模型，并給出相應(yīng)算法.對(duì)模型及所提出的求解算法進(jìn)行實(shí)證研究，結(jié)果表明：模型與算法有效，并能對(duì)突發(fā)事件應(yīng)急資源調(diào)度起到積極的作用.

連續(xù)性消耗；多資源；應(yīng)急資源調(diào)度；調(diào)度模型

近年來(lái)無(wú)論是自然災(zāi)害、事故災(zāi)害還是公共安全災(zāi)害，爆發(fā)的頻率、規(guī)模都明顯增加，因此，應(yīng)急系統(tǒng)的設(shè)計(jì)和管理便顯得尤為重要［1］.步入21世紀(jì)以來(lái)，應(yīng)急管理得到長(zhǎng)足的發(fā)展，各種介紹應(yīng)急系統(tǒng)及其在各行業(yè)中應(yīng)用的文獻(xiàn)不斷涌現(xiàn)［2-4］.突發(fā)的地震、水災(zāi)、核泄露等惡性事件發(fā)生時(shí)，臨場(chǎng)快速地給出相關(guān)救災(zāi)物資調(diào)度能極大減少人員傷亡［5］.我國(guó)地域遼闊，災(zāi)害時(shí)有發(fā)生，如南方雪災(zāi)和四川汶川地震均給國(guó)家?guī)?lái)了巨大災(zāi)害［6］.這些災(zāi)害的特點(diǎn)是受災(zāi)點(diǎn)集中、物資需求量大、物資調(diào)配復(fù)雜，因此需要多個(gè)物資儲(chǔ)備點(diǎn)同時(shí)出救.面對(duì)突如其來(lái)的災(zāi)害，如何快速合理的調(diào)度救援物資是一個(gè)亟待解決的問(wèn)題.

當(dāng)突發(fā)性重大自然災(zāi)害發(fā)生時(shí)，往往存在災(zāi)害點(diǎn)同時(shí)需要調(diào)集多種救援設(shè)備和物資的現(xiàn)象.目前國(guó)內(nèi)關(guān)于應(yīng)急資源調(diào)度的研究大都針對(duì)資源消耗速率一定，主要包括多資源組合、多目標(biāo)規(guī)劃、模糊優(yōu)化、連續(xù)消耗等方面［7-11］.劉春林等［9］在考慮連續(xù)消耗應(yīng)急系統(tǒng)的一般調(diào)運(yùn)方法的基礎(chǔ)上，提出了以最早應(yīng)急開(kāi)始時(shí)間為目標(biāo)的固定消耗速率應(yīng)急資源調(diào)度模型及相應(yīng)的求解算法.趙林度等［10］建立了具有脈沖需求的應(yīng)急資源調(diào)度模型，研究了單目標(biāo)和二階段資源調(diào)度問(wèn)題.李梅霞等［11］研究了消耗速率為函數(shù)的單資源連續(xù)型應(yīng)急資源調(diào)度模型，特別給出了應(yīng)急時(shí)間最早的單資源應(yīng)急調(diào)度模型及算法，并從理論上進(jìn)行了分析和證明.

國(guó)外方面，應(yīng)急系統(tǒng)的研究起步比較早，相關(guān)的研究及應(yīng)用大量涌現(xiàn)，例如Zografor等［12］研究了基于響應(yīng)時(shí)間最短的適時(shí)決策支持系統(tǒng)的公路網(wǎng)事故響應(yīng)模型；Jae［13］研究了災(zāi)害發(fā)生時(shí)如何分配有限的車(chē)輛資源將傷員運(yùn)送到醫(yī)院，確保傷員存活率最高；Gulay等［14］提出了一種分層多標(biāo)準(zhǔn)方法解決直升機(jī)在救災(zāi)中的調(diào)度問(wèn)題，使派遣的直升機(jī)和飛行員數(shù)目在滿(mǎn)足需求的情況下成本最低.

上述研究大都是在考慮資源消耗速率為恒定值時(shí)，構(gòu)建的資源調(diào)度模型和算法，但是由于災(zāi)害現(xiàn)場(chǎng)傷亡人數(shù)往往具有不可預(yù)測(cè)性，因此應(yīng)急資源消耗數(shù)量也不會(huì)簡(jiǎn)單的為一個(gè)恒定值.筆者在以上研究的基礎(chǔ)上，構(gòu)建消耗速率為非負(fù)可積函數(shù)的連續(xù)型多資源應(yīng)急系統(tǒng)調(diào)度模型.該模型以最早應(yīng)急時(shí)間為目標(biāo)，給出資源調(diào)度總方案和最早應(yīng)急開(kāi)始時(shí)間的求取算法，并通過(guò)實(shí)證分析驗(yàn)證算法的有效性和實(shí)用性.

1 問(wèn)題描述

設(shè)A1，A2，…，An為n個(gè)應(yīng)急資源供應(yīng)點(diǎn)（出救點(diǎn)）；A為應(yīng)急地點(diǎn)；x1，x2，…，xm分別為m種應(yīng)急物資需求量，（xj表示對(duì)第j種資源的需求量）；Ai中第j種資源可用量表示為xji（i=1，2，…，n）；vj（y）為第j種資源消耗速率（vj（y）為可積函數(shù)，且vj（y）≥0）；sj為第j種資源參與應(yīng)急的開(kāi)始時(shí)間；fj為其完成時(shí)間；（Ai，x）為出救點(diǎn)Ai的資源j的調(diào)度方案，即從出救點(diǎn)Ai調(diào)度出的第j種資源為；應(yīng)急物資從Ai到應(yīng)急地點(diǎn)A的時(shí)間為ti（ti＞0），不妨設(shè)t1≤t2≤…≤tn.由于救災(zāi)工作一般要經(jīng)歷混亂、平穩(wěn)有序到救災(zāi)結(jié)束，資源消耗數(shù)量應(yīng)是先增加，然后趨于平衡，最后會(huì)逐漸遞減，不失一般性，本文以線(xiàn)性連續(xù)可積非負(fù)函數(shù)為資源消耗函數(shù).

對(duì)于第j種資源而言，其消耗速率vj（y）為可積函數(shù)且vj（y）≥0，則第j種資源的需求量xj滿(mǎn)足

因此，本模型研究的應(yīng)急資源調(diào)度問(wèn)題可以描述為：當(dāng)A地發(fā)生突發(fā)事件后，應(yīng)快速給出一個(gè)應(yīng)急資源調(diào)度方案

定義1如果對(duì)于總調(diào)度方案φ中任意單一資源單資源方案）關(guān)于起始時(shí)間s是連續(xù)可行的，則稱(chēng)總調(diào)度方案式（2）關(guān)于起始時(shí)間s是連續(xù)可行的.

設(shè)對(duì)于第j種資源，起始時(shí)間s是連續(xù)可行的所有方案的集合為χjs，模型最優(yōu)解為確定參與應(yīng)急的出救點(diǎn)及各自的應(yīng)急物資量，在保證應(yīng)急物資連續(xù)供應(yīng)的條件下，使得應(yīng)急開(kāi)始時(shí)間最早，即求解下述問(wèn)題

2 多資源應(yīng)急系統(tǒng)調(diào)度模型的求解

結(jié)合相關(guān)問(wèn)題的描述與假設(shè)，給出多資源連續(xù)消耗應(yīng)急資源調(diào)度模型的總調(diào)度方案和最早應(yīng)急開(kāi)始時(shí)間的求解，并給出相應(yīng)的證明.

2.1 調(diào)度方案

由定義1知，對(duì)于式（2）中任一應(yīng)急資源jk的方案，文獻(xiàn)［7］中給出的性質(zhì)仍然成立.

2.2 最早開(kāi)始時(shí)間

2.3 求解算法

根據(jù)定理1和定理3及相關(guān)證明過(guò)程，給出多資源應(yīng)急系統(tǒng)調(diào)度模型的總調(diào)度方案和對(duì)應(yīng)的最早應(yīng)急開(kāi)始時(shí)間的求解算法.算法步驟如下：

步驟1比較各應(yīng)急點(diǎn)應(yīng)急時(shí)間的大小，按照l(shuí)k的大小從小到大順序?qū)i重新排列；

步驟2對(duì)于每種資源的應(yīng)急需求量

步驟3當(dāng)j≤m時(shí)，重復(fù)步驟2，即可求出每種資源對(duì)應(yīng)的單資源方案，進(jìn)而求出總調(diào)度方案φ*；

步驟4具體計(jì)算依照文獻(xiàn)［11］.計(jì)算單一資源應(yīng)急最早開(kāi)始時(shí)間，即第j種資源應(yīng)急最早開(kāi)始時(shí)間；

步驟5根據(jù)定理2，求得總調(diào)度方案φ*對(duì)應(yīng)的最早應(yīng)急開(kāi)始時(shí)間

3 實(shí)證分析

某地A發(fā)生嚴(yán)重事故，急需3種應(yīng)急物資x1，x2，x3.現(xiàn)有A1，A2，A3，A4，A5，A6，A7，A88個(gè)物資供應(yīng)點(diǎn)可以提供物資.采用文獻(xiàn)［7］中數(shù)據(jù)，設(shè)事故發(fā)生地A對(duì)3種物資的需求量分別為x1=20，x2=30，x3=92.各出救點(diǎn)Ai能提供第j種資源的量xji如表1所示，到達(dá)A所需要的時(shí)間ti如表2所示.

表1 各出救點(diǎn)的物資量及到達(dá)時(shí)間Tab.1 Arrival time and nu m ber of each relief point

表2 各出救點(diǎn)到達(dá)災(zāi)害現(xiàn)場(chǎng)場(chǎng)地所需要的時(shí)間Tab.2 Arrival time of each relief point to disaster

b.根據(jù)算法步驟2，分別算得資源j的單一方案

其中，第一種資源需要6個(gè)出救點(diǎn)，分別為A1，A2，A3，A4，A5，A6.第二種資源需要5個(gè)出救點(diǎn)，分別為A1，A2，A3，A4，A5.第三種資源需要7個(gè)出救點(diǎn)，分別為A1，A2，A3，A4，A5，A6，A7.

當(dāng)v1（y）=1，v2（y）=2，v3（y）=4時(shí)，文獻(xiàn)［7］中算例即為本文的一個(gè)特例.

4 小 結(jié)

在假設(shè)應(yīng)急物資的消耗速率為非負(fù)可積函數(shù)的情況下，提出了以最早應(yīng)急時(shí)間為目標(biāo)的多資源應(yīng)急系統(tǒng)調(diào)度模型及相應(yīng)方案、應(yīng)急開(kāi)始時(shí)間的求解算法，并利用實(shí)證分析驗(yàn)證了算法的有效性和實(shí)用性.但是該多資源應(yīng)急系統(tǒng)調(diào)度模型仍存在著不足，首先面對(duì)應(yīng)急環(huán)境的緊迫性和不可預(yù)測(cè)性，各種應(yīng)急資源的消耗速率函數(shù)難以獲得.其次，本文所給模型只是建立在以“應(yīng)急開(kāi)始最早”的基礎(chǔ)上，但是以“應(yīng)急開(kāi)始最早”作為目標(biāo)的方案可能很多，無(wú)論從費(fèi)用或系統(tǒng)穩(wěn)定性角度，考慮“應(yīng)急時(shí)間最早的前提下出救點(diǎn)數(shù)目最少”的二階段問(wèn)題更有實(shí)際意義.因由于出行車(chē)輛的多少直接關(guān)系到系統(tǒng)的穩(wěn)定性和可靠性.因此可以在文中模型的基礎(chǔ)上建立“應(yīng)急開(kāi)始最早、出救點(diǎn)數(shù)目最少”的二階段應(yīng)急資源調(diào)度模型

φχs此外，在實(shí)際應(yīng)用中，由于應(yīng)急系統(tǒng)所處環(huán)境的多變性，各出救點(diǎn)的應(yīng)急時(shí)間不是一個(gè)確定的時(shí)間，而是一個(gè)區(qū)間數(shù)，因此如何在應(yīng)急時(shí)間不確定的情況下選擇“應(yīng)急時(shí)間最早”的多資源連續(xù)型消耗系統(tǒng)方案將是一個(gè)有意義的研究課題.

［1］ 陶澤瓊，高巖.基于改進(jìn)目標(biāo)規(guī)劃方法的應(yīng)急系統(tǒng)優(yōu)化選址模型［J］.技術(shù)與創(chuàng)新管理，2012，33（2）：179 -182.

［2］ Liu S.E mploying system of systems engineering in China’s emergency management［J］.IEEE systems journal，2011，5（2）：289-308.

［3］ Tassetto D，F(xiàn)azl i E H，Werner MA.Novel hybrid algorithmforpassivelocal izationofvictims in emergency situations［J］.International Journal of Satel l ite Com munications and Networking，2011，29（5）：461-478.

［4］ Yang J F，Gao Y.E mergency evacuation model and algorithm in the bui lding with faci l ities［J］.Intel l igent Information Management Systems and Technologies，2012，8（3）：283-292.

［5］ 何建敏，劉春林，曹杰，等.應(yīng)急管理與應(yīng)急系統(tǒng)——選址、調(diào)度與算法［M］.北京：科學(xué)出版社，2005.

［6］ 耿澤飛，胡飛虎，陳慧敏，等.多災(zāi)害點(diǎn)應(yīng)急資源調(diào)度模型研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)應(yīng)用與軟件，2010，22（2）：63-66.

［7］ 劉春林，盛昭瀚，何建敏.基于連續(xù)消耗應(yīng)急系統(tǒng)的多出救點(diǎn)選擇問(wèn)題［J］.管理工程學(xué)報(bào)，1999，13（3）：3 -6

［8］ 戴更新，達(dá)慶利.多物資組合應(yīng)急調(diào)度問(wèn)題的研究［J］.系統(tǒng)工程理論與實(shí)踐，2000，12（9）：52-55.

［9］ 劉春林，沈厚才.一類(lèi)離散應(yīng)急供應(yīng)系統(tǒng)的兩目標(biāo)優(yōu)化模型［J］.中國(guó)管理科學(xué)，2003，11（4）：27-31.

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

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

［12］ Zografos K G，Konstantinos N A，George M V.A realtime decision support system for roadway network response logistics［J］.Transportation Research Part C，2002，10（1）：1-18.

［13］ Choi J Y.Stochasticschedul ingproblemsfor minimizing tardy jobs with appl ication to emergency vehicle dispatching on unrel iable road networks［D］. New Yonk：University of New York.2003.

［14］ Gulay B，Linet O，Ahmet C.An interactive approach for hierarchical analysis of hel icopter logisitics in disaster rel ief operations［J］.European Journal of Operational Research，2002，140（1）：118-133.

（編輯：金 虹）

Dispatching M odel and Algorith m for M ulti-resource E m ergency Syste m s

ZHENG Hao， GAO Yan
（Business School，University of Shanghai for Science and Technology，Shanghai 200093，China）

Considering themulti-objective，dynamic，uncertain and time-sensitive features of emergency resource scheduling，the fast reaction time was focused as an important research subject.According to the characteristic of emergency system，themulti-resource emergency systems model with comsumption rates of nonnegative and integrable functions was introduced.A new model was built based on the object of earliest emergency-start-time，and the corresponding algorithm was provided.The results of empirical research illustrate that the model and the algorithm are both effective and play an active role in emergency resource scheduling.They also provide a theoretical support to emergency scheduling decision.

continuous consu m ption；m ulti-resource；emergency source dispatching；dispatching model

N 945.12

A

1007-6735（2013）05-0415-05

2012-12-26

上海市科委資助項(xiàng)目（10550500800）

鄭 昊（1987-），男，碩士研究生.研究方向：應(yīng)急管理.E-mai l：zhenghao.87＠163.com

高 巖（1962-），男，教授.研究方向：復(fù)雜系統(tǒng)分析與優(yōu)化.E-mai l：gaoyan＠usst.edu.cn