遺傳-蟻群算法在災后應急物資路徑規劃問題中的應用研究

王 帥 蔣華偉

1(中國地震局地球物理勘探中心綜合地球物理研究室 河南 鄭州 450002)2(河南工業大學信息科學與工程學院 河南 鄭州 450001)

0 引 言

干旱、洪澇、地震、臺風等重大自然災害的發生嚴重影響社會經濟發展和人民生命財產安全，開展災后應急物資運輸的路徑優化工作是值得研究的重要課題。如國家在應對青海玉樹地震和汶川大地震等應急物資調度工作上做到了及時供應，但在應急物資路徑規劃方面仍顯薄弱。因此依靠現代化信息科學技術提升應急物資調撥效率，創建合理、高效的應急糧食調撥車輛路徑優化系統已刻不容緩。

對于車輛路徑規劃問題，國內外專家學者做了很多研究。對應急物資車輛路徑規劃的研究主要體現在如下幾個方面：Rathi等[1]提出了LP模型，主要用于解決應急車輛參加救援時的指派問題；Equi等[2]對在應急物流運送中貨物的組合運輸與應急車輛的調度問題進行了研究。文獻[3-4]借助網絡可靠性方法同蟻群算法相結合的思想，對帶有時間窗限制的物流車輛路徑問題進行了研究。通過算法的結合與改進，他們的研究方法可以規劃出滿足供應需求的最佳行駛路徑。但綜合分析，尚存在所得結果易陷入局部最優；目前僅對多個救援點組合優化支援單個受災點做了大量研究；沒有將受災點的具體位置、需求緊急程度、實時路況等考慮進去。研究所涉及的內容仍有局限性。

本文對應急物資調撥問題的研究多集中在如下方面：(1) 應急物資調撥多救援點組合優化研究。對多個物資需求點的應急調度問題進行分析，結合實際情況給出了相應的約束條件，建立了“應急開始最早，救援點最少”的多目標應急物資調度數學模型，初步解決了應急物資調度中的路徑規劃問題。(2) 應急物資調撥路徑優化研究。圍繞應急物資調撥車輛路徑優化問題開展研究，考慮實時路況參數的情況下，把蟻群算法和遺傳算法結合起來，構建包含時間與成本等要素在內的多目標數學規劃模型。

1 路徑優化模型建立

1.1 假設條件

(1) 每一個受災點只能被訪問一次，每一輛車只能走一條路線。

(2) 每一個受災點均有最晚到達時間限制，物資需在約定的時間點前送到。

(3) 各個節點之間假設都能連通，各個路段根據路徑的好壞有一個估計值，估計值越低，路越難走車速越慢。

(4) 假設應急物資配送點和受災點間的距離以及受災點相互之間的距離為已知量。

(5) 每輛車的載重量大于或等于此輛車所遍歷的所有受災點所需要的物資總量。

1.2 模型建立

已知1.1節假設條件，定義下面的變量：

M為物資運輸車輛集合，M={k,k=1,2,…,m}。

V為應急物資配送點和各個受災點的集合，V={i,i=0,1,…,n},當i=0時在物資配送中心位置。

依據上述相應條件，建立以下模型：

目標函數：

minZ=(Z1,Z2)

(1)

(2)

式中：tij為運輸車從受災點i運送到點j所需花費的時間。

(3)

式中：fij為運輸車從受災點i運送到點j所需的費用。

約束條件：

(4)

式中：qi為受災點i所需物資總量，i∈V;Qk為運輸車所載物資量，Qk≥max{qi,i∈V}。

RTi≤LTii=1,2,…,n

(5)

式中：RTi為運送車抵達受災點i的時間；LTi為運送車輛最晚到達點i的時間。

tij=dij/αijv

(6)

式中：dij為受災點i和j間的距離；v為車的平均速度；αij為路況參數，0≤αij≤1，值越小路況越差。

fij=dijαij/c

(7)

式中：c為運輸車每行駛單位距離所需的費用。

(8)

(9)

(10)

式中：|S|為包括物資配送中心和受災點的所有點的數量。

上述模型所引出的數學表達式含義如下：

式(1)是總目標函數，也就是在滿足應急時間最短的情況下兼顧運送成本；

式(2)是主要目標函數，即是在整個應急過程中所花費的時間最少；

式(3)是次要目標函數，即是在整個應急過程中所需費用最低；

式(4)是每輛車所遍歷的受災點所需的物資總量不大于該車的承重量；

式(5)運輸車抵達受災點的時間不得超過所允許的最晚時間限制；

式(6)在考慮路況系數的影響下，運輸車從受災點i到點j所需時間；

式(7)在考慮路況系數的影響下，運輸車從受災點i到點j所需費用；

式(8)確保每個受災節點被每輛運輸車遍歷一次；

式(9)、式(10)為了保證每輛運輸車從物資配送中心把物資配發到該輛車被安排的受災點后，返回到物資配送中心。

在應急物資調撥路徑規劃問題上，“應急”即時間觀念非常重要，只有所需物資在第一時間送達到災區，才能真正體現出車輛路徑優化的意義。若把各個受災點和物資物流配送中點均看成應急車輛遍歷的節點，假定運輸路線上任意一個節點i是鄰近節點j的上一個物資運達點，運輸車抵達節點i的時間是RTi，抵達受災點j的時間是RTj，有關于時間的限制函數：

(11)

式中：UTi為運送車在受災點i卸車所花費的時間。

在諸多轉化問題上，最常用的一種辦法即是線性加權法。把上述用于應急物資調撥車輛路徑優化方案的多目標問題轉化為單目標問題的函數如下所示：

(12)

假設每個受災點對物資的緊急需求程度一樣，則把式(6)、式(7)代入式(12)，目標函數為：

(13)

式中：W1和W2是權值系數，指每個目標函數在數學模型中的權衡比重，它的具體參數設置可以依據實時應急物資車輛路徑調撥過程狀況來確定。

2 求解遺傳-蟻群算法路徑優化模型

由于蟻群算法具有容易陷進局部最優、初期的信息素匱乏和求解速度較慢的缺點，而遺傳算法具有全局快速搜索能力，缺點是無法對系統的反饋信息充分利用，求解效率偏低[5-6]。把蟻群算法和遺傳算法相聯合，在求解的初始時刻信息素分布由GA生成，然后采用ACA求得最優解。基本思想[7]是：充分利用各個算法的優點，揚長避短，優勢互補，從而達到時間、經濟和安全性等效率上的多重提高。

把遺傳算法和蟻群算法相融合來求解應急物資調撥車輛路徑規劃問題的方法是：先利用遺傳算法的搜索速度快、搜索的隨機性以及全局收斂性生成模型的可行解；然后把它轉化成搜尋最優路徑的初始時刻的信息素分布；再采用蟻群算法在現有信息素布局的情況下，改進蟻群算法，設計螞蟻群體的信息素更新策略和轉移策略；接著，為了使算法的求解能力提高，引入Lin-Kernighan(LK)[8]局部搜索優化算法。通過建立合適的局部搜索優化算法優化邊集，使得求解效率得到提高，從而提高了蟻群算法的尋優能力和收斂速率。

2.1 遺傳-蟻群算法中參數的設置

(1) 遺傳算法參數的設置 目前遺傳算法已非常成熟，在此不作詳細陳述。下面列出模型求解當中需要的相關設置與模型求解流程：染色體由編碼構造而成，在求解應急車輛路徑規劃問題時，一般采用相對直觀的自然數編碼的方式，每條染色體即對應一組可行解；在構造一條新的路徑時，在當前的路徑當中按順序插入染色體總基因值(受災點)，若某個基因插入后導致這條路徑上出現車輛到達受災點的時間無法滿足條件，則重新構造路徑，重新回到初始狀態，直至全部受災點規劃到此路徑中。

適應度函數的設計：由于所建立的模型是最小化的組合優化問題，其終極目標為所有車輛所需總費用最少，也即是目標函數取最小值。若某輛車在行駛過程中所花費的總代價最大，則此路徑的適應度最小，設每條路徑上的花費為f，那么適應度F=1/f。

遺傳操作：① 在選擇算子上采取對每一個子群體利用順序選擇法,其基本策略是：基于目標函數值大小把群體中的每個個體排序，根據這個排列順序來進行選擇運算，使得排前邊的優異個體會有更加多的機會遺傳給下一代。確定個體的選擇概率，引入賭輪選擇法。如此循環幾代后，就可以求出模型問題的幾種可行解。② 交叉就是將兩個父個體里邊的部分基因替換，從而形成新個體的過程。③ 針對變異算子采用順序均勻變異的操作。

(2) 蟻群算法參數的設置 蟻群算法易表現出停滯、早熟的征象，可以引進局部最優搜尋方法，也就是通過弧、邊互換，在可行解的多個鄰域內適當調整，當進行到無法在鄰域內調整時結束。以此逐個調整的方法有效避免絕對的局部最優解，這些經過局部調整的解是為了在以后的信息素初始分布的蟻群算法中使用。目前常用的局部最優搜索策略包括遺傳算法、貪心算法、二階段法以及三階段法等。經大量研究后表明鏈式LK算法對旅行商的車輛路徑優化問題有更好的實際效果和效率。本文選用LK鏈式算法，采用以下算法創建CLK(Chained Lin-Kernighan)的參考優化邊集COV:

輸入：遺傳算法建立的初始解，初始化各個弧邊的信息素濃度；

輸出：CLK的COV。

開始

第一步，初始化

① 首先創建一個弧邊集合COV；

② 弧邊r→1；

③ 類型Lecjk→LecjkType；

④ 構建模型的近鄰邊5條弧邊集Dn；

(注：以上是在實驗中構造的原始初始弧邊集)

第二步，循環N次，進行如下操作:

1) 從所有優化的環路中隨機選擇一條s；

2) 計算CLK(r,LeckType,Dn,s)從而得出s′(s′是一條優化之后的路徑)；

3) 把s′里面全部弧邊并入到COV；

第三步，返回COV；

結束

2.2 遺傳-蟻群算法的實現過程

遺傳-蟻群算法的實現流程如圖1所示。

圖1 求解模型的遺傳-蟻群算法流程圖

3 遺傳、蟻群及遺傳-蟻群算法中路徑優化對比分析

3.1 路徑優化結果對比分析

把文中提到的蟻群算法跟遺傳算法結合起來求解由Solomon構建的一些帶硬時間窗問題的測試數據模型[9]。針對不同數量的受災需求點P1問題，把運輸車輛的限載量設置為30，單位時間長度為1，響應時間為95。實驗參數設置如下：蟻群算法中ρ=0.2，β=1，α=1，NC=4 000;遺傳算法中pm=0.1,pc=0.9,N=100,MAXGEN=200。每一種狀況下測10次，選擇這10次中的最好解。分別選用遺傳-蟻群算法、基本ACA、GA對標準數據集來測試，表1中約定全部運輸車載重量相同，表2中約定更改運輸車的載重量。

表1 三種算法的最好結果對照

表2 更改載重量后三種算法的最好成效對照

通過以上實驗表明，基本蟻群算法和遺傳算法所得出的最佳路徑沒有本文所采用的遺傳-蟻群算法的最佳路徑短，說明遺傳-蟻群算法能更好地解決VRPTW問題。

3.2 LK優化算法和信息素更新策略對遺傳-蟻群算法性能的影響分析

針對P1中的20個物資需求點，分開用三種方式來測試，其中參數的設置同3.1節一樣，三種算法各運行100次，不同的測試方法對三種算法的性能的變動影響如表3所示。表3中方法A不使用信息更新策略且不用LK鏈式算法優化處理；方法B不用LK鏈式算法優化處理但使用信息素更新策略；方法C是既使用信息更新策略，又使用LK鏈式算法優化處理。

表3 不同處理方式對相應算法的變化影響

從表3得出，采用遺傳-蟻群算法的同時，對可行解和蟻群遍歷的路徑進行LK鏈式算法優化處理得到的結果性能最好，而只使用蟻群算法或者是單單使用信息素更新策略均無法讓算法得出最好的解。

4 仿真實驗

把遺傳-蟻群算法用來求解應急物資調撥路徑規劃中的數學模型，依據模型所需的條件，從眾多數據中選擇出一組比較貼近實際情況的來分析。假定某個地點出現突發事件急需物資支援，包含1個應急物資分發站點與8個受災點，且假設應急物資分發站點表示為0節點。表4指應急物資分發站點和8個受災點以及各個受災點之間的真實距離；表5指各個受災點i(i=1,2,…,8)所需物資數量為qi，UTi為卸物資用時，LTi為允許車輛抵達受災點的最遲時間；表6指應急物資分發站點和8個受災點以及各個受災點之間的路況參數。應急車的勻速行駛速率是60 km/h,所有車輛的承載量均為10 t，單位距離的運輸價格c=1.5元/km。途中規定物資必須在規定的時間內送到物資需求點且不得超載，應急物資調撥過程中要求適當合理地安排好整個配送路線，滿足車輛行駛的總時間最短且運輸產生的費用最少。

表4 實際距離對應表 km

表5 受災點物資需求情況

表6 路況參數

為了驗證遺傳-蟻群算法的有效性，采用MATLAB 2012軟件進行實驗仿真。由于在應急物資運送中時間的緊迫性，把目標函數里的時間、花費的比重系數設置為ω1=0.8,ω2=0.2。蟻群算法設置參數為：ρ=0.5，β=3，α=1，NC=2 000,Q=100;遺傳算法參數設置為：pm=0.1,pc=0.9,N=50,MAXGEN=400。當目標函數值取得minZ=679.5時，運輸車的最終道路行駛路徑規劃如表7所示。

表7 運輸車輛配送路徑

5 結 語

本文依據應急物資調撥路徑規劃的實際問題，構建了一個考慮應急成本的同時兼顧應急時間等多個目標的數學模型。并且根據當今路徑規劃算法在應急物資調撥路徑規劃問題中存在的不足，首先運用遺傳算法依據模型需要滿足的條件求解出一些優化解，然后再轉為蟻群算法中的信息素初始分布，計算得出各個可行解并做優化處理，最終求得問題模型的最優解。通過比較驗證了該方法的優越性，同時該方法也可解決單應急點的應急物資路徑優化問題。由于遺傳-蟻群算法在程序執行中會產生代碼冗余，求解速度慢，因此改進算法，使其更加適應應急物資路徑規劃模型的特點，是下一步的研究方向。