基于混沌蟻群算法的地震應急物流配送路徑優(yōu)化問題研究

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

(防災科技學院防災儀器系，北京 101601)

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

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

1.1 問題闡述

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

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

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

1)單一的地震救災物資配送中心作為地震應急救援車輛起點及終點。

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

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

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

5)地震應急運輸救援車輛必須在要求時間內到達，否則，優(yōu)化路徑將被放棄。

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

S.T.

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

1，2，3，…，l為地震受災點編號，0，1，…為地震救災物資配送中心編號，定義變量xijk，yki為:

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

2 混沌蟻群算法求解模型

Step1

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

Step2由(15)計算螞蟻k的轉移概率。

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

Step3根據(jù)轉移概率轉移到下一個救災點j，同時將j加入tabuk中。如果車輛載重達到上限，車輛返回地震救災物資配送中心;

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

Step5計算目標函數(shù)和Tk，并記錄當前最優(yōu)解;

Step6

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

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

3 實驗仿真

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

表1 實驗數(shù)據(jù)

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

圖1 混沌蟻群算法運行路線圖

圖2 基本蟻群算法運行路線圖

6 結束語

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

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

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

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

［4］葉志偉，鄭肇葆.蟻群算法中參數(shù) α，β，設置的研究——以TSP問題為例［J］.武漢大學學報(信息科學版)，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.