一種基于演化模型的應(yīng)急服務(wù)網(wǎng)絡(luò)優(yōu)化方法

鄧菊麗 王艷 陳國(guó)榮

(1. 重慶科技學(xué)院化學(xué)化工學(xué)院， 重慶 401331； 2. 重慶科技學(xué)院智能技術(shù)與工程學(xué)院， 重慶 401331)

0 前言

應(yīng)急管理是指政府及其他公共機(jī)構(gòu)在突發(fā)事件的事前預(yù)防、事發(fā)應(yīng)對(duì)、事中處置和事后善后恢復(fù)過(guò)程中，通過(guò)建立必要的應(yīng)對(duì)機(jī)制，采取一系列必要措施，應(yīng)用科學(xué)的技術(shù)規(guī)劃與管理等手段，保障公眾生命、健康和財(cái)產(chǎn)安全，促進(jìn)社會(huì)和諧健康發(fā)展的有關(guān)活動(dòng)。由于應(yīng)急網(wǎng)絡(luò)規(guī)劃布局不夠合理，我國(guó)現(xiàn)有的應(yīng)急服務(wù)中心和應(yīng)急物流基地，服務(wù)效率并不高。同時(shí)，盲目投資興建各種功能大而全的應(yīng)急服務(wù)基地的情況還時(shí)有發(fā)生，造成社會(huì)資源的浪費(fèi)。我們應(yīng)該從全局的角度規(guī)劃應(yīng)急服務(wù)網(wǎng)絡(luò)的布局，避免社會(huì)資源的浪費(fèi)，提高應(yīng)急救援效率和事故應(yīng)對(duì)效率。關(guān)于應(yīng)急服務(wù)網(wǎng)絡(luò)規(guī)劃和建設(shè)，學(xué)者們主要從應(yīng)急服務(wù)網(wǎng)絡(luò)建模和服務(wù)基地的選擇等方面作了研究。

(1) 應(yīng)急服務(wù)網(wǎng)絡(luò)建模方面的研究。趙林度等人構(gòu)建了基于彈性的城際重大危險(xiǎn)源應(yīng)急網(wǎng)絡(luò)協(xié)同機(jī)制，并分別從風(fēng)險(xiǎn)彈性、信息彈性、資源彈性的角度對(duì)城際應(yīng)急網(wǎng)絡(luò)的協(xié)同彈性水平進(jìn)行了研究[1]。宋琪通過(guò)對(duì)地震應(yīng)急協(xié)同物流網(wǎng)絡(luò)進(jìn)行復(fù)雜系統(tǒng)分析，建立了多Agent模型結(jié)構(gòu)及Agent交互規(guī)則[2]。陳濤等人以北京為例，開展了城市運(yùn)行與應(yīng)急管理技術(shù)架構(gòu)與應(yīng)用模式研究，提出城市運(yùn)行和應(yīng)急管理融合的技術(shù)框架[3]。李陽(yáng)研究了面向城市應(yīng)急管理的情報(bào)能力建設(shè)問(wèn)題[4]。

(2) 應(yīng)急服務(wù)基地的選擇方面的研究。陳國(guó)榮等人基于對(duì)應(yīng)急物流的研究，提出了一種基于成長(zhǎng)的物流網(wǎng)絡(luò)建模方法[5]。鄭斌等人以汶川大地震應(yīng)急物資配送為背景，設(shè)計(jì)了一種震后應(yīng)急物流動(dòng)態(tài)選址-聯(lián)運(yùn)問(wèn)題的雙層規(guī)劃模型[6]。王沛等人結(jié)合商品車運(yùn)輸“庫(kù)前移”模式的運(yùn)作特點(diǎn)，開展了基于“庫(kù)前移”模式的鐵路商品車物流基地分層動(dòng)態(tài)選址優(yōu)化研究[7]。劉潔研究了鐵路乘用車物流基地作業(yè)區(qū)布局優(yōu)化研究[8]。

上述方法的不足之處是，對(duì)于網(wǎng)絡(luò)的規(guī)劃和研究基本上停留在應(yīng)急服務(wù)基地結(jié)點(diǎn)數(shù)量和應(yīng)急網(wǎng)絡(luò)連接保持固定不變的狀態(tài)，不能適應(yīng)網(wǎng)絡(luò)規(guī)模不斷成長(zhǎng)和網(wǎng)絡(luò)結(jié)構(gòu)變化的趨勢(shì)。文獻(xiàn)[5]中提出了一種基于成長(zhǎng)的物流網(wǎng)絡(luò)建模方法NGM(Nodes Growing Model)，解決了應(yīng)急物流網(wǎng)絡(luò)成長(zhǎng)過(guò)程的建模問(wèn)題。

本次研究是在文獻(xiàn)[5]的基礎(chǔ)上，通過(guò)施加一定的擾動(dòng)，使網(wǎng)絡(luò)產(chǎn)生形變，從而得到一種新的演化效果。通過(guò)比較演化情形，從中獲取一種較優(yōu)的應(yīng)急服務(wù)網(wǎng)絡(luò)效果，以實(shí)現(xiàn)網(wǎng)絡(luò)的最優(yōu)控制。

1 應(yīng)急服務(wù)網(wǎng)絡(luò)的演化模型

考慮應(yīng)急服務(wù)網(wǎng)絡(luò)的實(shí)際情況，假定所研究的網(wǎng)絡(luò)不存在結(jié)點(diǎn)自身到自身的連接，也不存在2個(gè)結(jié)點(diǎn)之間的重復(fù)連接。另外，本次研究中對(duì)邊的刪除只是基于網(wǎng)絡(luò)圖的正常演化過(guò)程，不考慮網(wǎng)絡(luò)圖的突變。

1.1 基于優(yōu)先連接和賦權(quán)邊的結(jié)點(diǎn)增長(zhǎng)模型

結(jié)點(diǎn)的增長(zhǎng)參考了文獻(xiàn)[5]中提出的成長(zhǎng)模型，算法如下：

(1) 產(chǎn)生第1個(gè)結(jié)點(diǎn)。根據(jù)產(chǎn)業(yè)需求建設(shè)第一個(gè)應(yīng)急服務(wù)基地，并將其作為網(wǎng)絡(luò)第一個(gè)結(jié)點(diǎn)和起點(diǎn)。

(2) 產(chǎn)生第2個(gè)結(jié)點(diǎn)。由于更多應(yīng)急服務(wù)需求的增加，決定在該地建立新的應(yīng)急服務(wù)結(jié)點(diǎn)，兩個(gè)結(jié)點(diǎn)之間用一條邊連接起來(lái)。

(3) 隨機(jī)化增加結(jié)點(diǎn)。異地應(yīng)急服務(wù)需求的進(jìn)一步增加，產(chǎn)生更多的結(jié)點(diǎn)。

(4) 基于優(yōu)先序和賦權(quán)邊的網(wǎng)絡(luò)連接，新結(jié)點(diǎn)與已知結(jié)點(diǎn)i通過(guò)帶權(quán)的路徑相連接的概率Pi、結(jié)點(diǎn)i的度ki、權(quán)重ri之間滿足式(1)：

(1)

其中

新結(jié)點(diǎn)與原有網(wǎng)絡(luò)中結(jié)點(diǎn)，按照Pi從大到小的順序連接；t為結(jié)點(diǎn)度和邊的權(quán)重調(diào)節(jié)參數(shù)，0≤t≤1，其值取決于實(shí)際網(wǎng)絡(luò)的具體需求。權(quán)重越大，該路徑在網(wǎng)絡(luò)中的重要度、兩結(jié)點(diǎn)的相關(guān)度、被選擇連接的可能性就越大。

上述算法構(gòu)造的網(wǎng)絡(luò)成長(zhǎng)過(guò)程如圖1所示，其成長(zhǎng)網(wǎng)絡(luò)度分布服從式(2)規(guī)律：

P(k，r，t) ∝2n2(ktr1-t)-3

(2)

式中：n為網(wǎng)絡(luò)結(jié)點(diǎn)的總數(shù)；k為結(jié)點(diǎn)的度；r為邊的權(quán)重。

圖1所示為向有19個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中增加1個(gè)結(jié)點(diǎn)的情況。其中，應(yīng)急服務(wù)網(wǎng)絡(luò)具有冪率特性，按照指數(shù)規(guī)律進(jìn)行成長(zhǎng)。需要討論的是，這種成長(zhǎng)方式是否是我們需要的，以及應(yīng)該從哪些方面進(jìn)行優(yōu)化。

1.2 增長(zhǎng)型演化過(guò)程的加邊效應(yīng)

定義1：當(dāng)圖G中的任意兩結(jié)點(diǎn)i和j之間需要增加新的連接邊時(shí)，必須考慮擇優(yōu)原則，即新增加的連接邊必須使得網(wǎng)絡(luò)圖中任何兩結(jié)點(diǎn)之間的距離更短。

圖1 向有19個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中增加1個(gè)結(jié)點(diǎn)

網(wǎng)絡(luò)中各結(jié)點(diǎn)的度分布如式(3)所示：

K=[k1，k2，…，kn]

(3)

網(wǎng)絡(luò)中結(jié)點(diǎn)之間的距離dui如式(4)所示：

(4)

且

(5)

忽略結(jié)點(diǎn)本身對(duì)邊權(quán)重的影響，并假定邊的成本為權(quán)重的倒數(shù)。在定義1的基礎(chǔ)上，如果網(wǎng)絡(luò)圖G中的結(jié)點(diǎn)u需要增加一條邊，并給定了新增連接邊的邊權(quán)重r，則由式(1)得式(6)和式(7)：

(6)

Pa=max{Pui}，(0

(7)

因此，邊的增長(zhǎng)過(guò)程如下：

(1) 確定需要增加邊的結(jié)點(diǎn)u。

(2)計(jì)算網(wǎng)絡(luò)中各結(jié)點(diǎn)到結(jié)點(diǎn)u的距離dui。

(3)按照式(6)計(jì)算并確定與結(jié)點(diǎn)u相連的max{Pui}，(0

(4) 比較rui和r的關(guān)系，考查有無(wú)增加連接邊eui的必要。如果rui>r，則結(jié)點(diǎn)u和結(jié)點(diǎn)i之間的連線eui即為網(wǎng)絡(luò)圖中新增加的邊，且增加新邊后的網(wǎng)絡(luò)圖的度分布為：K=[k1，k2，(ki+1) ，…，(ku+1)，kn]。如果rui≤r，即新增邊的重要度不夠，則增加新邊不能對(duì)網(wǎng)絡(luò)產(chǎn)生優(yōu)化效果，因而沒(méi)有必要增加這一條重要度為r的邊。

(5)如果結(jié)點(diǎn)u和結(jié)點(diǎn)i之間出現(xiàn)重邊，則刪除邊eui。

基于上述步驟，對(duì)結(jié)點(diǎn)C17增加邊，如圖2所示。

1.3 蛻化型演化過(guò)程

定義2：當(dāng)圖G中的任意兩結(jié)點(diǎn)i和j之間需要?jiǎng)h除連接邊時(shí)，必須考慮擇劣原則，即每次被刪除的邊的重要度對(duì)于給定結(jié)點(diǎn)rij為最低。

本次研究中，對(duì)于邊的刪除不考慮網(wǎng)絡(luò)圖的突變，而是僅基于網(wǎng)絡(luò)圖的正常演化過(guò)程。從定義2可看出，刪除邊與增加邊的計(jì)算過(guò)程相同，只是邊eui所對(duì)應(yīng)的結(jié)點(diǎn)u和結(jié)點(diǎn)i的連接概率Pd由概率矩陣集合中的最小值min{Pui} 確定，即

Pd=min{Pui}，(0

(8)

綜上所述，邊的刪除過(guò)程如下：

(1)確定需要?jiǎng)h除邊的結(jié)點(diǎn)u。

(2)計(jì)算網(wǎng)絡(luò)中各結(jié)點(diǎn)到結(jié)點(diǎn)u的距離dui。

(3)按照式(6)計(jì)算并確定與結(jié)點(diǎn)u相連的Pd。

(4)刪除連接概率Pd對(duì)應(yīng)的邊eui，更新結(jié)點(diǎn)度的集合K=[k1，k2，(ki-1) ，…，(ku-1) ，kn]。

(5)如果刪除eui后出現(xiàn)孤點(diǎn)，則將相應(yīng)的結(jié)點(diǎn)一并刪除，并更新結(jié)點(diǎn)的集合和結(jié)點(diǎn)總數(shù)n。

基于上述步驟，刪除結(jié)點(diǎn)C19與C2之間的連接邊，如圖3所示。

圖3 對(duì)結(jié)點(diǎn)C19刪除邊的過(guò)程

1.4 平衡演化過(guò)程

前面著重強(qiáng)調(diào)了結(jié)點(diǎn)增長(zhǎng)型演化過(guò)程和結(jié)點(diǎn)蛻化型演化過(guò)程。但在實(shí)際情況下，不斷有新的結(jié)點(diǎn)加入現(xiàn)有的應(yīng)急服務(wù)網(wǎng)絡(luò)，也不斷有舊結(jié)點(diǎn)蛻化和消失，因而整個(gè)網(wǎng)絡(luò)在不斷發(fā)生動(dòng)態(tài)變化。很明顯，應(yīng)急服務(wù)網(wǎng)絡(luò)滿足耗散結(jié)構(gòu)體的基本特性，因而具有耗散結(jié)構(gòu)的相關(guān)特性。即，網(wǎng)絡(luò)的平衡屬于動(dòng)態(tài)平衡，需要外界的輸入和輸出予以供養(yǎng)。

為了判斷網(wǎng)絡(luò)是否達(dá)到平衡，下面定義結(jié)點(diǎn)的熵變dA。

定義3：對(duì)于給定的結(jié)點(diǎn)，如果市場(chǎng)需求變化為dD，結(jié)點(diǎn)所能供給的需求變化為dS，則該結(jié)點(diǎn)的熵變dA可通過(guò)式(9)來(lái)計(jì)算：

dA=dS-dD

(9)

定義3表明，熵變dA是網(wǎng)絡(luò)與外界之間進(jìn)行物質(zhì)和能量交換的結(jié)果。其中，dD為市場(chǎng)的需求變化，可正可負(fù)。如果dD為正，表示應(yīng)急服務(wù)需求呈增長(zhǎng)態(tài)勢(shì)；反之，如果dD為負(fù)，表示應(yīng)急服務(wù)需求可能萎縮。dS為結(jié)點(diǎn)的供給能力，對(duì)于一個(gè)給定的結(jié)點(diǎn)來(lái)說(shuō)，其能力有一個(gè)最大限值dSmax，超出此限值時(shí)給定結(jié)點(diǎn)將無(wú)法滿足市場(chǎng)的需要；然而，如果市場(chǎng)需求遠(yuǎn)不能滿足該結(jié)點(diǎn)的能力，由于成本等因素的影響，可能會(huì)運(yùn)行不下去。

上述結(jié)果最終表現(xiàn)在熵變dA上。一方面，如果dA>0，意味著網(wǎng)絡(luò)具有較好的增長(zhǎng)動(dòng)力；且當(dāng)dA?0時(shí)，結(jié)點(diǎn)很有可能發(fā)生突變，產(chǎn)生新結(jié)點(diǎn)和新邊。另一方面，如果熵變dA<0，說(shuō)明該結(jié)點(diǎn)無(wú)法達(dá)到預(yù)定的運(yùn)行效果；且當(dāng)dA?0時(shí)，結(jié)點(diǎn)及其相應(yīng)的邊入不敷出，進(jìn)入蛻化程序在所難免。

2 仿真實(shí)驗(yàn)分析

為了驗(yàn)證本應(yīng)急服務(wù)網(wǎng)絡(luò)建模方法的正確性，我們建立了一個(gè)實(shí)驗(yàn)網(wǎng)絡(luò)模型?？紤]結(jié)點(diǎn)增長(zhǎng)效應(yīng)，向結(jié)點(diǎn)數(shù)為19的網(wǎng)絡(luò)中增加1個(gè)新結(jié)點(diǎn)，即第20個(gè)結(jié)點(diǎn)，其有關(guān)數(shù)據(jù)如表1所示。表1中，R為新增結(jié)點(diǎn)邊權(quán)重；K19為結(jié)點(diǎn)C19的度；Kr為基于邊權(quán)重的演化網(wǎng)絡(luò)；Kk為基于結(jié)點(diǎn)的度的演化網(wǎng)絡(luò)數(shù)；Kr，k為基于邊權(quán)重和結(jié)點(diǎn)度的演化網(wǎng)絡(luò)數(shù)；Pr為基于邊權(quán)重的演化網(wǎng)絡(luò)加邊概率；Pk為基于結(jié)點(diǎn)度的演化網(wǎng)絡(luò)加邊概率；Pr，k為基于邊權(quán)重和結(jié)點(diǎn)度的加邊概率；Cr為基于邊的聚類系數(shù)；Ck為基于結(jié)點(diǎn)的聚類系數(shù)；Cr，k為綜合聚類系數(shù)。

由表1中的數(shù)據(jù)以及式(2)可知：賦權(quán)化的網(wǎng)絡(luò)度分布為冪指數(shù)方程，因而該模型建立的網(wǎng)絡(luò)屬于冪律分布網(wǎng)絡(luò)。

由式(1)和(2)可知，盡管新結(jié)點(diǎn)的連接傾向于選擇“富”結(jié)點(diǎn)，但由于邊權(quán)重因素的影響，優(yōu)先連接的現(xiàn)象也非常普遍。當(dāng)t= 0時(shí)，結(jié)點(diǎn)的度無(wú)關(guān)緊要，起決定作用的是邊的權(quán)重；當(dāng)t=1時(shí)，網(wǎng)絡(luò)中結(jié)點(diǎn)的重要性完全取決于結(jié)點(diǎn)的度；當(dāng) 0

表1 第20個(gè)結(jié)點(diǎn)后參數(shù)值的變化情況

注：加背景底紋的數(shù)值表示該列極大值，即具有優(yōu)先連接特性的結(jié)點(diǎn)；帶“*”數(shù)字為該列極小值，即優(yōu)先退化邊

根據(jù)定義2所述的擇優(yōu)加邊原則，與結(jié)點(diǎn)u相連接的結(jié)點(diǎn)i的概率Pa，由概率矩陣集合中的最大值max{Pui}，(0r，結(jié)點(diǎn)u和結(jié)點(diǎn)i之間的連線eui即為網(wǎng)絡(luò)圖中新增加的邊，且增加新邊后的網(wǎng)絡(luò)圖的度分布為：K=[k1，k2，(ki+1) ，…，(ku+1) ，kn]；如果rui≤r，則新增加的邊的重要度不夠，表明增加新邊不能對(duì)網(wǎng)絡(luò)產(chǎn)生優(yōu)化效果，因而沒(méi)有必要增加這一條重要度為r的邊。由于式(6)與式(1)一樣，都考慮了邊的權(quán)重和結(jié)點(diǎn)的度，因此，增加新邊后網(wǎng)絡(luò)的結(jié)構(gòu)仍然保持為層次結(jié)構(gòu)?？紤]加邊效應(yīng)，在選擇結(jié)點(diǎn)時(shí)，選擇結(jié)點(diǎn)C5的可能性最大(見圖2)。

根據(jù)定義2所述的擇劣刪邊原則，與結(jié)點(diǎn)u相連接的結(jié)點(diǎn)i的概率Pa，由概率矩陣集合中的最小值min{Pui}，(0

定義3考慮了市場(chǎng)的需求和網(wǎng)絡(luò)結(jié)點(diǎn)的供給能力，給出了網(wǎng)絡(luò)增長(zhǎng)和蛻化的動(dòng)力，因而對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)不會(huì)產(chǎn)生破壞作用。

3 結(jié) 語(yǔ)

針對(duì)應(yīng)急服務(wù)網(wǎng)絡(luò)的發(fā)展規(guī)律，提出了應(yīng)急服務(wù)網(wǎng)絡(luò)的演化模型：

(1) 對(duì)于結(jié)點(diǎn)的增長(zhǎng)過(guò)程，提出了應(yīng)急服務(wù)網(wǎng)絡(luò)的成長(zhǎng)模型，給出了定量和定性的計(jì)算方法和結(jié)點(diǎn)增長(zhǎng)步驟。

(2) 對(duì)于邊的增加，推導(dǎo)了基于擇優(yōu)原則的邊增長(zhǎng)定量計(jì)算方法。

(3) 考慮到邊和結(jié)點(diǎn)的刪除情況，給出了基于擇劣原則的邊和結(jié)點(diǎn)的刪除過(guò)程。

(4) 考慮網(wǎng)絡(luò)的平衡演化過(guò)程，建立了網(wǎng)絡(luò)的耗散結(jié)構(gòu)模型。

對(duì)上述方法進(jìn)行仿真，結(jié)果表明該建模方法符合應(yīng)急服務(wù)網(wǎng)絡(luò)的實(shí)際情況，邊和結(jié)點(diǎn)的變動(dòng)不會(huì)影響應(yīng)急服務(wù)網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定發(fā)展。