鄧 婕，池 宏，許保光

(1.中國科學(xué)院科技政策與管理科學(xué)研究所，北京 100190;2.江南大學(xué)商學(xué)院，江蘇 無錫 214122; 3.中國科學(xué)院大學(xué)公共政策與管理學(xué)院，北京 100049)

?

基于有向圖相似的應(yīng)急響應(yīng)程序模塊化問題研究

鄧 婕1,2，池 宏1,3，許保光1,3

(1.中國科學(xué)院科技政策與管理科學(xué)研究所，北京 100190;2.江南大學(xué)商學(xué)院，江蘇 無錫 214122; 3.中國科學(xué)院大學(xué)公共政策與管理學(xué)院，北京 100049)

對于發(fā)生頻率低，影響力大的突發(fā)事件，組織與個人的應(yīng)急經(jīng)驗將影響判斷與決策。應(yīng)急響應(yīng)程序在突發(fā)事件的響應(yīng)過程中起著指導(dǎo)作用，通過對多個應(yīng)急預(yù)案中響應(yīng)程序分析發(fā)現(xiàn)，一些行動措施經(jīng)常按照固定次序重復(fù)出現(xiàn)，如果將這種組合關(guān)系規(guī)范化，并固定成為模塊，響應(yīng)時間將會縮短，應(yīng)急機構(gòu)與人員之間的協(xié)調(diào)將會改善，模塊的產(chǎn)生為應(yīng)急預(yù)案的快速調(diào)整以及應(yīng)急培訓(xùn)提供參考方案。本文的主要目的是從多個應(yīng)急響應(yīng)程序中提取具有通用性與特殊性的模塊，首先對多個應(yīng)急響應(yīng)程序疊加起來的有向總圖進行了分割，通過定義的有向圖相似性判斷候選模塊的代表性，最后以復(fù)原應(yīng)急響應(yīng)程序的差異性之和與模塊接口之和為目標(biāo)，建立數(shù)學(xué)規(guī)劃模型，并設(shè)計啟發(fā)式算法求解，將有向總圖所有的邊分配到響應(yīng)程序模塊。通過案例計算分析，驗證所提方法可以獲得所需模塊，并為實現(xiàn)應(yīng)急響應(yīng)程序快速重構(gòu)與功能組合提供了方法基礎(chǔ)。

應(yīng)急管理；有向圖相似；響應(yīng)程序模塊；模塊化

1 引言

隨著我國突發(fā)事件的頻繁發(fā)生，政府與社會也越來越重視應(yīng)急預(yù)案的建設(shè)和管理工作。應(yīng)急預(yù)案跟法律法規(guī)一樣以文本形式存在，它包含了應(yīng)急方針、組織機構(gòu)與職責(zé)、風(fēng)險分析、能力評估、應(yīng)急響應(yīng)程序和支持附件等，作為應(yīng)急響應(yīng)第一處置行動的主要依據(jù)[1]，當(dāng)前的應(yīng)急響應(yīng)程序通常用流程圖的形式表示。由于突發(fā)事件具有突發(fā)性、蔓延性、不確定性等特點，響應(yīng)的即時性與準確性可以最大程度挽救生命與財產(chǎn)損失，因此響應(yīng)過程中不斷出現(xiàn)的征兆或者搜集的信息對應(yīng)急響應(yīng)程序的編制提出了快速調(diào)整的要求。在制造業(yè)中存在全球化、多樣性帶來的小批量大批次的新制造需求，而可重構(gòu)制造系統(tǒng)通過靈活的模塊快速安排制造系統(tǒng)成功的解決了這個問題，通過制造業(yè)的啟示，對同一類型的應(yīng)急響應(yīng)程序研究發(fā)現(xiàn)，在相同場景下，總是重復(fù)出現(xiàn)一些相同且邏輯關(guān)系固定若干措施(行動)集合，這些行動集合可以用來實現(xiàn)一定的功能，如果將這些行動集合定義為模塊，當(dāng)處置需求發(fā)生變動時，可以通過模塊的修改、替代、增加、刪除等操作活動，實現(xiàn)模塊的快速重組。有學(xué)者已經(jīng)意識到應(yīng)急響應(yīng)程序模塊化可以解決應(yīng)急響應(yīng)的結(jié)構(gòu)化管理和動態(tài)調(diào)整問題，并在文章中提到了模塊化的思想與重要性[2-3]。

“模塊化”思想在應(yīng)急管理領(lǐng)域已有少量研究涉及，下面將從應(yīng)急流程、應(yīng)急預(yù)案以及應(yīng)急系統(tǒng)方面進行闡述。應(yīng)急流程方面，田軍等[4]通過統(tǒng)一建模語言(UML)對應(yīng)急任務(wù)之間的依賴關(guān)系進行描述，從任務(wù)之間的流依賴和資源依賴中的角色依賴、設(shè)備依賴和設(shè)施依賴的關(guān)系強度方面提出依賴量指標(biāo)，建立了應(yīng)急任務(wù)活動的聚類優(yōu)化模型，獲得具有高內(nèi)聚和松散連接的流程模塊。鄧婕等[5]為提高響應(yīng)程序動態(tài)調(diào)整效率，通過定義緊密度與代表性，建立多目標(biāo)數(shù)學(xué)規(guī)劃模型，并設(shè)計蟻群算法進行求解，通過算例分析發(fā)現(xiàn)可以為響應(yīng)程序模塊化提供有效合理的方案。姜艷萍等[6]提出了一種風(fēng)險決策方法，以應(yīng)急效果與實踐作為評價指標(biāo)，可以實現(xiàn)應(yīng)急決策方案動態(tài)調(diào)整問題，從而獲得最優(yōu)方案，同理，王劍和羅東[7]也是為了解決應(yīng)急決策問題，建立了貝葉斯決策網(wǎng)絡(luò)agent應(yīng)急決策模型，從而來選擇決策方案，二者的方案均為場景下的處置措施集合，都可以視為模塊。應(yīng)急預(yù)案方面，榮莉莉和楊永俊[8]針對預(yù)案應(yīng)急響應(yīng)流程WBS分解定義了核心任務(wù)，每個核心任務(wù)包含著一些具體問題，每個問題由一個應(yīng)急處置措施來回答，其提出核心任務(wù)在一定程度上可以等同于本文中去掉邏輯關(guān)系的模塊。Liu Lei等[9]提出了基于預(yù)案模塊化，通過功能與需求相匹配原則重構(gòu)生成新預(yù)案的思路，并建立了預(yù)案重構(gòu)的框架。Girard等[10]提出了對當(dāng)?shù)貞?yīng)急響應(yīng)計劃的事前評估來告知決策者可能失效的環(huán)節(jié)，以便有機會對脆弱環(huán)節(jié)加強，其中應(yīng)急響應(yīng)計劃是由模塊按順序組成，評估方法為故障樹方法。Turoff等[11]使用動態(tài)情景模型來應(yīng)對潛在的突發(fā)事件，模型中要考慮一系列的因素以及必要事件，此必要事件等同與本文的模塊。應(yīng)急系統(tǒng)方面，Mendonc等[12]在文中指出在應(yīng)急管理需要一些靈活的模塊來保證安全、有效的應(yīng)急響應(yīng)，這些模塊可以處理不確定性與挑戰(zhàn)性情景，以及幫助計劃進行調(diào)整。Yoon等[13]也是主要研究交通輔助決策系統(tǒng)評價方法的有效性，文中系統(tǒng)是由計劃、資源、信息、交流四個大模塊組成，每個大模塊下具有小模塊，通過抽取小模塊作為組成新計劃。以上所有的文章，應(yīng)急流程類文章沒有提供模塊接口，并且丟失了模塊內(nèi)活動間銜接關(guān)系；應(yīng)急預(yù)案只是介紹了模塊的概念以及使用情況，應(yīng)急系統(tǒng)類文章的重點在評估方法的有效性，并未給出模塊的來源以及依據(jù)；因此模塊的啟用場景以及接口可插性是本文的一個創(chuàng)新點。

有向圖的相似性在數(shù)據(jù)挖掘中有較多的應(yīng)用，目前使用的相似性方法大致可以分為以下三類[14]:基于圖同構(gòu)的方法[15-16]、基于特征的方法[17]、基于迭代的方法[18]。SimRank算法為迭代算法中較為成功的算法，最開始應(yīng)用在計算圖的自相似性上，通過對矩陣A2(A為鄰接矩陣)迭代計算一個圖中任意兩個節(jié)點的相似性，當(dāng)相似分數(shù)收斂時算法結(jié)束。Blondel等[19]通過兩個有向圖的鄰接矩陣計算將這個方法擴充用到兩個有向圖的相似性比較中，其方法關(guān)注的是節(jié)點的相似性；Zager和Verghese[20]提出了圖相似與匹配的一種遞歸方法，這種方法引入了有向的邊與節(jié)點的相似分數(shù)的觀點來計算兩個有向圖的相似性。Bayati等[21]用信息傳遞算法提出了兩種稀疏圖匹配算法，即將尋找給定兩個圖節(jié)點的關(guān)系問題表達為整數(shù)二次規(guī)劃問題，然后用belief propagation(BP)算法來求解。雖然以上的相似性計算方法與匹配方法給了本文啟示，但是本文需要計算有向圖的相似性，且有向圖中節(jié)點具有唯一標(biāo)示，不需要計算不同標(biāo)識節(jié)點之間的相似性，因此前面介紹的方法需要經(jīng)過改進來適應(yīng)本文的需求。

為了提取網(wǎng)絡(luò)圖表達的應(yīng)急響應(yīng)程序中具有代表性與通用性的模塊化，本文希望通過定義有向圖相似性，建立應(yīng)急響應(yīng)程序模塊化模型，通過場景約束與圖分割方法獲得候選模塊，并設(shè)計啟發(fā)式算法對候選模塊進行調(diào)整，達到模塊化目的，產(chǎn)生一些好的初始方案，以供應(yīng)急專家在應(yīng)急決策支持中快速調(diào)用。

2 問題描述和數(shù)學(xué)模型

本文的問題來源于航空公司的應(yīng)急預(yù)案重構(gòu)需求，由于應(yīng)急機構(gòu)的不同，模塊的規(guī)?？纱罂尚?，從政府層面，一個應(yīng)急機構(gòu)可以算是一個大模塊，從企業(yè)層面，一個部門的功能模塊。本文通過分析自然災(zāi)害與事故災(zāi)難類突發(fā)事件，將突發(fā)事件劃分為若干個階段，每個階段具有一定的場景與處置目標(biāo)，模塊在這樣的情況下進行使用。本文將需要模塊化的多個應(yīng)急響應(yīng)程序重疊起來形成有向圖，該圖中具有節(jié)點、邊、場景等屬性，在定義了有向圖相似性與場景約束條件下，建立數(shù)學(xué)模型對有向圖進行分割。

2.1 相關(guān)知識介紹

定義1 源節(jié)點矩陣、目標(biāo)矩陣、出度、入度

如圖1，在一個有m個節(jié)點，n條邊的圖GA中，讓oA(i)代表邊i的源節(jié)點(開始節(jié)點)，tA(i)代表邊i的目標(biāo)節(jié)點(結(jié)束節(jié)點)，通過m*n的矩陣可以表達GA的鄰接結(jié)構(gòu)，那么源節(jié)點矩陣AO和目標(biāo)節(jié)點矩陣AT定義為以下公式：

(1)

(2)

圖1 源節(jié)點矩陣、目標(biāo)矩陣

定義2 圖匹配

給定兩個圖GA=(VA,EA),|VA|=nA和GB=(VB,EB),|VB|=nB，這兩個圖的匹配是一個從圖GA節(jié)點到圖GB節(jié)點的一對一映射M。映射M可以用節(jié)點對集合表示，每一節(jié)點對為(a,b),a∈VA,b∈VB。通常用一個nA×nB的映射矩陣M表示，矩陣中每一個元素M(a,b),a∈VA,b∈VB定義為:

兩個圖的匹配問題可以用著名的二分圖匹配算法解決。這個二分圖由兩個圖的節(jié)點構(gòu)成，二分圖邊上的權(quán)值是圖節(jié)點間的相似值。在我們的問題中，GA與GB均有相同的大小(nA=nB=n)，因而可以直接采用解決指派問題的匈牙利算法。問題可以定義為：用VA中的n個節(jié)點對應(yīng)VB中的n節(jié)點，VA中每個節(jié)點只能與VB中的一個節(jié)點相對應(yīng)，并且使得對應(yīng)上的節(jié)點間的相似值總和最大。令Xij表示VA中的節(jié)點i與VB中的節(jié)點j對應(yīng)關(guān)系，Xij=1，節(jié)點i、j對應(yīng)，否則Xij=0；Sij表示VA中的節(jié)點i與VB中的節(jié)點j間的相似值，問題的數(shù)學(xué)模型為：

滿足以下約束條件：

Xij∈{0,1},?i,j=1,…,n

2.2 相似性定義

本文的思路，根據(jù)圖分割后獲得的模塊，給定代表性閾值，模塊可以會存在的各種子結(jié)構(gòu)，如果應(yīng)急響應(yīng)程序包含子結(jié)構(gòu)，即子結(jié)構(gòu)可以在應(yīng)急響應(yīng)程序中找到，那么說明模塊與應(yīng)急響應(yīng)程序相似。下面將定義有向圖的相似性，首先介紹一下節(jié)點相似性。

(一)節(jié)點相似性

(3)

(二)有向圖相似性

計算兩個有向圖GA和GB的相似性有以下三步：(1)計算標(biāo)識相同的節(jié)點相似性；(2)無向圖將用上一步計算出的節(jié)點相似性構(gòu)造一個二分圖，再在該二分圖上找到一個最大權(quán)值匹配，但是對于表達應(yīng)急響應(yīng)程序的有向圖而言，標(biāo)識不同的節(jié)點就是兩個不同的行動，沒法進行匹配，因此只需要對標(biāo)識相同的節(jié)點進行權(quán)值匹配；(3)所有匹配節(jié)點間相似性的總和并歸一化后，即為兩個圖之間的相似性。

根據(jù)前面介紹的步驟與應(yīng)急響應(yīng)程序的節(jié)點標(biāo)識特殊性，GA與GB的相似性可以定義為匹配節(jié)點間的相似值求和，并用GA與GB節(jié)點數(shù)之積的平方根進行標(biāo)準化。

(4)

2.3 模塊化的目標(biāo)

從應(yīng)急響應(yīng)指揮者角度出發(fā)，希望應(yīng)急響應(yīng)開展過程中的管理是從粗到細的過程，即每層或者每個階段(模塊)具有管理者，這樣的分工將有利于應(yīng)急任務(wù)的對接與管理。行動作為應(yīng)急響應(yīng)程序的最小組成單元，在進行統(tǒng)一標(biāo)準化后，即明確行動為響應(yīng)突發(fā)事件的過程中具體的某人或者某類相同性質(zhì)的人組成的小團隊承擔(dān)的單一性質(zhì)的工作，應(yīng)急響應(yīng)程序可以抽象為網(wǎng)絡(luò)計劃圖，對多個應(yīng)急響應(yīng)程序網(wǎng)絡(luò)計劃圖分析發(fā)現(xiàn)，由多個行動銜接組成的工作流(模塊)重復(fù)出現(xiàn)在多個應(yīng)急響應(yīng)程序中且可以實現(xiàn)一定功能。如果將這些相似且有序的行動組合用模塊替換的話，應(yīng)急響應(yīng)程序網(wǎng)絡(luò)計劃圖就會變得的簡潔明了，從管理角度出發(fā)，此措施可以方便以后的指揮管理、培訓(xùn)、能力評估以及進行資源準備。為了達成指揮者形成模塊的需求，可以利用以下兩個目標(biāo)獲得質(zhì)量較高的模塊。

目標(biāo)1：差異性之和最小化

從全局出發(fā)，盡量將同場景下出現(xiàn)頻率高且具有相同功能的多個相似網(wǎng)絡(luò)計劃圖提取作為模塊，那么在復(fù)原應(yīng)急響應(yīng)程序的時候，可以調(diào)用模塊快速組成應(yīng)急響應(yīng)程序，因此模塊的合理性體現(xiàn)在被應(yīng)急響應(yīng)程序調(diào)用時復(fù)原應(yīng)急響應(yīng)程序的復(fù)原程度，如果模塊復(fù)原的應(yīng)急響應(yīng)程序與原應(yīng)急響應(yīng)程序相比差異較少，即冗余與缺失的行動與邊較少，則復(fù)原程度好，模塊設(shè)置合理，否則設(shè)置不太合理，因此差異性之和最小化可以作為目標(biāo)來獲得質(zhì)量較優(yōu)的解。

目標(biāo)2：模塊之間接口之和最小化

接口一詞普遍出現(xiàn)在計算機領(lǐng)域中，它的含義是信息交換的共享邊界。對于響應(yīng)程序模塊而言，其特點是功能明確，接口較少，這樣工作交接需要協(xié)調(diào)的部門少，方便了責(zé)任追究與管理。響應(yīng)程序模塊是從應(yīng)急響應(yīng)程序總圖中分割出來，根據(jù)點分割的思想希望模塊間的通信，即模塊間的切點的重復(fù)數(shù)量最少，因此無論是模塊本身以及圖分割，模塊之間接口之和最小化應(yīng)該作為一個目標(biāo)。

2.4 圖模塊化問題描述

決策問題是從G(V,E)的所有分割集合為Θ中找到一種合理分割模式來滿足應(yīng)急響應(yīng)程序復(fù)原后差異性之和最小與模塊間接口之和最小的需求，并獲得若干子圖(g1,g2,…，gc)形成程序模塊，其中g(shù)c是第c個模塊，C是模塊的總數(shù)。設(shè)決策變量為xgci,xgci=1,?i∈G(V),gc∈{g1,g2,…，gc}表示將i納入程序模塊gc，即i∈gc，否則xgci=0；假設(shè)gc執(zhí)行的場景為d，響應(yīng)程序k有多個場景，其中場景d對應(yīng)的子圖用gc(k)表示，用Sgcgc(k)表示程序模塊gc與響應(yīng)程序子圖gc(k)的相似性，ξ表示相似性閾值，若存在Sgcgc(k)≥ξ，則接受gc為一個模塊，并可以在復(fù)原應(yīng)急響應(yīng)程序k時使用，表示為zkgc=1,?gc∈{g1,g2,…，gc}；否則，不接受表示為zkgc=0,?gc∈{g1,g2,…，gc}。

2.5 數(shù)學(xué)模型

符號說明

k 應(yīng)急響應(yīng)程序下標(biāo)(k∈K)

c模塊下標(biāo)(c∈{1,…，C})

(i,j)表示E(G)中的一條邊

gc為第c個程序模塊

gc(k)表示在與gc相同場景下響應(yīng)程序k對應(yīng)的子圖

ξ為相似性閾值

決策變量

則數(shù)學(xué)模型為

(5)

(6)

(7)

xgcixgcj=ygcij?gc∈{g1,g2,…，gc},

i∈V(G),j∈V(G),i≠j,(i,j)∈A(G)

(8)

xgcixgcj-Dij≤0，?gc∈{g1,g2,…，gc},

i∈V(G),j∈V(G),i≠j,(i,j)∈A(G)

(9)

(10)

xgci∈{0,1},?gc∈{g1,g2,…，gc},i∈V(G)

(11)

ygcij∈{0,1},?gc∈{g1,g2,…，gc},(i,j)∈A(G),i≠j

(12)

zkgc∈{0,1},?k∈K,gc∈{g1,g2,…，gc}

(13)

其中式(5)為目標(biāo)1差異之和，它一共由四部分組成：第一部分為與原應(yīng)急響應(yīng)程序相比缺失的邊，第二部分為與原應(yīng)急響應(yīng)程序相比冗余的邊，第三部分為與原應(yīng)急響應(yīng)程序相比缺失的點，第四部分為與原應(yīng)急響應(yīng)程序相比冗余的點；式(6)為目標(biāo)2模塊接口之和；式(7)是保證總圖的邊被分配給一個模塊，且每條邊且被分配一次；式(8)是保證分配到同一個模塊的兩個節(jié)點，連接二者的邊也被分配給此模塊，若兩個節(jié)點分到不同模塊，二者之間不存在連邊；式(9)保證一個模塊內(nèi)的行動是同一個場景；由于本文采用點分割的模式對有向圖進行分割，因此式(10)為確定切分點；式(11)-(13)為決策變量。

3 啟發(fā)式算法

本文將在多個應(yīng)急響應(yīng)程序網(wǎng)絡(luò)計劃圖映射的總圖G，對G圖中所有的邊采用圖分割的方式分配到子圖中來獲得模塊。由于事先不確定G需要劃分的模塊數(shù)量C，因此本文是先根據(jù)場景數(shù)量獲得候選模塊，然后對候選模塊中不滿足約束條件的節(jié)點不斷剪枝來獲得新的候選模塊，當(dāng)候選模塊的改進不能影響目標(biāo)增量加權(quán)或者相似性增量之和時，算法結(jié)束。本文中的啟發(fā)式算法主要采用剪枝原理，實際屬于窮舉法，最后形成了C個模塊，那么進行了C-1次剪枝，剪枝后比較兩個圖的相似性，那么其計算復(fù)雜度為O(2(C-1))，因此該算法可以適用規(guī)模較大的數(shù)據(jù)。

(1)剪枝原理

本文剪枝操作是從候選模塊gc與應(yīng)急響應(yīng)程序k在gc執(zhí)行場景下對應(yīng)的子圖gc(k)的相似性出發(fā)，通過設(shè)定相似性閾值ξ與相似性閾值下限θ將具有通用性與特殊性的模塊全部提取出來，θ的提出是為了提高相似性低模塊的剪枝速度。如果gc與gc(k)大部分相似，但又都不滿足相似性閾值，即θ

對于剪出來的子圖也需要優(yōu)化，即判斷這些新增的子圖是否可以合并成新的候選模塊，如果能合并，將其作為新的候選模塊gc，再對gc與gc(k)的相似性判斷是否需要剪枝。

(2)算法結(jié)束條件

在對候選模塊的優(yōu)化過程中，候選模塊的數(shù)量會隨著剪枝操作而不斷增加，即有向圖的切點也會增加，那么f2的值就會增大，但是隨著模塊的規(guī)模變小，即模塊包含的節(jié)點與關(guān)系變少，調(diào)用其復(fù)原應(yīng)急響應(yīng)程序的質(zhì)量也就越好，f1就會變小。為了解決本文中相互矛盾的雙目標(biāo)，需要設(shè)定一個指標(biāo)來平衡其關(guān)系，由于兩個目標(biāo)值的數(shù)量級有可能不一致，本文將采用兩個目標(biāo)增量加權(quán)Δfn的方式來解決這一問題的，表達見下式(14)，其中第一部分為目標(biāo)1在第n次剪枝后的增量，第二部分為目標(biāo)2在第n次剪枝后的增量，然后將兩個目標(biāo)增量的加權(quán)Δfn作為此次算法終止的指標(biāo)，當(dāng)Δfn小于某個設(shè)定值ε，可以認為目標(biāo)值沒有改進的空間，算法結(jié)束。

(14)

Δsimn=

(15)

4 算例

本文算例選取航空公司現(xiàn)有的起落架故障、空中顛簸、空中停車三個應(yīng)急響應(yīng)程序?qū)ζ淝蠼忭憫?yīng)程序模塊，由于應(yīng)急響應(yīng)程序涉及的行動數(shù)量較多，因此用編號表示，圖2至圖4分別是這3個應(yīng)急響應(yīng)程序的網(wǎng)絡(luò)圖。

圖2 起落架故障應(yīng)急響應(yīng)程序

圖3 輪胎故障應(yīng)急響應(yīng)程序

圖4 爆炸物應(yīng)急響應(yīng)程序

本文將對三組應(yīng)急響應(yīng)程序進行模塊化，首先將三個應(yīng)急響應(yīng)程序合并形成圖5中應(yīng)急響應(yīng)程序總圖G，通過對航空公司應(yīng)急工作的分析發(fā)現(xiàn)，基本存在以下幾個場景：接收信息S1、啟動預(yù)案S2、現(xiàn)場處置S3、關(guān)閉預(yù)案S4，由于存在跨場景的行動集合，因此這些行動集合需要單獨作為模塊。在場景約束下，圖5的最初模塊數(shù)量為6個，其中模塊(a)在場景S1下啟動的信息上傳下達，模塊(b)在場景S2下啟動的人員集結(jié)，模塊(c)、(d)在場景S3下啟動的非安全落地與安全落地下現(xiàn)場處置,模塊(e)為跨場景模塊媒體應(yīng)對，其位于在場景S2與S4中，模塊(f)在場景S4下啟動的預(yù)案關(guān)閉，隨著剪枝過程模塊數(shù)量在原始數(shù)量基礎(chǔ)上增加。

本文在給定相似性閾值下限θ為0.3，相似性閾值ξ為0.75、終止條件閾值ε為0.01的情況下，經(jīng)過算法計算獲得結(jié)果見表1，由于將圖5中的模塊與圖2-4分別計算相似性，發(fā)現(xiàn)圖5中(a)、(c)、(e)、(f)其它模塊與圖2-4應(yīng)急響應(yīng)程序中對應(yīng)的子圖相似性都為1，不需要剪枝，即圖6中的模塊(A)、(E)、(G)、(K)，然而模塊(b)、(d)相似性低需要剪枝。第1次剪枝，模塊(b)被切分成3個模塊，其中2個為特殊性模塊(D)、(F)，其對應(yīng)的功能為本公司判斷模塊、地面空中判斷模塊，不可繼續(xù)剪枝，剩下1個模塊(b’)。第2次剪枝，雖然模塊(d)可以在圖4的子圖中找到，但是如果繼續(xù)對其剪枝，分成模塊(H)、(I)、(J)，在提高模塊(d)與圖2-3對應(yīng)子圖的相似性的同時，也會增加模塊(d)與所有子圖的相似性之和。第3次剪枝，對模塊(b’)進行再次剪枝，獲得模塊(B)、(C)，從而提高代表性之和，獲得具有通用性的模塊；當(dāng)開始第4次剪枝時，發(fā)現(xiàn)每個候選模塊與其同場景下對應(yīng)的子圖的相似性已經(jīng)達到1，因此無法繼續(xù)進行剪枝，最后選擇方案3作為最優(yōu)解f1=0，f2=34。

圖5 應(yīng)急響應(yīng)程序總圖G以其初始模塊情況

剪枝次數(shù)1234模塊數(shù)量8101111f1281200f221323434Δfn—0．04760．93750Δsimn?—(0，0．2275，0，0，0，0，0，0)(0，0，0．2546，0，0，0，0，0，0，0)(0，0，0，0，0，0，0，0，0，0，0)

*中的一組值(0,0.2275,0,0,0,0,0,0)為第二次剪枝與第一次剪枝相似性的對比，由于在第二次剪枝過程中，其中有1個模塊被劃分成3個模塊，因此三個模塊的平均相似性與原來的模塊計算相似性之和增量。

第3次剪枝次數(shù)對應(yīng)的模塊集合見圖6，分析圖中的模塊，沒有發(fā)現(xiàn)任何模塊違背模型中約束條件，即將同一條邊分給多個模塊，不同場景下的行動放在同一個模塊中；另外圖6中重復(fù)的節(jié)點為模塊的接口，例如，接口5被分配給5個模塊，接口6-11被分配給4個模塊，此措施增加了目標(biāo)f2。由于算例最優(yōu)解中已經(jīng)獲得具有特殊性的模塊B、D、F、I、J，因此在復(fù)原3個應(yīng)急響應(yīng)程序的時候，起落架故障應(yīng)急響應(yīng)程序根據(jù)相似性與功能調(diào)用了模塊(A、B、C、G、H、K)，輪胎故障應(yīng)急響應(yīng)程序調(diào)用模塊(A、C、D、E、H、K)，爆炸應(yīng)急響應(yīng)程序調(diào)用了模塊(A、C、D、E、F、G、H、I、J、K)，根據(jù)3個應(yīng)急響應(yīng)程序調(diào)用模塊情況復(fù)原后差異性都為0，因此差異性之和也為0。通過算例可以得知基于有向圖相似性的模型與啟發(fā)式算法在提取通用性模塊與特殊性模塊的有效性，且算法的計算復(fù)雜度低，計算速度快，可以為大規(guī)模的應(yīng)急響應(yīng)程序模塊化服務(wù)。

圖6 第3次剪枝次數(shù)對應(yīng)的模塊集合

5 結(jié)語

本文研究利用有向圖相似性的思路，通過對多個應(yīng)急響應(yīng)程序疊加的有向總圖進行分割，建立了多目標(biāo)數(shù)學(xué)模型，并設(shè)計啟發(fā)式算法對候選模塊的從粗到細進行了優(yōu)化，選取航空公司的作為算例，通過模塊化結(jié)果顯示，本文提出的數(shù)學(xué)模型與啟發(fā)式算法對多個應(yīng)急響應(yīng)程序的模塊化具有可行性，將具有通用性與特殊性的模塊都提取出來，并提供了模塊的接口。本文的貢獻在于，提出了應(yīng)急響應(yīng)程序模塊的有向圖相似性定義以及提取模塊的具體模型，形成了模塊，保留了模塊之間的接口，在一定程度上可以提高應(yīng)急管理的組織效率與應(yīng)急預(yù)案調(diào)整的速度，體現(xiàn)了模塊的即插即用性，可以為計算機輔助應(yīng)急管理提供基礎(chǔ)。

[1] 袁宏永,蘇國鋒,李藐.論應(yīng)急文本預(yù)案、數(shù)字預(yù)案與智能方案[ J] .中國應(yīng)急管理, 2007,(4):20-23.

[2] 劉磊,池宏,邵雪焱,等.預(yù)案管理中的重構(gòu)問題研究[C]. 第四屆國際應(yīng)急管理論壇暨中國(雙法)應(yīng)急管理專業(yè)委員會第五屆年會,北京,2009年12月12日-13日.

[3] 蔡冠華,黎偉.美國應(yīng)急預(yù)案體系研究及對我國的標(biāo)準化建議[J].質(zhì)量與標(biāo)準,2013,(7):42-45.

[4] 田軍,李莉芳,白劍,等.基于DSM的應(yīng)急任務(wù)流程模塊化設(shè)計研究[J].中國管理科學(xué),2014, 22(8):100- 107.

[5] 鄧婕,祁明亮,池宏,等.應(yīng)急預(yù)案響應(yīng)程序模塊化研究[J].運籌與管理, 2015, 24(5):132-143.

[6] 姜艷萍,樊治平,蘇明明.應(yīng)急決策方案的動態(tài)調(diào)整方法研究[J].中國管理科學(xué),2011,19(5):104-109.

[7] 王劍,羅東.基于BDN的突發(fā)事件多主體應(yīng)急決策模型研究[J].中國管理科學(xué),2015,23(S1):316-325.

[8] 榮莉莉,楊永俊.一種基于知識供需匹配的預(yù)案應(yīng)急能力評價方法[J].管理學(xué)報,2009,6(12):1643-1647.

[9] Liu lei, Chi Hong, Shao Xueyan, et al. A study on reconstruction problem in emergency plan management[C]// Proceedings of International Symposium on Emergency Management, Beijing, China,2009.

[10] GirardC,David P, PiatyszekE et al. Emergency response plan: Model-based assessment with multi-state degradation[J].Safety Science,2016，85:230-240.

[11] Turoffa M, Baulsb V, Plotnickc L,et al.A collaborative dynamic scenario model for the interaction of critical infrastructures[J]. Futures, 2016，84(Part A):23-42.

[12] Mendonc D, Beroggi G E G, van Gent D, et al. Designing gaming simulations for the assessment of group decision support systems in emergency response[J].Safety Science, 2006,44(6):523-535.

[13] Yoon S W,Velasquez J D,Partridge B K, et al.Transportation security decision support system for emergency response: A training prototype[J].Decision Support Systems,2008, 46(1):139-148.

[14] Koutra D, Parikh A,Parikh A,et al. Algorithms for graph similarity and subgraphmatching[R].Technical Report,2011.Carnegie Mellon University.

[15] Zelinka B. On a certain distance between isomorphism classes of graphs[J].Casopis Pest. Math.,100,(4): 371-373.

[16] Sobik F,Sommerfeld E. A graph theoretic approach to the characterization of classes of structured objects[J].Computers and Artificial Intelligence,1984,3: 235-247.

[17] Giugno R,Shasha D.Graphgrep: A fast and universal method for querying graphs[C]//Proceedings of International Cenferenee on Pattern Recognition,Quebec City,Canada,August 11-15,2002.

[18] Jeh G,Widom J. SimRank: A measure of structural-context similarity[C]// Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, Edmonton,Alberta,Canada,July 23-26,2002.

[19] Blondel V D, Gajardo A, Heymans M, et al. A measure of similarity between graph vertices: Applications to synonym extraction and web searching[J]. SIAM Review, 2004, 46(4), 647-666.

[20] Zager L A,Verghese G C. Graph similarity scoring and matching[J]. Applied Mathematics Letters, 2008.21(1):86-94.

[21] Bayati M,Gleich D F,Saberi A, et al. Message passing algorithms for sparse networkalignment[J]. 2013,7(11):1-31.

The Research on Emergency Response Procedures ModularityBased on the Similarity of Directed Graph

DENG Jie1,2, CHI Hong1,3, XU Bao-guang1,3

(1.Institute of Policy and Management, Chinese Academy of Sciences, Beijing 100190,China;2.Jiangnan University, School of Business, Wuxi 214122,China;3.School of Public Policy and Management,UCAS,Beijing 100049,China)

In very low-frequency,high-consequence emergency events, a group or individual’s prior experience will influence judgments and decision. Emergency response procedures play a guiding role when emergency accidents happen. Through analyzing multiple emergency response procedures, it is found that some actions repeatedly work together with a sequence, if those actions can be normalizedand fixed as a module, reaction time will be reduced and coordination will be improved, the generation of emergency modular will provide a suggestion for the same type of emergency accident on adjusting and emergency training. The purpose of this paper is to extract the commonality and particularity module from multiple emergency response procedures, firstly partition the general directed graphwhich is formed by superimposing multiple emergency response procedures, and determine therepresentative of candidate module by defining the similarity of the directed graph. Finally, a mathematical programming model whose goal is to minimum the sum of procedures’ difference and module’s interface is built. Then, by designing the heuristic algorithm, all edges of general directed graph are distributed to response procedure modules. Through analyzing the case, it is verified that this method can obtain the module with demand, and it provides a methodological basis for rapidly reconstruction and functional combination on emergency response procedures.

emergency management; the similarity of directed graph; response procedure module; modularity

2015-07-20；

2017-01-09

池宏(1960-)，男(漢族)，福建人，中國科學(xué)院科技政策與管理科學(xué)研究所，研究員，研究方向：應(yīng)急管理、安全管理、風(fēng)險管理和項目管理，E-mail：chihong@casipm.ac.cn.

1003-207(2017)04-0115-09

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

C931.1; O221.4

A