張岳峰，何建敏，孫 艷，劉向東

（東南大學(xué) 經(jīng)濟管理學(xué)院，南京 211189）

0 引言

隨著現(xiàn)代經(jīng)濟的迅猛發(fā)展，高節(jié)奏的社會生活以及突發(fā)事件的日益增多使社會安全承受著前所未有的挑戰(zhàn)[1]。針對一些突如其來的緊急事件，若能及時采取應(yīng)急措施就能盡量避免不必要的人員傷亡和經(jīng)濟損失。然而在這些措施中，最為關(guān)鍵的就是要求制定適當(dāng)、有效的調(diào)度方案使所需資源盡快到達(dá)應(yīng)急地點，以輔助應(yīng)急活動的盡早進(jìn)行[2]。方磊等[3][4]在考慮應(yīng)急系統(tǒng)時間緊迫性的前提下，提出基于系統(tǒng)的費用最小的選址模型和應(yīng)急限制期下的應(yīng)急選址模型。汪定偉等[5]提出一種基于災(zāi)害發(fā)生概率、災(zāi)害擴散函數(shù)和救援函數(shù)的救援中心選址優(yōu)化的數(shù)學(xué)模型，并用嵌入啟發(fā)式遺傳算法求解。Ceyhun[6]等人提出一種多目標(biāo)基于應(yīng)急車輛—位置覆蓋模型，以行程最短為優(yōu)化目標(biāo)，為提高后備服務(wù)水平盡可能讓一輛車服務(wù)更多節(jié)點。林興強等[7]把路網(wǎng)可靠性概念引入到車輛路徑問題中，建立基于行程時間可靠性的車輛優(yōu)化調(diào)度模型。孫燕、陳森發(fā)等[8]利用層次分析法和灰色系統(tǒng)理論提出一種可用于車載系統(tǒng)的根據(jù)駕駛員的偏好(要求)選擇最優(yōu)路徑的方法。劉春林等[9][10]提出基于“時間最短”、“出救點數(shù)目最少”的多目標(biāo)數(shù)學(xué)模型。針對應(yīng)急系統(tǒng)的特點，何建敏等[11]研究了基于單目標(biāo)、多目標(biāo)、兩階段問題且有資源數(shù)量約束的組合優(yōu)化模型及快速求解算法。可見，不少學(xué)者已經(jīng)從應(yīng)急資源地域分布、出救路線選擇、應(yīng)急時間最短或出救點最少等方面作為目標(biāo)分別進(jìn)行了研究。

然而，應(yīng)急資源的調(diào)度問題常常需要考慮的因數(shù)和目標(biāo)往往不止一個。盡管也有部分學(xué)者考慮到了多目標(biāo)規(guī)劃，但一般都沒有考慮應(yīng)急調(diào)度的成本問題。藉此，本文將以連續(xù)性消耗應(yīng)急系統(tǒng)為背景探討路徑時間為隨機數(shù)時應(yīng)急資源調(diào)度的優(yōu)化問題。首先，從交通工具通過道路的時間變化可能性進(jìn)行闡述，采用正態(tài)分布隨機變量刻畫路段通行時間的不確定性，并建立道路時間隨機條件下時間滿意度最大和路徑費用最小的多目標(biāo)資源調(diào)度模型。其次，對蟻群算法進(jìn)行改進(jìn)，求解模型的非劣解集，并采用TOPSIS方法得到最優(yōu)解；最后，通過算例驗證模型和算法的可行性和有效性。

1 問題描述與模型建立

就一般的交通路網(wǎng)而言，可以采用圖論中的賦權(quán)圖G（或有向圖，當(dāng)存在單行道等情況時）進(jìn)行簡化，將路的端點或者路和路的交叉點用頂點集V(G)表示，相應(yīng)的路用邊集E(G)來表示，邊e∈E(G)上的權(quán)重集W(G)|(w1,w2)表示通過這條路所需的時間w1和費用w2。那么，該問題就化解為從出救點到事發(fā)點的最優(yōu)路徑P*，使得

為了使模型更好地適應(yīng)現(xiàn)實交通工具的運行情況，假設(shè)所有路段的通行時間都是服從正態(tài)分布的，并且路段與路段之間的通行時間相互獨立。設(shè)μ為通過該路段所需時間的均值，σ為標(biāo)準(zhǔn)差，根據(jù)經(jīng)典的正態(tài)分布3σ原則，將原來取值于[-∞,+∞]的正態(tài)分布隨機變量限制在[μ-3σ,μ+3σ](μ-3σ＞0)中。由此可以求解置信度為99.7%的最大滿意路徑。根據(jù)相互獨立的正態(tài)分布的可加性和區(qū)間數(shù)的加法法則，整個路徑P的通行時間也是一個服從正態(tài)分布的區(qū)間數(shù)。

設(shè)網(wǎng)絡(luò)G中任意一條邊e的時間權(quán)重為[μ(e)-3σ(e),μ(e)+3σ(e)]，則對 于 任 意 一 條 路 徑P，其 時間權(quán)重也是區(qū)間數(shù)

由于[μ-3σ,μ+3σ]是服從正態(tài)分布的區(qū)間數(shù)，其密度函數(shù)為：

在網(wǎng)絡(luò)優(yōu)化中，若只考慮兩點之間的最短路徑問題，便轉(zhuǎn)化成最小費用流問題的特殊情形。一般的最小費用流可以寫成線性規(guī)劃的形式，即：

其中，cij表示邊(i,j)上單位流量的費用，第一個約束表示從vs流出的凈流量為f，第二個約束表示從vd流出的凈流量為-f，第三個約束表示除了源點vs和匯點vd外其它點必須遵循流量守恒，第四個約束表示邊(i,j)上的流量是非負(fù)的并且在容量uij限制內(nèi)。只要在最小費用流模型下作如下假設(shè)：

（1）vs作為源點凈流出量為1，vd作為匯點凈流出量為-1，其它點的凈流出量為0；

（2）當(dāng)網(wǎng)絡(luò)中任意兩節(jié)點存在連接邊時，邊上的單位流量費用等于邊權(quán)的值；當(dāng)任意兩節(jié)點不存在連接邊時，邊上的單位流量費用等于一個很大的常數(shù)；

（3）各邊的容量無限制。

這樣，對于上述最小費用流問題實質(zhì)上可以轉(zhuǎn)化為一個整數(shù)線性規(guī)劃的形式，即：

定義 1 設(shè)M=[μ-3σ,μ+3σ]是服從正態(tài)分布的區(qū)間數(shù)，c為給定的實數(shù)，M小于等于c的可能度定義為：

定義2如果邊e上的通行時間取左端點μ(e)-3σ(e)，在最小費用流模型中即邊e上的費用取左端點，以此求得的最小費用流稱為樂觀最小費用流。

定義3如果邊e上的通行時間取右端點μ(e)+3σ(e)，在最小費用流模型中即邊e上的費用取右端點，以此求得的最小費用流稱為保守最小費用流。

定義4對于給定的費用c，最小費用流值F小于等于c的滿意度H(F≤c)定義為T({M≤c})。

顯然，滿意度函數(shù)具有以下性質(zhì)：

（1）0≤H(F,c)≤1

（2）如果保守最小費用流值小于給定費用c，即：

則H(F0,c)=1，F(xiàn)0即最大滿意最小費用流。

（3）如果樂觀最小費用流值大于給定費用c，即：

則H(F0,c)=0，無最大滿意最小費用流。

最后整個問題的模型可以簡化為：

2 基于蟻群算法的模型求解方法

標(biāo)準(zhǔn)的蟻群算法主要是解決TSP（旅行商問題）的，在此基礎(chǔ)上許多學(xué)者將其進(jìn)行改進(jìn)，使其適用于VRP（車輛路徑問題）。這兩類問題的相同之處在于旅行商或車輛在網(wǎng)絡(luò)中的某一點出發(fā)，最后又回到該點；不同之處在于，旅行商需要經(jīng)過網(wǎng)絡(luò)的所有節(jié)點，而車輛只需要到達(dá)固定的幾個客戶點。而資源調(diào)度問題只考慮運載工具從出救點到事發(fā)點的調(diào)度問題，如何從事發(fā)點回到出救點不在該問題的討論范圍之內(nèi)。因此本文從以下幾個方面對蟻群算法進(jìn)行改進(jìn)，使該算法適合多目標(biāo)的資源調(diào)度問題。

在給出多目標(biāo)資源調(diào)度模型的蟻群算法之前，首先對以下符號進(jìn)行定義：

o為目標(biāo)，取值為1或2，表示時間或費用；

m為螞蟻個數(shù)；

s為出救點；

d為事件爆發(fā)點；

Nk為螞蟻k當(dāng)前的可行集；

NCmax為蟻群算法循環(huán)最大次數(shù)；

為以目標(biāo)為o的蟻群中螞蟻k的行走路徑；為目標(biāo)o的邊弧(i,j)權(quán)重；

為對于目標(biāo)o而言，邊弧(i,j)的能見度(visibility)，即

τij為邊弧(i,j)的軌跡強度（intensity）；

式中Q表示螞蟻所留的信息素大小，為一個常數(shù)。

由此可以得到軌跡強度更新的方法：

式中ρ表示軌跡的持久度；

式中，α是軌跡強度的相對重要性；β是能見度的相對重要性。

為了適應(yīng)該模型的求解，還需要對蟻群算法的過程進(jìn)行調(diào)整。

（1）螞蟻可行集的設(shè)置

螞蟻可行集是指螞蟻下一步所有可以行徑的節(jié)點。若螞蟻k在節(jié)點i處時，則定義該螞蟻的可行集為Nk(i)，它是節(jié)點i的所有后繼節(jié)點集合。設(shè)集合(i)為螞蟻k關(guān)于目標(biāo)o（時間或費用）到達(dá)i點時的行走路徑，那么：

（2）目標(biāo)函數(shù)的調(diào)整

在確定情況下，問題求解的一個目標(biāo)是時間最短。而當(dāng)前該目標(biāo)變?yōu)闈M意度最大。因此算法的的需要改成滿意度。

（3）信息素增加值的調(diào)整

（4）螞蟻進(jìn)行下一節(jié)點選擇時，能見度的相對重要性應(yīng)當(dāng)適當(dāng)減少。因為問題的目標(biāo)不是一次運行的時間最短問題，而是要求所有可行解中時間滿意度最大。

根據(jù)以上的改進(jìn)，考慮到應(yīng)急調(diào)度中時間因數(shù)的重要性，設(shè)計算法時讓以時間為目標(biāo)的螞蟻群先走。因此設(shè)計算法如下。

輸入?yún)?shù)：α，β，ρ，m，Q，s，d，NCmax

步驟1：初始化參數(shù)nc←1；

步驟2：若nc＞NCmax，轉(zhuǎn)步驟8；否則，令nc←nc+1，={s}，o←1，k←1，轉(zhuǎn)步驟3；

步驟3：若o＞2，更新信息素，轉(zhuǎn)步驟2；否則令k←1，轉(zhuǎn)步驟4；

步驟4：若k＞m，根據(jù)m次循環(huán)后得到的所有目標(biāo)函數(shù)值更新解集，并令o←o+1，轉(zhuǎn)步驟3；否則令k←k+1，轉(zhuǎn)步驟5；

步驟5：根據(jù)和更新集合Nk。若Nk=Φ，宣布螞蟻k死亡，轉(zhuǎn)步驟4；否則轉(zhuǎn)步驟6；

步驟6：根據(jù)和蒙特卡洛方法在集合Nk中選中節(jié)點i；

步驟8：刪除解集中的劣勢解，輸出解集；算法結(jié)束。

在得到方案的非劣解集后，還需要對方案進(jìn)行排序選擇其中的最優(yōu)方案。本文采用TOPSIS方法來確定最優(yōu)方案：設(shè)由蟻群算法得到?jīng)Q策矩陣為[X,Y]，其中X=(xi)'；Y=(yi)'；i=1,2,...,m。X表示時間滿意度，Y表示費用，即共有m對非劣方案。

（1）無量綱化

（2）確定最優(yōu)值與最劣值

（3）計算歐氏距離

（4）計算接近度

（5）選取最優(yōu)方案

選擇Ci最大的作為非劣解集中的最優(yōu)方案。

3 算例分析

圖1 時間為正態(tài)分布隨機數(shù)時的城市網(wǎng)絡(luò)

時間為正態(tài)分布隨機數(shù)時的網(wǎng)絡(luò)見圖1，由此可以得到路徑上時間的上限、下限和費用矩陣。令t=180,m=60，NCmax=50,α=0.5,β=1,ρ=0.9,Q=1。采用蟻群算法非劣解見表1。

表1 非劣解集

由此可以得到?jīng)Q策矩陣：

采用TOPSIS方法，可以得到目標(biāo)集合（0.9182，93）最優(yōu)，即在該環(huán)境下選擇路徑1-＞4-＞9-＞11-＞14-＞13-＞15是最優(yōu)的。

4 總結(jié)

本文討論了在路徑時間為正態(tài)分布的隨機數(shù)條件下，應(yīng)急資源的多目標(biāo)調(diào)度問題。主要從以下幾個方面進(jìn)行了研究：（1）考慮到交通工具通過某條道路所消耗的時間是變化的，因此采用正態(tài)分布的隨機數(shù)刻畫調(diào)度時間的不確定性，并建立時間滿意度最大和路徑費用最低的多目標(biāo)應(yīng)急資源調(diào)度模型；（2）設(shè)計多目標(biāo)的蟻群算法，求解路徑時間隨機的條件下，多目標(biāo)的應(yīng)急資源調(diào)度模型的非劣解集，并通過TOPSIS方法對蟻群算法得到的方案集進(jìn)行選優(yōu)。（3）通過算例驗證了模型和算法的可行性和有效性。具有一定的實際運用意義，當(dāng)還需要考慮其它目標(biāo)，只要將該目標(biāo)轉(zhuǎn)換成網(wǎng)絡(luò)上權(quán)重，整合進(jìn)目標(biāo)函數(shù),并增加一組螞蟻種群便可以進(jìn)行求解。本文的研究和結(jié)論也多目標(biāo)應(yīng)急調(diào)度優(yōu)化問題提供了進(jìn)一步研究的思路。

[1]Choi S O.Relative Efficiency of Fire and Emergency Services in Florida:an Application and Test of Data Envel Opment Analysis[J].International Journal of Emergency Management，2005,2(3).

[2]潘郁,余佳,達(dá)慶利.基于粒子群算法的連續(xù)性消耗應(yīng)急資源調(diào)度[J].系統(tǒng)工程學(xué)報，2007,22(005).

[3]方磊，何建敏.應(yīng)急系統(tǒng)優(yōu)化選址的模型及其算法[J].系統(tǒng)工程學(xué)報，2003,18(1).

[4]方磊，何建敏.城市應(yīng)急系統(tǒng)優(yōu)化選址決策模型和算法[J].管理科學(xué)學(xué)報，2005,8(1).

[5]汪定偉，張國祥.突發(fā)性災(zāi)害救援中心選址優(yōu)化的模型與算法[J].東北大學(xué)學(xué)報（自然科學(xué)版），2005,26(10).

[6]Ceyhun A H S I.Fuzzy Mufti-objective Covering-based Vehicle Location Model for Emergency Services[J].Computer&Operational Research，2007,34(3).

[7]林興強，陳馳，陳景新，任愛珠.基于行程時間可靠性的車輛優(yōu)化調(diào)度[J].交通運輸系統(tǒng)工程與信息，2005,5(5).

[8]孫燕，陳森發(fā)，亓霞，黃昆鳥.基于灰色系統(tǒng)理論的最優(yōu)路徑選擇方法[J].土木工程學(xué)報，2003,36(1).

[9]劉春林，何建敏，盛昭瀚.應(yīng)急系統(tǒng)調(diào)度問題的模糊規(guī)劃方法[J].系統(tǒng)工程學(xué)報，1999,14(4).

[10]劉春林，沈厚才.一類離散應(yīng)急供應(yīng)系統(tǒng)的兩目標(biāo)優(yōu)化模型[J].中國管理科學(xué)，2003,11(4).

[11]何建敏，劉春林，尤海燕.應(yīng)急系統(tǒng)多出救點的選擇問題[J].系統(tǒng)工程理論與實踐，2001,(11).