基于蟻群算法的突發事件應急調度概述

楊祎

【摘 要】 針對突發事件而引起的應急調度目的是為了保證所需資源盡早到達和突發事件損失最小化，本文提出用蟻群算法作為一種智能優化算法來計算出最佳路線。文章概述了蟻群算法，介紹了蟻群優化算法基本流程，評價了它的效果和意義。

【關鍵詞】 突發事件;應急調度;蟻群算法

近年來，突發事件常常發生，當突發事件發生之后，常常因為無法充分地，及時地供應各類資源，比如關于應急資源的庫存短缺、車輛在資源調運過程中安排以及調運方式選擇不合理等，進而又導致其他各種問題的出現。由于突發事件的緊急性、難預知性以及發生后信息匱乏等特點，使得實現突發事件應急調度的空間效應和時間效應有更多的難度，即應急調度的過程較難實現。蟻群算法作為一種智能優化算發已經在諸多領域取得良好的研究成果。

一、應急資源調度的概述

1、應急資源調度的介紹

應急資源調度是指從資源供應點向資源需求點進行資源調運、資源供給的一個過程。應急資源是突發事件中急需的各類資源，它可以包括人力資源、資金資源、物資資源等等。這些資源在整個突發事件中，又有應急需求點多、需求量大、種類繁多、領域廣等特點，故在進行這些資源調度的過程中，我們必須預知資源的布局、優化配置和調度特點，這也是主要的決策問題。

（1）通常情況下，應急調度的弱經濟性和時間約束的緊迫性與普通物流調度是以效益為核心的目標是不同的，應急調度問題的場景通常是在有限且緊迫的時間約束條件下將應急救災物資以最短的時間送達受災點。也就是在時間最短的條件下尋求最小化運輸成本。屬于同時追求運輸時間最小化與運輸成本最小化的多目標規劃問題，而其中運輸時間最小化是核心目標。

（2）在應急調度的一些場景中，我們無法進行事先精確地預測所需要的救災物資的種類、數量等，導致了應急調度的不確定性和突發性。

（3）在實際應用中應急調度配送車輛調度是一種非常規性活動。

2、應急資源調度模型的研究

根據問題涉及的范圍不同應急調度問題屬于復雜的TSP問題（旅行商尋找最佳路線問題），可以在兩種基本類型的基礎上進行描述。第一類是宏觀的應急調度問題，宏觀的應急調度問題應用多種運輸方式協同合作實現應急物資的調度并且在地理空間上設計廣泛。例如“5·12”汶川大地震發生以后，救災物資需要通過水路、公路等方式援助，甚至有時候需要多種運輸方式的協同合作從全國各地甚至全世界調度運輸到災區。另一類是微觀應急調度問題，微觀應急調度問題調度途徑相對單純，涉及地理空間比較小，例如更小區域的應急物資調度。在宏觀調度的調度安排前提下，進行的后續微觀應急調度，主要是完成具體的調度物資向各個分散點的轉移調度。

在我國，對于全國性的突發事件中的應急調度活動，所有的車輛調度都是由政府臨時征用并合理安排調度的。這種情況下，這些車輛都必須在規定時間內完成調度任務，在最短時間內，以最優路徑將應急物資送達受災點，所以在我國研究應急調度問題是十分必要并有現實意義的。

在應急資源調度問題中將車輛路徑問題的求解方法進一步簡化，充分考慮各個因素，將問題分解成若干個基本問題，對于這些若干個基本問題，再利用成熟的研究方法，進而得到最優解或滿意解。目前求解確定性車輛路徑問題的主要方法是啟發式算法，現代啟發式算法在目前的研究成果來看，確實可以找到最優解。這些算法也被統稱為智能優化算法，由此可見，將智能優化算法中的一種——蟻群算法引入到求解應急調度模型中是一個可行的方案。

二、蟻群算法的概述

1、蟻群行為的描述

蟻群算法是對真實蟻群行為研究而提出的。1990年Goss S A等做了著名的“非對稱雙橋”實驗對蟻群的覓食行為進行了研究。實驗結果證明，蟻群通過某種特殊的引導元素進行路徑的選擇，最終會選擇一條最短路徑來完成覓食過程。

螞蟻群體之所以能具有非常強的適應環境變化的能力，是因為螞蟻在尋找食物時，它釋放了一種其他螞蟻也能夠感覺到的特殊分泌物——信息素，這種信息素在它們經過的路徑上釋放，進而指導后繼螞蟻的前進方向。當某條路徑上經過的螞蟻數越多，就會留下更多的信息量，后來的螞蟻也會優先選擇信息量多的路徑，最終整個蟻群會找出最優路徑。

人們正是通過模擬蟻群搜索食物的生物過程，而總結出的一種求解復雜優化問題的啟發式算法——蟻群優化算法。這種算法也正是采用的是一種分布式的協同優化機制，蟻群優化算法中的人工螞蟻群搜索的智能行為——發現最短路徑。表現在以下三個方面：

（1）人工螞蟻在行走時，不會再選擇已經走過的路徑，如此行為可以理解成人工螞蟻的行走有記憶性的。

（2）螞蟻作為群體用信息素作為媒介來進行相互通信，這種方式正是一種協同機制。

（3）在從蟻巢到實物源的尋食過程中，螞蟻是集群活動的，單只螞蟻雖然能夠找到的一條路徑，但很難找到通向食物的較短的路徑。隨著時間流逝，某條路徑的信息濃度會逐漸增高，而后繼螞蟻也會選擇信息素濃度高的路徑行走，如此就形成一條最短路徑。因此蟻群優化算法模型也可以理解成增強學習系統的特例。

圖1-1 蟻群優化算法流程圖

2、蟻群優化算法基本流程

以TSP為例來說明基本蟻群優化算法的實現步驟，蟻群優化算法的執行過程主要體現在以下幾個階段：（1）初始化階段，在這個階段中需要設置運行參數，對于信息素的設置主要是信息素濃度的初始值設置以及它的揮發系數，并且在此階段需要設置搜索一個循環的終止條件。最后也需要進行蟻群數目的設置;（2）搜索階段，本階段是建立在上一階段基礎上的，初始化設置后，蟻群開始搜索的過程都是按照概率轉移公式進行的，根據這個公式，計算出移動過程中的城市轉移概率;（3）信息更新階段，此階段的實現過程都是按照蟻周模型進行的，信息的更新是在每批螞蟻完成可行性解構建之后進行。具體步驟如圖1-1所示。

三、基于蟻群優化算法的應急調度

1、蟻群算法求解車輛路徑問題的思考

分析應急調度問題是考慮了車輛的最大載質量限制和單邊硬時間窗限制的VRP問題。它要求配送車輛必須在每個受災點的時間限制之前將救災物資送達救災點且累計載質量不能超出最大載質量限制。

應用蟻群優化算法求解應急調度問題時，人工螞蟻模擬配送車輛成所有受災點的配送任務，在未完成配送任務的受災點中，根據概率轉移規則找出下一個配送任務且滿足單邊硬時間窗和車輛的最大載質量限制。在人工螞蟻執行整個配送任務中，每一只人工螞蟻都會完成本次所有配送任務后更新信息素，直到整個蟻群完成所有的配送任務，記為一次迭代完成。若沒有找到滿足條件的配送任務，人工螞蟻返回配送中心重新完成未完成的配送任務，直到完成所有的配送任務為止。數次迭代后，直到迭代次數達到最大值或者出現了重復路徑，則表示迭代可以結束了，由此確定最終搜索到全局最優路徑或者近似于最優路徑的次優路徑。這里的由螞蟻來完成配送任務只是利用螞蟻模擬配送路線，在多輪迭代模擬之后可以找到最有路徑或者次優路徑。

【參考文獻】

[1] 劉春林、何建敏、盛昭瀚.應急系統調度問題的模糊規劃方法[J].系統工程學報，1999（4）.

[2] 何建敏、劉春林.限制期條件下應急車輛調度問題的模糊優化方法[J].控制與決策，2001.16（3）.

[3] 高淑萍，劉三陽.應急系統調度問題的最優決策[J].系統工程與電子技術，2003.25（10）.

[4] 蔣璐璐.蟻群算法在車輛路徑問題中的應用研究[D].西安理工大學，2010.

[5] 詹士昌、徐婕、吳俊.蟻群算法中有關算法參數的最優選擇[J].科技通報，2003（05）.

[6] 孫明雪.蟻群算法的改進及其在TSP問題中的應用[D].吉林大學，2006.

[7] 王穎、謝劍英等.一種基于蟻群系統的多點路由新算法[J].計算機工程，2001（01）.