基于蟻群算法的突發(fā)事件應(yīng)急調(diào)度概述

楊祎

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

【關(guān)鍵詞】 突發(fā)事件;應(yīng)急調(diào)度;蟻群算法

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

一、應(yīng)急資源調(diào)度的概述

1、應(yīng)急資源調(diào)度的介紹

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

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

（2）在應(yīng)急調(diào)度的一些場景中，我們無法進行事先精確地預(yù)測所需要的救災(zāi)物資的種類、數(shù)量等，導(dǎo)致了應(yīng)急調(diào)度的不確定性和突發(fā)性。

（3）在實際應(yīng)用中應(yīng)急調(diào)度配送車輛調(diào)度是一種非常規(guī)性活動。

2、應(yīng)急資源調(diào)度模型的研究

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

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

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

二、蟻群算法的概述

1、蟻群行為的描述

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

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

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

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

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

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

圖1-1 蟻群優(yōu)化算法流程圖

2、蟻群優(yōu)化算法基本流程

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

三、基于蟻群優(yōu)化算法的應(yīng)急調(diào)度

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

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

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

【參考文獻】

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

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

[3] 高淑萍，劉三陽.應(yīng)急系統(tǒng)調(diào)度問題的最優(yōu)決策[J].系統(tǒng)工程與電子技術(shù)，2003.25（10）.

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

[5] 詹士昌、徐婕、吳俊.蟻群算法中有關(guān)算法參數(shù)的最優(yōu)選擇[J].科技通報，2003（05）.

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

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