劉金雨，劉亞敏，連 浩，張佳惠，王 娟

(防災(zāi)科技學(xué)院防災(zāi)儀器系，北京 101601)

近年來，我國地震頻發(fā)，快捷有效開展災(zāi)后救援已成為近年來的研究重點(diǎn)。但目前大多數(shù)混沌蟻群算法只局限于定性分析及保障機(jī)制［1］，缺乏定量研究。本文采用混沌蟻群算法對數(shù)學(xué)模型進(jìn)行求解，提高了基本蟻群算法的全局搜索能力及收斂速度。仿真試驗(yàn)驗(yàn)證了算法的可行性及有效性。

1 地震應(yīng)急物流配送路徑優(yōu)化

1.1 問題闡述

地震救災(zāi)物資的運(yùn)輸需求具有突發(fā)性和局部性，因此地震救援需要考慮環(huán)境時(shí)間等因素。本文以地震救援物資運(yùn)送到各個(gè)地震受災(zāi)點(diǎn)時(shí)間最短為目標(biāo)，引入路況系數(shù)及地震救援物資緊缺系數(shù)來分別表征道路損壞程度及救援物資緊缺程度，其中路況系數(shù)與道路損壞程度成正比，地震救援物資緊缺系數(shù)與救援車輛配送效率成正比。

1.2 地震應(yīng)急物流配送路徑優(yōu)化模型

基于混沌蟻群算法的數(shù)學(xué)模型假設(shè)如下:

1)單一的地震救災(zāi)物資配送中心作為地震應(yīng)急救援車輛起點(diǎn)及終點(diǎn)。

2)每次配送中，地震救援車輛所載物資小于等于地震救援車輛的已知最大載重量，途中無裝貨。

3)地震受災(zāi)點(diǎn)的位置和需求量已知且需求量不超過地震救援車輛的最大載重量。

4)地震救援車輛平均行駛速度已知且確定。

5)地震應(yīng)急運(yùn)輸救援車輛必須在要求時(shí)間內(nèi)到達(dá)，否則，優(yōu)化路徑將被放棄。

基于上述假設(shè)，數(shù)學(xué)模型以配送時(shí)間最短為目標(biāo)，如下:

S.T.

其中，地震救援車輛總數(shù)為m';地震受災(zāi)點(diǎn)總個(gè)數(shù)為l;i與j點(diǎn)之間的總距離為dij;地震救援車輛k行駛的總時(shí)長為Tk;tij為地震救援車輛從地震受災(zāi)點(diǎn)i到地震受災(zāi)點(diǎn)j行駛的總時(shí)長;gi為第i個(gè)地震受災(zāi)點(diǎn)的總物資需求量;地震救援車輛最大載重量限制為q;地震救援車輛編號為k;地震物資救援車輛行駛速度為v;災(zāi)后路況系數(shù)為φij;災(zāi)后醫(yī)療器械緊缺程度用系數(shù)μi表示;tjk為地震救援車輛k到達(dá)受災(zāi)點(diǎn)i點(diǎn)的總時(shí)長;最大地震受災(zāi)點(diǎn)配送時(shí)間為tei。

1，2，3，…，l為地震受災(zāi)點(diǎn)編號，0，1，…為地震救災(zāi)物資配送中心編號，定義變量xijk，yki為:

式(1)是以時(shí)間最少為目標(biāo)函數(shù)的數(shù)學(xué)模型。式(2)為地震救援車輛k行駛總時(shí)長;式(3)為在加入每個(gè)地震受災(zāi)點(diǎn)的路況情況和物資緊缺程度后，地震救援車輛行駛經(jīng)過地震受災(zāi)點(diǎn)i，j所需要總時(shí)長;式(4)地震救援物資總重量小于等于地震救援車輛最大載重;式(5)、式(6)和式(7)有且僅有一救援車輛經(jīng)過單一地震受災(zāi)點(diǎn)。式(8)為第k輛車經(jīng)過i轉(zhuǎn)移完成第j需求點(diǎn)任務(wù);式(9)為第k輛車經(jīng)過j轉(zhuǎn)移完成第i需求點(diǎn)任務(wù)。式(10)確保全部救援車輛出發(fā)點(diǎn)及終點(diǎn)為地震救災(zāi)物資配送中心。式(11)為物資到達(dá)地震受災(zāi)點(diǎn)時(shí)長限制。

2 混沌蟻群算法求解模型

Step1

式中 μ 為控制參數(shù)，取值區(qū)間［3.56，4］［2］;信息素初始值由混沌量確定。

Step2由(15)計(jì)算螞蟻k的轉(zhuǎn)移概率。

式中，allowedk=(1，2，…，n)－tabuk為螞蟻 k當(dāng)前能選擇集合;tabuk(k=1，2，…，m)表示螞蟻 k的禁忌表，ηij(t)為啟發(fā)函數(shù)，一般選ηij(t)=1/dij;α為路徑ij上殘留信息的重要程度，β為啟發(fā)信息的重要程度。

Step3根據(jù)轉(zhuǎn)移概率轉(zhuǎn)移到下一個(gè)救災(zāi)點(diǎn)j，同時(shí)將j加入tabuk中。如果車輛載重達(dá)到上限，車輛返回地震救災(zāi)物資配送中心;

Step4檢查tabuk是否滿。若為否，回到step 2，否則，繼續(xù)step 5;

Step5計(jì)算目標(biāo)函數(shù)和Tk，并記錄當(dāng)前最優(yōu)解;

Step6

上式為信息素更新，Zij(t)是混沌變量。q1為系數(shù)。ρ表示全局信息素?fù)]發(fā)因子(0，1)［3］。Δτij(t)表示本次周游中路徑ij信息素增量。

Step7若 NC ＜NCmaxNC=NC+1，清空 tabuk，回到 step 2。若 NC=NCmax，結(jié)束。

3 實(shí)驗(yàn)仿真

假定災(zāi)后4輛救援車向19個(gè)地震受災(zāi)點(diǎn)運(yùn)送地震救災(zāi)物資。救援車輛最大裝載重為90 t，速度為60 km/h。表1為各個(gè)地震救援路徑優(yōu)化實(shí)驗(yàn)數(shù)據(jù)。選α=1，β=5，ρ=0.6［4］，混沌變量 Zij(0)=0.5，q1=1。地震受災(zāi)點(diǎn)與地震救災(zāi)物資配送中心之間的距離計(jì)算如下式:

表1 實(shí)驗(yàn)數(shù)據(jù)

圖1，圖2分別給出4輛救援車基于混沌蟻群算法和基本蟻群算法的運(yùn)行路線圖的最優(yōu)解尋優(yōu)路線。由圖可以看出混沌蟻群算法所需配送時(shí)間遠(yuǎn)小于基本蟻群算法所需的配送時(shí)間。這是由于引入混沌概念，增加了螞蟻的歷遍性，近而避免基本蟻群算法過早收斂及陷于局部最優(yōu)的不足。

圖1 混沌蟻群算法運(yùn)行路線圖

圖2 基本蟻群算法運(yùn)行路線圖

6 結(jié)束語

混沌蟻群算法利用了歷遍性優(yōu)化搜索［6］，在地震應(yīng)急物流路徑優(yōu)化問題上優(yōu)于基本蟻群算法。本文數(shù)學(xué)模型考慮的實(shí)際條件還不是很全面，今后對于地震應(yīng)急物流路徑優(yōu)化問題的模型建立還需要進(jìn)一步的完善和充實(shí)。

［1］馮旭東，率帥.抓好應(yīng)急物流配送的幾項(xiàng)對策［J］.中國物流與采購，2003，23(3):31 －34.

［2］高尚.旅行商問題的混沌蟻群算法［J］.系統(tǒng)工程理論與實(shí)踐，2005，8(9):100 －103.

［3］劉立東.改進(jìn)蟻群優(yōu)化算法的研究［D］.成都:西南交通大學(xué)，2005.

［4］葉志偉，鄭肇葆.蟻群算法中參數(shù) α，β，設(shè)置的研究——以TSP問題為例［J］.武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2004，29(7):597 －601.

［5］Dorigo M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem［J］.IEEE Transactions on Evolutionary Computation，1997，1(1):53－66.

［6］Reimann M，Doerner K，Riehard FH.D －Ants:Savings Based Ants Divide and Conquer the Vehicle Routing Problem［J］.Computers and Operations Research，2004，31(2):563－591.