面向多災(zāi)點(diǎn)需求的應(yīng)急資源調(diào)度博弈模型及優(yōu)化

楊繼君，佘 廉

(1. 國(guó)家行政學(xué)院應(yīng)急管理培訓(xùn)中心，北京 100089；2. 廣西行政學(xué)院應(yīng)急管理培訓(xùn)部，廣西 南寧 530021)

?

面向多災(zāi)點(diǎn)需求的應(yīng)急資源調(diào)度博弈模型及優(yōu)化

楊繼君1,2，佘 廉1

(1. 國(guó)家行政學(xué)院應(yīng)急管理培訓(xùn)中心，北京 100089；2. 廣西行政學(xué)院應(yīng)急管理培訓(xùn)部，廣西 南寧 530021)

非常規(guī)突發(fā)事件爆發(fā)后經(jīng)常會(huì)造成多個(gè)災(zāi)點(diǎn)，而各災(zāi)點(diǎn)的需求往往是不同的，單獨(dú)的應(yīng)急資源中心很難同時(shí)滿足這種要求，因此如何把多個(gè)應(yīng)急資源中心所儲(chǔ)備的應(yīng)急資源公平合理地調(diào)配到各個(gè)災(zāi)點(diǎn)成為應(yīng)急決策者亟待解決的現(xiàn)實(shí)問(wèn)題。本文首先描述了各災(zāi)點(diǎn)對(duì)應(yīng)急資源需求變化的動(dòng)態(tài)過(guò)程即按照應(yīng)急資源需求信息的變化將整個(gè)應(yīng)急資源調(diào)度過(guò)程劃分成若干階段，在此基礎(chǔ)上構(gòu)建了基于多災(zāi)點(diǎn)多階段的應(yīng)急資源調(diào)度過(guò)程理論模型。隨后以博弈論為工具，在進(jìn)行一系列模型假設(shè)和確定各災(zāi)點(diǎn)災(zāi)情的前提下，建立面向多災(zāi)點(diǎn)需求的應(yīng)急資源博弈調(diào)度模型，并采用改進(jìn)的蟻群算法進(jìn)行求解，實(shí)現(xiàn)對(duì)各災(zāi)點(diǎn)以最小的“虛擬成本”進(jìn)行所需應(yīng)急資源的調(diào)度。最后的模型仿真測(cè)試和算例分析驗(yàn)證了所建模型的有效性和可行性。該模型與算法也為商業(yè)物流中的資源配送提供了新的解決方案和實(shí)現(xiàn)途徑。

非常規(guī)突發(fā)事件；資源需求；調(diào)度博弈；改進(jìn)蟻群算法

1 引言

當(dāng)非常規(guī)突發(fā)事件發(fā)生后，通常會(huì)造成多個(gè)受災(zāi)點(diǎn)(后簡(jiǎn)稱“災(zāi)點(diǎn)”)，這在5.12汶川大地震中就有明顯的體現(xiàn)，此次地震中同時(shí)造成了汶川、北川、青川和綿竹等多個(gè)重災(zāi)點(diǎn)。通常情況下，各災(zāi)點(diǎn)的需求往往是不同的，同時(shí)隨著事態(tài)的不斷演化它們的需求也是不斷變化的，而且單獨(dú)的應(yīng)急資源中心很難同時(shí)滿足這種要求，因此把多個(gè)應(yīng)急資源中心所儲(chǔ)備的應(yīng)急資源公平合理地調(diào)配到各個(gè)災(zāi)點(diǎn)的研究更具有現(xiàn)實(shí)意義。

目前，國(guó)內(nèi)外針對(duì)多災(zāi)點(diǎn)的應(yīng)急資源調(diào)配方法已展開了一些研究：Shetty與Gupta[1-2]通過(guò)建立多災(zāi)點(diǎn)的非合作博弈模型探討應(yīng)急資源公平合理調(diào)度問(wèn)題，但是該模型是建立在完全信息基礎(chǔ)之上的，這與實(shí)際情況不符。Wang Susheng等[3]提出了通過(guò)各災(zāi)點(diǎn)方案調(diào)整算法來(lái)解決多災(zāi)點(diǎn)資源競(jìng)爭(zhēng)的問(wèn)題，但該算法對(duì)于多目標(biāo)問(wèn)題的求解呈現(xiàn)了一定的局限性。Rubel等[4]建立了基于Agent的多災(zāi)點(diǎn)應(yīng)急資源調(diào)配模型，以期解決應(yīng)急資源調(diào)配過(guò)程中低效率問(wèn)題，但在調(diào)配成本函數(shù)的構(gòu)建中僅考慮距離和時(shí)間兩個(gè)因素而忽略災(zāi)情的嚴(yán)重程度是其主要不足。王蘇生等[5]以雙層決策方法建立基于公平優(yōu)先原則的多災(zāi)點(diǎn)應(yīng)急資源配置模型及其算法，使應(yīng)急資源配置過(guò)程兼顧及時(shí)性和公平性，但該研究把成本最小化作為優(yōu)化目標(biāo)與應(yīng)急管理中的弱經(jīng)濟(jì)性明顯有出入。楊勃等[6]建立了多受災(zāi)點(diǎn)救災(zāi)物資分配調(diào)度模型及其啟發(fā)式求解算法，實(shí)現(xiàn)滿足所有受災(zāi)點(diǎn)物資需求的時(shí)間最小化，但該研究?jī)H涉及一類特殊情形即由單一資源中心向多個(gè)受災(zāi)點(diǎn)調(diào)配應(yīng)急資源的情形，其拓展性不強(qiáng)。王旭坪等[7]以前景理論為工具，建立了災(zāi)民感知滿意度的多災(zāi)點(diǎn)應(yīng)急資源分配模型，但災(zāi)民滿意度函數(shù)的刻畫缺乏客觀量化標(biāo)準(zhǔn)和科學(xué)依據(jù)，并且確定的方案不滿足動(dòng)態(tài)調(diào)整要求。詹沙磊等[8]在綜合考慮了需求點(diǎn)和配送路徑連通性的隨機(jī)性以及出救點(diǎn)對(duì)受災(zāi)點(diǎn)的最大覆蓋范圍等限制條件下建立了基于信息更新的應(yīng)急物資配送多目標(biāo)隨機(jī)規(guī)劃模型，該研究是建立在多個(gè)觀測(cè)時(shí)刻上的單次決策問(wèn)題，這與應(yīng)急決策中的動(dòng)態(tài)性和連續(xù)性相悖。蔡玫等[9]構(gòu)建多出救點(diǎn)、多受災(zāi)點(diǎn)的多目標(biāo)模糊調(diào)度優(yōu)化模型，采用模糊評(píng)價(jià)方法研究應(yīng)急決策者風(fēng)險(xiǎn)偏好對(duì)應(yīng)急物資調(diào)度策略的影響，劉曄等[10]從風(fēng)險(xiǎn)偏好的視角也做過(guò)類似研究。宋曉宇等[11]從物資調(diào)度費(fèi)用最小化和受災(zāi)點(diǎn)滿意度最大化的雙重目標(biāo)出發(fā)，構(gòu)建了多受災(zāi)點(diǎn)、多出救點(diǎn)、多階段動(dòng)態(tài)調(diào)度模型，可是該研究忽略了應(yīng)急物資調(diào)度中最為重要的目標(biāo)即時(shí)間最短問(wèn)題。張玲等[12]綜合考慮應(yīng)急資源保障的可靠性、不同情景的決策魯棒性和救災(zāi)代價(jià)的經(jīng)濟(jì)性等目標(biāo)建立了二階段災(zāi)后應(yīng)急救災(zāi)網(wǎng)絡(luò)模型，解決了應(yīng)急配送中心選擇和應(yīng)急救災(zāi)物資配送問(wèn)題，但在第二階段對(duì)滿足各個(gè)災(zāi)點(diǎn)所需應(yīng)急物資的均衡性沒(méi)有涉及；陳濤等[13]通過(guò)在二階段模型中引入信息更新機(jī)制也做過(guò)類似研究。阮俊虎等[14]以最小化總的醫(yī)療物資運(yùn)輸持續(xù)時(shí)間為目標(biāo)提出了基于聚類的兩階段醫(yī)療物資聯(lián)合運(yùn)輸模型，該模型和算法能夠有效選擇出應(yīng)急中轉(zhuǎn)點(diǎn)和安排具體的運(yùn)輸路線，不過(guò)把通往各醫(yī)療救助點(diǎn)的車輛行駛速度設(shè)為常數(shù)與實(shí)際情況有些出入，因?yàn)橥ㄍ麽t(yī)療點(diǎn)的路況各不相同(損壞程度不一樣)必然導(dǎo)致車輛行駛速度各異。許勝銘等[15]針對(duì)煤礦瓦斯爆炸事故的特點(diǎn)，通過(guò)引入受災(zāi)點(diǎn)人員傷亡密度和運(yùn)輸費(fèi)用兩個(gè)優(yōu)化目標(biāo)，構(gòu)建多出救點(diǎn)、多物資、多受災(zāi)點(diǎn)的應(yīng)急物資調(diào)度模型，該研究雖然具有很強(qiáng)的針對(duì)性，但把純粹運(yùn)輸費(fèi)用作為優(yōu)化目標(biāo)有些欠妥。筆者在上述研究成果的基礎(chǔ)上，綜合考慮各災(zāi)點(diǎn)的災(zāi)害嚴(yán)重程度、響應(yīng)時(shí)間和距離(應(yīng)急資源中心到災(zāi)點(diǎn)的距離)、路況等因素的情況下，以博弈論為工具構(gòu)建面向多災(zāi)點(diǎn)需求的應(yīng)急資源調(diào)度模型和智能求解算法，力圖實(shí)現(xiàn)對(duì)各個(gè)災(zāi)點(diǎn)進(jìn)行公平合理的應(yīng)急資源調(diào)度。

2 面向多災(zāi)點(diǎn)需求的應(yīng)急資源調(diào)度模型

2.1 模型假設(shè)

在每一階段，由于應(yīng)急資源中心所存儲(chǔ)的應(yīng)急資源是有限的，各個(gè)災(zāi)點(diǎn)所需資源可能是相互沖突的，具有對(duì)抗的性質(zhì)，應(yīng)用博弈論的語(yǔ)言，各災(zāi)點(diǎn)(局中人)間對(duì)應(yīng)急資源的需求就可認(rèn)為是非合作博弈的，它們博弈的目的是盡量以最小的“虛擬成本”獲得所急需的資源。

在建立面向多災(zāi)點(diǎn)需求的應(yīng)急資源調(diào)度博弈模型之前，作如下假設(shè)：

(1)具備先進(jìn)的應(yīng)急信息平臺(tái)即信息更新方式和速度滿足要求。在每一階段，應(yīng)急資源中心都能夠及時(shí)獲取災(zāi)點(diǎn)的數(shù)量、嚴(yán)重程度及所需資源量等狀況信息，同時(shí)各個(gè)災(zāi)點(diǎn)也能及時(shí)了解所有應(yīng)急資源中心的資源狀況；

(2)為了滿足各災(zāi)點(diǎn)的需求，需要多個(gè)應(yīng)急資源中心相互配合來(lái)完成。若該區(qū)域內(nèi)的應(yīng)急資源中心的應(yīng)急資源不能滿足需求，則可從離該區(qū)域最近的應(yīng)急資源中心獲取所需應(yīng)急資源；

(3)對(duì)各個(gè)災(zāi)點(diǎn)，根據(jù)災(zāi)情性質(zhì)、影響和嚴(yán)重程度進(jìn)行分類分級(jí)并預(yù)估響應(yīng)時(shí)間；

(4)最初對(duì)各個(gè)災(zāi)點(diǎn)的資源分配是在不考慮應(yīng)急資源中心的資源數(shù)量情況下，按照救災(zāi)單位“虛擬成本”最小原則進(jìn)行初始分配。而“虛擬成本”(后簡(jiǎn)稱“成本”)函數(shù)是一個(gè)多元復(fù)合函數(shù)，其影響因素為災(zāi)情的嚴(yán)重程度、響應(yīng)時(shí)間、平均速度和距離。這樣，首先需要對(duì)災(zāi)點(diǎn)向各應(yīng)急資源中心所支付的單位調(diào)度成本按大小進(jìn)行排序。當(dāng)多個(gè)災(zāi)點(diǎn)以相同單位成本向同一應(yīng)急資源中心調(diào)度資源，而該應(yīng)急資源中心所擁有的資源又無(wú)法滿足所有災(zāi)點(diǎn)的需求時(shí)，則就形成多個(gè)災(zāi)點(diǎn)對(duì)該應(yīng)急資源的競(jìng)爭(zhēng)。

2.2 基于非合作博弈的應(yīng)急資源調(diào)度模型構(gòu)建

將應(yīng)急資源調(diào)度模型映射為非合作博弈模型，該模型的標(biāo)準(zhǔn)形式定義如下：

G={t,N,(Si(t))i∈N,(P(t)i)i∈N}

(1)

其中，Si(t)是災(zāi)點(diǎn)i在t階段全部可選策略的集合即災(zāi)點(diǎn)i可采取的行動(dòng)方案，Pi(t)=Pi(s1,s2,…,sn)為災(zāi)點(diǎn)i在t階段的效用函數(shù)，它是由調(diào)度成本的倒數(shù)映射而來(lái)；s=(s1,s2,…,sn)為n個(gè)災(zāi)點(diǎn)的一個(gè)組合策略。

(1)資源調(diào)度的速度vik(t)

(2)

其中，μ(t)為路況系數(shù)，它反映的是應(yīng)急資源中心k到災(zāi)點(diǎn)i的道路好壞狀況，μ(t)∈[0,1]，路況越好，μ(t)越大。

(2)救災(zāi)單位成本函數(shù)cik(t)

救災(zāi)單位成本是應(yīng)急資源調(diào)度的依據(jù)，其函數(shù)定義如下：

(3)

(3)資源需求量與供應(yīng)量的確定

突發(fā)事件爆發(fā)后，首要的工作就是要確定受災(zāi)點(diǎn)的數(shù)量與所需要的資源種類和數(shù)量，同時(shí)還要確定所在區(qū)域內(nèi)各應(yīng)急資源中心所儲(chǔ)備的資源狀況。在我們的模型中規(guī)定：若區(qū)域內(nèi)所儲(chǔ)備的應(yīng)急資源不能滿足區(qū)域內(nèi)各災(zāi)點(diǎn)對(duì)資源的需求，則臨近區(qū)域的應(yīng)急資源中心自動(dòng)加入救災(zāi)行動(dòng)中，這樣做的目的一方面是為了實(shí)現(xiàn)快速救援，盡量減少災(zāi)區(qū)的生命和財(cái)產(chǎn)損失，另一方面也是為了保證救災(zāi)成本盡量最小化。為使問(wèn)題簡(jiǎn)化，以各災(zāi)點(diǎn)需要的同一類資源例如帳篷加以說(shuō)明，具體確定步驟如下：

① 在災(zāi)區(qū)內(nèi)，確定所有災(zāi)點(diǎn)所需資源總量

(4)

其中，qi表示第i個(gè)災(zāi)點(diǎn)所要的資源量。

② 確定區(qū)域內(nèi)各應(yīng)急資源中心所儲(chǔ)備的資源量

(5)

其中，uk為第k個(gè)應(yīng)急資源中心所能夠提供的資源量，M={1,2,…,m}為區(qū)域內(nèi)m個(gè)應(yīng)急資源中心集合。

③ 若Q>U，說(shuō)明該區(qū)域內(nèi)的應(yīng)急資源不能滿足災(zāi)區(qū)的需要，則臨近區(qū)域的應(yīng)急中心自動(dòng)進(jìn)入災(zāi)區(qū)進(jìn)行救災(zāi)，此時(shí)能夠提供的應(yīng)急資源總量為U=U+um+1+…um+k，直到U=Q為止；若Q≤U，說(shuō)明區(qū)域內(nèi)的資源是能夠滿足災(zāi)區(qū)需要的，不需要區(qū)域外應(yīng)急資源中心的援助。

(4)策略的構(gòu)建與簡(jiǎn)化

各災(zāi)點(diǎn)的信息集狀況是影響各災(zāi)點(diǎn)策略選擇和博弈結(jié)果的重要因素，也是構(gòu)建博弈策略的核心內(nèi)容。在本模型的構(gòu)建中，局中人的信息集包括以下內(nèi)容：①災(zāi)點(diǎn)的數(shù)量；②應(yīng)急資源中心的數(shù)量；③每個(gè)災(zāi)點(diǎn)到達(dá)各應(yīng)急資源中心的距離和路況信息；④災(zāi)點(diǎn)的災(zāi)情嚴(yán)重程度即各災(zāi)點(diǎn)的級(jí)別；⑤每個(gè)災(zāi)點(diǎn)所需要資源的數(shù)量。

(6)

圖1 災(zāi)點(diǎn)i的博弈調(diào)度策略構(gòu)建示意圖

其中，各災(zāi)點(diǎn)對(duì)特定應(yīng)急資源中心k的資源爭(zhēng)奪滿足的條件為：

(7)

各災(zāi)點(diǎn)因爭(zhēng)奪資源而進(jìn)行博弈時(shí)，必須首先確定各災(zāi)點(diǎn)采取的所有可能策略，只有這樣，每個(gè)災(zāi)點(diǎn)在其他災(zāi)點(diǎn)采取行動(dòng)時(shí)才能夠采取最優(yōu)行動(dòng)，使自己的效用最大化。各災(zāi)點(diǎn)在特定組合策略Sj下對(duì)某一應(yīng)急資源中心k的資源博弈過(guò)程如圖2所示。

圖2 各災(zāi)點(diǎn)對(duì)應(yīng)急資源中心k的資源博弈過(guò)程

假設(shè)應(yīng)急資源中心k儲(chǔ)備有uk單位的可用資源(k∈M)，則每個(gè)災(zāi)點(diǎn)從所有應(yīng)急資源中心獲取資源的所有可能的行動(dòng)方案數(shù)為Z=u1*u2*…*um，其資源調(diào)度策略為Si=(si,1,si,2,…,si,h(i))，其中h(i)≤Z。

按上述方法構(gòu)建的策略集中可能存在不可行的策略，因此有必要對(duì)其進(jìn)行剔出，使問(wèn)題得到簡(jiǎn)化。剔出不合理的行動(dòng)策略可依照如下兩條準(zhǔn)則來(lái)進(jìn)行：

② 對(duì)每個(gè)應(yīng)急資源中心的資源需求量不能超過(guò)該應(yīng)急資源中心所儲(chǔ)備的資源量即不能調(diào)度應(yīng)急資源中心不存在的資源，故須滿足式(7)。

(5)調(diào)度總成本函數(shù)的確定

(8)

(6)博弈策略的排序

為了使各個(gè)災(zāi)點(diǎn)按照成本最低原則選擇最優(yōu)策略向每個(gè)應(yīng)急資源中心調(diào)度資源，故對(duì)各個(gè)災(zāi)點(diǎn)的策略進(jìn)行合理排序是非常有必要的。

① 調(diào)度策略以調(diào)度總成本的大小按升序排列即調(diào)度成本越小的策略，其等級(jí)越高，排序越靠前；

② 若出現(xiàn)兩個(gè)調(diào)度策略的總成本相同，則以調(diào)度策略中調(diào)度單位成本最小的為最優(yōu)，依次類推。例如，災(zāi)點(diǎn)i的兩個(gè)策略分別為si,j和si,g，其調(diào)度總成本分別為Ci,j和Ci,g(按公式(8)求取)，各自的單位調(diào)度成本與對(duì)應(yīng)的調(diào)度資源的數(shù)量的比值最小來(lái)確定。設(shè)si,j和si,g所對(duì)應(yīng)的比值βsi,j、θsi,g分別為：

(9)

(10)

其中，式(9)和(10)中的分子按式(3)求取。若Ci,j=Ci,g，則分別求出βsi,j與θsi,g中最小值即

(11)

(12)

③ 災(zāi)點(diǎn)向應(yīng)急資源中心調(diào)度資源時(shí)，以單位調(diào)度成本最小原則進(jìn)行最大量的資源調(diào)度，這樣做的實(shí)質(zhì)是反映救災(zāi)時(shí)間緊迫原則即在盡量短的時(shí)間內(nèi)調(diào)度最大量的資源，其調(diào)度總成本也是最低的。式(3)和(8)就說(shuō)明了調(diào)度時(shí)間、調(diào)度的資源量、災(zāi)點(diǎn)的嚴(yán)重程度和調(diào)度成本的關(guān)系。

(7)收益函數(shù)

在博弈中，收益函數(shù)反映在一個(gè)特定的策略組合下局中人i所期望得到的效用水平，在應(yīng)急資源調(diào)度中，災(zāi)點(diǎn)i選擇某一調(diào)度策略j時(shí)調(diào)度單位成本從應(yīng)急資源中心k調(diào)度應(yīng)急資源量的多少來(lái)表示其效用的大小：

(13)

災(zāi)點(diǎn)i從所有應(yīng)急資源中心M調(diào)度所需資源的效用滿足疊加定理，可以表示如下：

(14)

(8)目標(biāo)函數(shù)

應(yīng)急資源調(diào)度的目標(biāo)是在對(duì)各個(gè)災(zāi)點(diǎn)實(shí)現(xiàn)公平調(diào)度的情況下，使總的效用函數(shù)最大化。

目標(biāo)函數(shù)定義如下：

(15)

(9)收益矩陣

局中人i收益矩陣可表示如下：

(16)

3 模型求解算法設(shè)計(jì)—改進(jìn)蟻群優(yōu)化算法

借鑒基本蟻群算法(Ant Colony Optimization, ACO)[16]的進(jìn)化思想，對(duì)其進(jìn)行必要的延伸和修改，將該算法拓展到博弈模型的納什均衡求解問(wèn)題中?；舅悸窞椋好恐晃浵伿紫冗M(jìn)行全局搜索，然后在各自鄰域內(nèi)進(jìn)行局部搜索，得到局部最優(yōu)解，完成一次進(jìn)化后，每只螞蟻依據(jù)各自所在的位置更新信息素強(qiáng)度。

3.1 全局搜索

各螞蟻根據(jù)當(dāng)前的信息素強(qiáng)度和適應(yīng)度函數(shù)計(jì)算轉(zhuǎn)移概率，并按公式(19)和(20)生成子代蟻群。

定義1 參考余謙和王先甲[17]，定義蟻群算法的適應(yīng)度函數(shù)(Fitness)如下：

(17)

定義2 轉(zhuǎn)移函數(shù)：

(18)

其中，f(Xi)為螞蟻i的適應(yīng)度函數(shù)，Δfij=f(Xi)-f(Xj)；τ(j)為螞蟻j的信息素強(qiáng)度值。

全局搜索中引入遺傳算法(GA)的交叉和變異操作，產(chǎn)生適應(yīng)度函數(shù)更優(yōu)的子代蟻群。螞蟻i根據(jù)轉(zhuǎn)移概率p選擇下一步移動(dòng)的目標(biāo)，按公式(19)生成子代個(gè)體：

Xi=δXi+(1-δ)Xj

(19)

式(19)不僅保證了螞蟻i向其他信息素濃度更高的螞蟻j的鄰域范圍內(nèi)移動(dòng)，而且保證了進(jìn)化后的子代蟻群仍然在博弈的混合策略空間內(nèi)，其中δ為在(0,1)內(nèi)產(chǎn)生的一個(gè)隨機(jī)數(shù)。

3.2 局部搜索

變鄰域搜索方法(Variable Neighbourhood Search, VNS)是Hansen等人[18]提出的一種啟發(fā)式算法，目前已被用于解決許多經(jīng)典的優(yōu)化問(wèn)題[19,20]。該算法從一個(gè)初始解開始，通過(guò)系統(tǒng)地改變鄰域搜索中的鄰域結(jié)構(gòu)來(lái)提高求解的質(zhì)量，避免陷入局部最優(yōu)。

每只螞蟻采用變鄰域搜索策略，在半徑為r的鄰域空間內(nèi)隨機(jī)搜索，并通過(guò)控制迭代步長(zhǎng)，使得各只螞蟻的位置始終保持在可行解范圍內(nèi)。

定義3 鄰域搜索公式：

(20)

其中，Xit表示螞蟻t搜索到局中人i的解策略，Δri表示[-r,r]之間的一組隨機(jī)搜索向量，為可變的鄰域搜索項(xiàng)。

定理1 若初始化的每只螞蟻在混合策略組合空間內(nèi)，即

根據(jù)以上的證明，可以保證蟻群中每個(gè)局中人的混合策略是在他的混合策略空間內(nèi)，因而螞蟻在進(jìn)化過(guò)程中始終保持在博弈的混合策略組合空間內(nèi)。

信息素更新規(guī)則：局部搜索結(jié)束后，按照如下公式更新信息素強(qiáng)度：

(21)

其中，λ是一個(gè)非常小的正數(shù)，防止出現(xiàn)除數(shù)為0的情況，ρ表示信息素?fù)]發(fā)系數(shù)。

3.3 改進(jìn)蟻群算法的效果分析

文中提出的改進(jìn)蟻群算法(Improved ACO)主要用于對(duì)所建的博弈模型進(jìn)行納什均衡求解。為了說(shuō)明其改進(jìn)效果，我們將與陳士俊等人[21]采用遺傳算法(GA)對(duì)納什均衡求解的效果進(jìn)行比較。選取陳士俊等[21]中的三維雙博弈矩陣， 采用改進(jìn)蟻群算法求解該博弈的納什均衡解，參數(shù)設(shè)置：

M=20，genMax=1000，gMax=100，R0=0.9，low-percentage=0.5，精度為10-4， high-percentage=1。

采用MATLAB[22]編程實(shí)現(xiàn)求解。 利用改進(jìn)蟻群算法求解該博弈的結(jié)果如表1所示。該博弈的唯一納什均衡為(1/3,1/3,1/3;1/3,1/3,1/3)，陳士俊等[21]采用遺傳算法計(jì)算400代得到該博弈的近似解(0.3333,0.3333,0.3333;0.3333,0.3333,0.3333)，而利用改進(jìn)蟻群算法平均進(jìn)化73代即得到該近似解。

表1 求解結(jié)果

圖3為采用遺傳算法和改進(jìn)蟻群算法求解該博弈的離線性能比較圖，GA曲線為遺傳算法的離線性能，Improved ACO曲線為改進(jìn)蟻群算法的離線性能。從圖3可以得知，改進(jìn)后的蟻群算法優(yōu)于遺傳算法，表現(xiàn)更快更好的收斂性能。

圖3 兩種算法求解博弈的離線性能比較

3.4 模型仿真測(cè)試與分析

仿真測(cè)試目的是為了評(píng)估所建模型的有效性和可行性。當(dāng)突發(fā)事件發(fā)生時(shí)，響應(yīng)時(shí)間關(guān)系到應(yīng)急資源中心是否能夠迅速采取有效措施，把應(yīng)急資源及時(shí)調(diào)度到各個(gè)災(zāi)點(diǎn)，減少時(shí)間延誤，降低災(zāi)害對(duì)社會(huì)正常秩序的沖擊和人員傷亡。救災(zāi)響應(yīng)時(shí)間的影響因素包括：①災(zāi)點(diǎn)的數(shù)量；②應(yīng)急資源中心的數(shù)量；③應(yīng)急資源中心所擁有的資源單位數(shù)量?，F(xiàn)分別從上述三個(gè)方面進(jìn)行仿真來(lái)分析模型的響應(yīng)時(shí)間情況。

測(cè)試數(shù)據(jù)假設(shè)：當(dāng)發(fā)生一次突發(fā)事件時(shí)，該區(qū)域的災(zāi)點(diǎn)數(shù)為2～4個(gè)，可以參與救災(zāi)的應(yīng)急資源中心為2～12，針對(duì)某一類特定資源最大供給總量為150個(gè)單位，每個(gè)災(zāi)點(diǎn)的最大需求量為60個(gè)單位，模型的其它相關(guān)參數(shù)隨機(jī)生成。下面所有測(cè)試都是針對(duì)某一類應(yīng)急資源。

測(cè)試1：?jiǎn)蝹€(gè)應(yīng)急資源中心所擁有應(yīng)急資源數(shù)量的變化對(duì)模型算法收斂時(shí)間的影響

在模型進(jìn)行每次測(cè)試時(shí)，首先保證每次測(cè)試的應(yīng)急資源中心的個(gè)數(shù)為常數(shù)的情況下，仿真結(jié)果為單個(gè)應(yīng)急資源中心所擁有資源數(shù)量的變化對(duì)模型算法收斂性的影響。圖4給出了應(yīng)急資源中心為10個(gè)，各災(zāi)點(diǎn)的總需求為100個(gè)單位的仿真結(jié)果和不同災(zāi)點(diǎn)數(shù)目下的對(duì)比曲線。

圖4 單個(gè)應(yīng)急資源中心資源量對(duì)收斂時(shí)間的影響

從圖4可知，隨著每個(gè)資源中心所擁有的應(yīng)急資源數(shù)量的增加，算法的收斂時(shí)間逐漸減少，其原因是資源量的增加導(dǎo)致了各災(zāi)點(diǎn)在該應(yīng)急資源中心減少了相互之間的競(jìng)爭(zhēng)機(jī)會(huì)，策略空間也相應(yīng)地變小，這樣必然會(huì)使算法的收斂性加快。比較理想的情況是就某種資源一個(gè)應(yīng)急資源中心能夠滿足需要該種資源的所有災(zāi)點(diǎn)，這樣各災(zāi)點(diǎn)就不會(huì)存在相互競(jìng)爭(zhēng)。但是，當(dāng)應(yīng)急資源中心所擁有的資源量超過(guò)一定范圍時(shí)，算法的收斂時(shí)間反而會(huì)增加，這可能是由于太多的災(zāi)點(diǎn)為了以支付較低成本來(lái)調(diào)度所需要的資源而匯集在某個(gè)應(yīng)急資源中心而進(jìn)行資源爭(zhēng)奪，結(jié)果反而導(dǎo)致博弈的策略空間變大，從而使算法的收斂時(shí)間延長(zhǎng)。另外，從圖4還可以看出，隨著災(zāi)點(diǎn)個(gè)數(shù)的增加，其收斂時(shí)間都有增大的趨勢(shì)，這是因?yàn)闉?zāi)點(diǎn)的增多，意味著參加博弈的局中人增加，相應(yīng)總的策略空間增大，所以其收斂時(shí)間就會(huì)有增大的趨勢(shì)。上述測(cè)試結(jié)果是與實(shí)際救災(zāi)情況相符的。

測(cè)試2:應(yīng)急資源中心數(shù)量變化對(duì)模型執(zhí)行時(shí)間的影響

在保證應(yīng)急資源單位總量為常數(shù)的情況下，應(yīng)急資源中心個(gè)數(shù)的變化對(duì)模型執(zhí)行時(shí)間的影響進(jìn)行仿真?，F(xiàn)就應(yīng)急資源總量為120個(gè)單位，各災(zāi)點(diǎn)總需求量為100個(gè)單位，各應(yīng)急資源中心所擁有的資源量為7～40個(gè)單位之間的條件下仿真結(jié)果如圖5所示。

圖5 應(yīng)急資源中心數(shù)量對(duì)模型執(zhí)行時(shí)間的影響

從圖5可知，當(dāng)應(yīng)急資源中心的數(shù)量比較少時(shí)(2～5個(gè))，模型的執(zhí)行時(shí)間比較長(zhǎng)，導(dǎo)致該結(jié)果的原因是由于應(yīng)急資源中心太少，幾乎所有的災(zāi)點(diǎn)都要到這些應(yīng)急資源中心調(diào)度所需資源，這樣就會(huì)使各災(zāi)點(diǎn)間需要進(jìn)行一系列的博弈來(lái)實(shí)行資源的最優(yōu)調(diào)度。相反，當(dāng)應(yīng)急資源中心個(gè)數(shù)增加時(shí)，各災(zāi)點(diǎn)調(diào)度所需要的資源就有更多的選擇，減少了相互之間博弈的機(jī)會(huì)，因此就降低了模型的執(zhí)行時(shí)間。另外，從圖5的對(duì)比曲線得知，隨著災(zāi)點(diǎn)個(gè)數(shù)的增加，模型的執(zhí)行時(shí)間逐漸增大，引起此種現(xiàn)象的原因是災(zāi)點(diǎn)個(gè)數(shù)的增加勢(shì)必增加了博弈的策略空間，會(huì)導(dǎo)致了更多的競(jìng)爭(zhēng)。這也都是與實(shí)際情況相符的。

4 算例分析

算例1：設(shè)某地區(qū)發(fā)生地震造成2個(gè)比較嚴(yán)重的災(zāi)點(diǎn)，該區(qū)域內(nèi)有2個(gè)應(yīng)急資源中心(分別用A和B表示)向?yàn)?zāi)點(diǎn)提供應(yīng)急資源(以帳篷為例)。另外，該區(qū)域附近有一個(gè)應(yīng)急資源中心(用C表示)。應(yīng)急資源供求關(guān)系如表2所示，假定平時(shí)車輛的運(yùn)輸速度為1 km/min，應(yīng)急資源中心到各災(zāi)點(diǎn)之間的距離如表3所示。1表示災(zāi)害等級(jí)程度高，2表示災(zāi)害等級(jí)程度一般，3表示災(zāi)害等級(jí)程度低。

分析：由表2可知，區(qū)域內(nèi)的應(yīng)急資源中心A和應(yīng)急資源中心B不能同時(shí)滿足2個(gè)災(zāi)點(diǎn)對(duì)帳篷的需求，因?yàn)镼=10(需求量)>U=8(供給量)，故該區(qū)域附近的應(yīng)急資源中心C自動(dòng)加入災(zāi)區(qū)的救災(zāi)行動(dòng)中，此時(shí)有Q=10

M=30，genMax=1000，gMax=10，

η=10-4，R0=0.9，low-percentage=0.5，

high-percentage=1，其它參數(shù)隨機(jī)生成。

表2 災(zāi)點(diǎn)/應(yīng)急救援中心資源供求關(guān)系

表3 應(yīng)急資源中心與各災(zāi)點(diǎn)間的距離(單位：km)

采用上述改進(jìn)蟻群優(yōu)化算法求解該博弈模型的Nash均衡解，5次計(jì)算結(jié)果如表4所示：

表4 求解結(jié)果

按照式(3)確定單位調(diào)度成本：

c1A=8；c1B=10；c1C=9

c2A=5；c1B=6；c1C=6

C1=3×8+10×0+9×1=33

C2=36, C=C1+C2=69

從上面的分析可知：災(zāi)點(diǎn)1首先從應(yīng)急資源中心A調(diào)度3個(gè)單位的帳篷，然后再?gòu)膽?yīng)急資源中心C調(diào)度1個(gè)單位的帳篷；而災(zāi)點(diǎn)2首先從應(yīng)急資源中心B調(diào)度5個(gè)單位的帳篷，然后從應(yīng)急資源中心C調(diào)度1個(gè)單位的帳篷來(lái)滿足資源需求。此時(shí)，按上述策略完成整個(gè)應(yīng)急資源調(diào)度任務(wù)所需要的總成本為69，成本最小，因而總體效用最大，故為最優(yōu)調(diào)度方案。

算例2：再考慮4個(gè)應(yīng)急資源中心，3個(gè)災(zāi)點(diǎn)的情形，參數(shù)設(shè)置與算例1相同。應(yīng)急資源供求關(guān)系如表5所示；應(yīng)急資源中心到各災(zāi)點(diǎn)之間的距離如表6所示：

表5 災(zāi)點(diǎn)/應(yīng)急救援中心資源供求關(guān)系

表6 應(yīng)急資源中心與各災(zāi)點(diǎn)間的距離(單位：km)

采用上述改進(jìn)蟻群優(yōu)化算法求解該博弈模型的Nash均衡解，5次計(jì)算結(jié)果如表7所示：

表7 求解結(jié)果

按照式(3)確定單位調(diào)度成本：

c1A=10；c1B=3；c1C=7；c1D=6

c2A=8；c2B=12；c2C=4；c2D=22

c3A=12；c3B=21；c3C=24；c3D=6

C1=10×1+3×8+7×0+6×0=34

C2=36，C3=36，C=106

從上面的分析可知：災(zāi)點(diǎn)1首先從應(yīng)急資源中心A調(diào)度1個(gè)單位的帳篷，然后再?gòu)膽?yīng)急資源中心B調(diào)度8個(gè)單位的帳篷；而災(zāi)點(diǎn)2首先從應(yīng)急資源中心A調(diào)度3個(gè)單位的帳篷，然后從應(yīng)急資源中心C調(diào)度3個(gè)單位的帳篷來(lái)滿足資源需求；災(zāi)點(diǎn)3首先從應(yīng)急資源中心A調(diào)度1個(gè)單位的帳篷，再?gòu)膽?yīng)急資源中心D調(diào)度4個(gè)單位的帳篷。此時(shí)，按上述策略完成整個(gè)應(yīng)急資源調(diào)度任務(wù)所需要的總成本為106，調(diào)度總成本最小，因而總體效用最大，故為最優(yōu)調(diào)度方案。

另外，算例2中平均計(jì)算時(shí)間(4.25s)大于算例1中平均計(jì)算時(shí)間(2.93s)，也間接驗(yàn)證了模型測(cè)試的正確性，因?yàn)殡S著災(zāi)點(diǎn)數(shù)量的增加(算例1中災(zāi)點(diǎn)數(shù)2，而算例2中災(zāi)點(diǎn)數(shù)為3)，模型的執(zhí)行時(shí)間逐漸增大，引起此種現(xiàn)象的原因是災(zāi)點(diǎn)個(gè)數(shù)增加勢(shì)必增加了博弈的策略空間，導(dǎo)致了更多的競(jìng)爭(zhēng)，這也是模型測(cè)試的基本結(jié)論之一。

5 結(jié)語(yǔ)

針對(duì)突發(fā)事件爆發(fā)后經(jīng)常會(huì)引發(fā)多個(gè)災(zāi)點(diǎn)的實(shí)際情況，通過(guò)分析各災(zāi)點(diǎn)為了獲取所需要的應(yīng)急資源而進(jìn)行相互競(jìng)爭(zhēng)的行為，具有非合作的性質(zhì)，但對(duì)各災(zāi)點(diǎn)進(jìn)行應(yīng)急資源調(diào)度時(shí)，又必須兼顧社會(huì)公平性，博弈論恰恰為此問(wèn)題的解決提供了有效途徑。因此，本文以博弈理論為分析工具，在確定各災(zāi)點(diǎn)災(zāi)情的基礎(chǔ)上，建立了面向多災(zāi)點(diǎn)需求的應(yīng)急資源調(diào)度博弈模型并給出了智能求解算法。最后的模型仿真測(cè)試和算例分析驗(yàn)證了所建模型的有效性和可行性。該模型與算法也為商業(yè)物流中的資源配送提供了新的解決方案和實(shí)現(xiàn)途徑。

[1] Shetty R, Gupta U. An automated decision support system based on game theoretic optimization for emergency management in urban[J]. Journal of Homeland Security and Emergency Management, 2007, 4(2): 1-25.

[2] Shetty R. An event driven single game solution for resource allocation in a multi-crisis environment[D]. Tampa: University of South Florida, 2004.

[3] Wang Susheng, Wang Yan, Sun Jian. An optimized emergency resources allocation algorithm for large-scale public emergency[C]// Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, August 19-22, 2007.

[4] Rubel D, Shinya H. An agent-based model for resource allocation during relief distribution[J]. Journal of Humanitarian Logistics and Supply Chain Management, 2014, 4(2): 265-285.

[5] 王蘇生, 王巖. 基于公平優(yōu)先原則的多受災(zāi)點(diǎn)應(yīng)急資源配置算法[J]. 運(yùn)籌與管理, 2008, 17(3): 16-21.

[6] 楊勃, 杜冰, 李小林. 多受災(zāi)點(diǎn)救災(zāi)物資分配調(diào)度問(wèn)題啟發(fā)式算法[J]. 系統(tǒng)工程, 2012, 30(1): 97-102.

[7] 王旭坪, 董莉, 陳明天. 考慮感知滿意度的多受災(zāi)點(diǎn)應(yīng)急資源分配模型[J]. 系統(tǒng)管理學(xué)報(bào), 2013, 22(2): 251-256.

[8] 詹沙磊, 劉南. 基于災(zāi)情信息更新的應(yīng)急物資配送多目標(biāo)隨機(jī)規(guī)劃模型[J]. 系統(tǒng)工程理論與實(shí)踐, 2013, 33(1): 159-166.

[9] 蔡玫, 羅倩, 朱莉,等. 面向應(yīng)急物資調(diào)度的一種模糊規(guī)劃模型[J]. 系統(tǒng)管理學(xué)報(bào), 2013, 22(4): 487-493.

[10] 劉曄, 姜國(guó)剛. 決策者風(fēng)險(xiǎn)態(tài)度對(duì)應(yīng)急物資調(diào)度影響研究[J]. 中國(guó)安全科學(xué)學(xué)報(bào), 2014, 24(8): 170-176.

[11] 宋曉宇, 王建國(guó), 常春光. 基于需求緊迫度的非線性連續(xù)消耗應(yīng)急調(diào)度模型與算法[J]. 信息與控制, 2014, 43(6): 735-743.

[12] 張玲, 陳濤, 黃鈞. 基于最小最大后悔值的應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建魯棒優(yōu)化模型與算法[J]. 中國(guó)管理科學(xué), 2014, 22(7): 131-139.

[13] 陳濤, 黃鈞, 朱建明. 基于信息更新的兩階段魯棒-隨機(jī)優(yōu)化調(diào)配模型研究[J]. 中國(guó)管理科學(xué), 2015, 23(10): 67-77.

[14] 阮俊虎, 王旭坪, 楊挺. 大規(guī)模災(zāi)害中基于聚類的醫(yī)療物資聯(lián)合運(yùn)送優(yōu)化[J]. 中國(guó)管理科學(xué), 2014, 22(10): 80-89.

[15] 許勝銘, 景國(guó)勛. 煤礦瓦斯爆炸事故的應(yīng)急救援物資調(diào)度模型研究[J]. 安全與環(huán)境學(xué)報(bào), 2015, 15(5): 104-107.

[16] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperative agents[J]. IEEE Transactions on SMC, 1996, 26(1): 28-41.

[17] 余謙, 王先甲. 基于粒子群優(yōu)化求解納什均衡的演化算法[J]. 武漢大學(xué)學(xué)報(bào)(理學(xué)版), 2006, 52(1): 25-29.

[18] Mladenovic N, Hansen P. Variable neighbourhood search[J]. Computers and Operations Research, 1997, 24(11): 1097-1100.

[19] Hansen P, Mladenovic N, Peter J A. Variable neighbourhood search: Methods and applications[J]. Annals of Operations Research, 2010, 175(1): 367-407.

[20] 曹正洋, 許維勝, 徐志宇. 開放式兩級(jí)車輛路徑問(wèn)題建模與多起始點(diǎn)變鄰域下降法求解[J]. 計(jì)算機(jī)科學(xué), 2014, 41(10): 232-237.

[21] 陳士俊, 孫永廣, 吳宗鑫. 一種求解NASH均衡解的遺傳算法[J]. 系統(tǒng)工程, 2001, 19(5): 67-70.

[22] 劉維. 精通Matlab與C/C++混合程序設(shè)計(jì)(第二版)[M]. 北京：北京航空航天大學(xué)出版社, 2008.

Game Model and Optimization Based on Resource Requirements of Multiple Crisis Locations

YANG Ji-jun1,2, SHE Lian1

(1. National Institute of Emergency Management, Chinese Academy of Governance, Beijing 100089,China；2. Department of Emergency Management, Guangxi Institute of Administration, Nanning 530021,China)

There would always be a lot of crisis locations when an unconventional emergency breaks out. The requirements of each crisis location are usually different, which is difficult to meet the requirements of multiple crisis locations for a single resource centre. So it is a practical problem to be solved urgently by decision makers how to fairly and reasonably schedule emergency resources for multiple crisis locations. According to the demand information, the dynamic process of emergency resources scheduling for multiple crisis locations are described, in which the emergency resources scheduling process are divided into several stages according to the change of demand information for multiple crisis locations. On this basis, a theoretical model of multi-stage emergency resources scheduling process is designed for multiple crisis locations. After a series of assumptions are made, the game model based on resource requirements of multiple crisis locations is set up by using game theory according to the degree of disaster, and the improved ant colony optimization (ACO) is introduced to seek out the solution in order to schedule emergency resources for multiple crisis locations according to the minimum virtual cost. Simulation tests and numerical analyses are given to demonstrate the feasibility and availability of the model. The model and algorithm can also provide a new solution and approach for the distribution of resources in business logistics.

unconventional emergency；resource requirements；game scheduling；improved ACO

2015-07-15；

2016-01-06

國(guó)家社科基金重點(diǎn)資助項(xiàng)目(16AGL017)；國(guó)家自然科學(xué)基金重大研究計(jì)劃(91324203)；中國(guó)博士后基金項(xiàng)目(2015M570995)

簡(jiǎn)介：楊繼君(1973-)，男(土家族)，湖南石門人，國(guó)家行政學(xué)院應(yīng)急管理培訓(xùn)中心博士后，英國(guó)紐卡斯?fàn)柎髮W(xué)訪問(wèn)學(xué)者，博士，副教授，研究方向：應(yīng)急管理與博弈論，E-mail: peteryang708@163.com.

TP393.07

A

1003-207(2016)08-0154-10

10.16381/j.cnki.issn1003-207x.2016.08.019