蟻群算法求解路徑時(shí)間隨機(jī)的應(yīng)急資源調(diào)度問題研究

張?jiān)婪?，何建敏，孫 艷，劉向東

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

0 引言

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

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

1 問題描述與模型建立

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最后整個(gè)問題的模型可以簡(jiǎn)化為：

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

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

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

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

m為螞蟻個(gè)數(shù)；

s為出救點(diǎn)；

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

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

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

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

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

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

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

由此可以得到軌跡強(qiáng)度更新的方法：

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

式中，α是軌跡強(qiáng)度的相對(duì)重要性；β是能見度的相對(duì)重要性。

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

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

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

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

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

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

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

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

輸入?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é)點(diǎn)i；

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

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

（1）無量綱化

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

（3）計(jì)算歐氏距離

（4）計(jì)算接近度

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

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

3 算例分析

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

時(shí)間為正態(tài)分布隨機(jī)數(shù)時(shí)的網(wǎng)絡(luò)見圖1，由此可以得到路徑上時(shí)間的上限、下限和費(fèi)用矩陣。令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é)

本文討論了在路徑時(shí)間為正態(tài)分布的隨機(jī)數(shù)條件下，應(yīng)急資源的多目標(biāo)調(diào)度問題。主要從以下幾個(gè)方面進(jìn)行了研究：（1）考慮到交通工具通過某條道路所消耗的時(shí)間是變化的，因此采用正態(tài)分布的隨機(jī)數(shù)刻畫調(diào)度時(shí)間的不確定性，并建立時(shí)間滿意度最大和路徑費(fèi)用最低的多目標(biāo)應(yīng)急資源調(diào)度模型；（2）設(shè)計(jì)多目標(biāo)的蟻群算法，求解路徑時(shí)間隨機(jī)的條件下，多目標(biāo)的應(yīng)急資源調(diào)度模型的非劣解集，并通過TOPSIS方法對(duì)蟻群算法得到的方案集進(jìn)行選優(yōu)。（3）通過算例驗(yàn)證了模型和算法的可行性和有效性。具有一定的實(shí)際運(yùn)用意義，當(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é)報(bào)，2007,22(005).

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

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

[5]汪定偉，張國祥.突發(fā)性災(zāi)害救援中心選址優(yōu)化的模型與算法[J].東北大學(xué)學(xué)報(bào)（自然科學(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]林興強(qiáng)，陳馳，陳景新，任愛珠.基于行程時(shí)間可靠性的車輛優(yōu)化調(diào)度[J].交通運(yùn)輸系統(tǒng)工程與信息，2005,5(5).

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

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

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

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