蟻群算法求解路徑時間隨機的應急資源調度問題研究

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

（東南大學 經濟管理學院，南京 211189）

0 引言

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

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

1 問題描述與模型建立

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

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

設網絡G中任意一條邊e的時間權重為[μ(e)-3σ(e),μ(e)+3σ(e)]，則對 于 任 意 一 條 路 徑P，其 時間權重也是區間數

由于[μ-3σ,μ+3σ]是服從正態分布的區間數，其密度函數為：

在網絡優化中，若只考慮兩點之間的最短路徑問題，便轉化成最小費用流問題的特殊情形。一般的最小費用流可以寫成線性規劃的形式，即：

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

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

（2）當網絡中任意兩節點存在連接邊時，邊上的單位流量費用等于邊權的值；當任意兩節點不存在連接邊時，邊上的單位流量費用等于一個很大的常數；

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

這樣，對于上述最小費用流問題實質上可以轉化為一個整數線性規劃的形式，即：

定義 1 設M=[μ-3σ,μ+3σ]是服從正態分布的區間數，c為給定的實數，M小于等于c的可能度定義為：

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

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

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

顯然，滿意度函數具有以下性質：

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

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

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

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

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

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

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

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

在給出多目標資源調度模型的蟻群算法之前，首先對以下符號進行定義：

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

m為螞蟻個數；

s為出救點；

d為事件爆發點；

Nk為螞蟻k當前的可行集；

NCmax為蟻群算法循環最大次數；

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

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

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

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

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

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

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

為了適應該模型的求解，還需要對蟻群算法的過程進行調整。

（1）螞蟻可行集的設置

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

（2）目標函數的調整

在確定情況下，問題求解的一個目標是時間最短。而當前該目標變為滿意度最大。因此算法的的需要改成滿意度。

（3）信息素增加值的調整

（4）螞蟻進行下一節點選擇時，能見度的相對重要性應當適當減少。因為問題的目標不是一次運行的時間最短問題，而是要求所有可行解中時間滿意度最大。

根據以上的改進，考慮到應急調度中時間因數的重要性，設計算法時讓以時間為目標的螞蟻群先走。因此設計算法如下。

輸入參數：α，β，ρ，m，Q，s，d，NCmax

步驟1：初始化參數nc←1；

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

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

步驟4：若k＞m，根據m次循環后得到的所有目標函數值更新解集，并令o←o+1，轉步驟3；否則令k←k+1，轉步驟5；

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

步驟6：根據和蒙特卡洛方法在集合Nk中選中節點i；

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

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

（1）無量綱化

（2）確定最優值與最劣值

（3）計算歐氏距離

（4）計算接近度

（5）選取最優方案

選擇Ci最大的作為非劣解集中的最優方案。

3 算例分析

圖1 時間為正態分布隨機數時的城市網絡

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

表1 非劣解集

由此可以得到決策矩陣：

采用TOPSIS方法，可以得到目標集合（0.9182，93）最優，即在該環境下選擇路徑1-＞4-＞9-＞11-＞14-＞13-＞15是最優的。

4 總結

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

[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]潘郁,余佳,達慶利.基于粒子群算法的連續性消耗應急資源調度[J].系統工程學報，2007,22(005).

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

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

[5]汪定偉，張國祥.突發性災害救援中心選址優化的模型與算法[J].東北大學學報（自然科學版），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]林興強，陳馳，陳景新，任愛珠.基于行程時間可靠性的車輛優化調度[J].交通運輸系統工程與信息，2005,5(5).

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

[9]劉春林，何建敏，盛昭瀚.應急系統調度問題的模糊規劃方法[J].系統工程學報，1999,14(4).

[10]劉春林，沈厚才.一類離散應急供應系統的兩目標優化模型[J].中國管理科學，2003,11(4).

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