楊祎

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

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

近年來，突發(fā)事件常常發(fā)生，當(dāng)突發(fā)事件發(fā)生之后，常常因?yàn)闊o法充分地，及時(shí)地供應(yīng)各類資源，比如關(guān)于應(yīng)急資源的庫存短缺、車輛在資源調(diào)運(yùn)過程中安排以及調(diào)運(yùn)方式選擇不合理等，進(jìn)而又導(dǎo)致其他各種問題的出現(xiàn)。由于突發(fā)事件的緊急性、難預(yù)知性以及發(fā)生后信息匱乏等特點(diǎn)，使得實(shí)現(xiàn)突發(fā)事件應(yīng)急調(diào)度的空間效應(yīng)和時(shí)間效應(yīng)有更多的難度，即應(yīng)急調(diào)度的過程較難實(shí)現(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ǎn)向資源需求點(diǎn)進(jìn)行資源調(diào)運(yùn)、資源供給的一個(gè)過程。應(yīng)急資源是突發(fā)事件中急需的各類資源，它可以包括人力資源、資金資源、物資資源等等。這些資源在整個(gè)突發(fā)事件中，又有應(yīng)急需求點(diǎn)多、需求量大、種類繁多、領(lǐng)域廣等特點(diǎn)，故在進(jìn)行這些資源調(diào)度的過程中，我們必須預(yù)知資源的布局、優(yōu)化配置和調(diào)度特點(diǎn)，這也是主要的決策問題。

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

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

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

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

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

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

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

二、蟻群算法的概述

1、蟻群行為的描述

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

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

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

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

（2）螞蟻?zhàn)鳛槿后w用信息素作為媒介來進(jìn)行相互通信，這種方式正是一種協(xié)同機(jī)制。

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

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

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

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

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

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

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

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

【參考文獻(xiàn)】

[1] 劉春林、何建敏、盛昭瀚.應(yīng)急系統(tǒng)調(diào)度問題的模糊規(guī)劃方法[J].系統(tǒng)工程學(xué)報(bào)，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].科技通報(bào)，2003（05）.

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

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