遺傳-蟻群算法在災(zāi)后應(yīng)急物資路徑規(guī)劃問題中的應(yīng)用研究

王 帥 蔣華偉

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

0 引 言

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

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

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

1 路徑優(yōu)化模型建立

1.1 假設(shè)條件

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

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

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

(4) 假設(shè)應(yīng)急物資配送點和受災(zāi)點間的距離以及受災(zāi)點相互之間的距離為已知量。

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

1.2 模型建立

已知1.1節(jié)假設(shè)條件，定義下面的變量：

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

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

依據(jù)上述相應(yīng)條件，建立以下模型：

目標函數(shù)：

minZ=(Z1,Z2)

(1)

(2)

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

(3)

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

約束條件：

(4)

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

RTi≤LTii=1,2,…,n

(5)

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

tij=dij/αijv

(6)

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

fij=dijαij/c

(7)

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

(8)

(9)

(10)

式中：|S|為包括物資配送中心和受災(zāi)點的所有點的數(shù)量。

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

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

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

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

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

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

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

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

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

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

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

(11)

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

在諸多轉(zhuǎn)化問題上，最常用的一種辦法即是線性加權(quán)法。把上述用于應(yīng)急物資調(diào)撥車輛路徑優(yōu)化方案的多目標問題轉(zhuǎn)化為單目標問題的函數(shù)如下所示：

(12)

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

(13)

式中：W1和W2是權(quán)值系數(shù)，指每個目標函數(shù)在數(shù)學模型中的權(quán)衡比重，它的具體參數(shù)設(shè)置可以依據(jù)實時應(yīng)急物資車輛路徑調(diào)撥過程狀況來確定。

2 求解遺傳-蟻群算法路徑優(yōu)化模型

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

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

2.1 遺傳-蟻群算法中參數(shù)的設(shè)置

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

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

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

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

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

輸出：CLK的COV。

開始

第一步，初始化

① 首先創(chuàng)建一個弧邊集合COV；

② 弧邊r→1；

③ 類型Lecjk→LecjkType；

④ 構(gòu)建模型的近鄰邊5條弧邊集Dn；

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

第二步，循環(huán)N次，進行如下操作:

1) 從所有優(yōu)化的環(huán)路中隨機選擇一條s；

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

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

第三步，返回COV；

結(jié)束

2.2 遺傳-蟻群算法的實現(xiàn)過程

遺傳-蟻群算法的實現(xiàn)流程如圖1所示。

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

3 遺傳、蟻群及遺傳-蟻群算法中路徑優(yōu)化對比分析

3.1 路徑優(yōu)化結(jié)果對比分析

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

表1 三種算法的最好結(jié)果對照

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

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

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

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

表3 不同處理方式對相應(yīng)算法的變化影響

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

4 仿真實驗

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

表4 實際距離對應(yīng)表 km

表5 受災(zāi)點物資需求情況

表6 路況參數(shù)

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

表7 運輸車輛配送路徑

5 結(jié) 語

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