基于啟發(fā)式函數(shù)蟻群算法的VRP優(yōu)化研究

鄭小雪

（福建農(nóng)林大學 交通學院，福建 福州 350002）

物流配送運輸，一般是指配送中心按照不同客戶多頻度、小批量的訂貨要求進行組織配送，即根據(jù)貨物量進行車輛的分配和配送線路的生成，也就是研究車輛的路徑問題。由于從事城市配送汽車貨運工作條件復雜，不僅貨運點多、貨物種類繁多、道路網(wǎng)復雜，而且運輸服務地區(qū)內(nèi)運輸網(wǎng)點分布不均勻。因此，如何應用現(xiàn)代數(shù)學方法及計算機快速求解路線優(yōu)化方案，是國內(nèi)外專家學者普遍探索的重要課題。

1 VRP問題描述及分類

從配送中心 (物流據(jù)點) 用多輛車向多個需求點 (客戶) 送貨，每個需求點的位置和需求量為已知，每輛車的載重量一定，要求合理安排車輛路線，達到一定的目標 (如路程最短、費用最少、時間盡量少、使用車輛盡量少等) 即為VRP問題[1]。并滿足以下條件：每條配送路徑上各需求點的需求量之和，不超過車輛載重量；每條配送路徑的長度不超過車輛一次配送的最大行駛距離；每個需求點必須滿足，且只能有一輛車送貨；每輛車均從中心出發(fā)，完成任務后又全部回到中心。

根據(jù)VRP問題的條件可分為以下分類：

（1）按照運輸任務分為純裝問題、純卸問題以及裝卸混合問題。

（2）按車輛載貨狀況分滿載問題和非滿載問題。

（3）按照車輛類型分為單車型問題和多車型問題。

（4）按照車輛是否返回配送中心車場，劃分為車輛開放問題和車輛封閉問題。

（5）按照優(yōu)化的目標可分為單目標優(yōu)化問題和多目標優(yōu)化問題。

（6）按照有無時間要求可分為有時間窗問題和無時間窗問題。

實際中的車輛優(yōu)化調(diào)度問題可能是以上分類中的一種或幾種的綜合。目前國內(nèi)外用于解決該問題的現(xiàn)代數(shù)學方法，主要有以下幾類[1]：精確優(yōu)化方法、啟發(fā)方法、模擬方法、交互優(yōu)化法。

2 VRP問題的數(shù)學模型

VRP問題在現(xiàn)實的物流系統(tǒng)中可由服務區(qū)、倉庫、分布在服務區(qū)內(nèi)的服務點組成。要把經(jīng)典的VRP問題抽象成一個數(shù)學模型，需要設定一些前提：只有一個倉庫，所有車輛從這里裝載貨物出發(fā)，運送完貨物返回倉庫；所有的車輛能力都是一樣的；每一個服務點只能由一輛車提供服務[2]。

設配送中心需向L個客戶送貨，每個客戶的需求量是g，每輛車的載重量是q，cij表示從i點到j點的運輸成本，其含義可以是距離、費用、時間等，設配送中心編碼為0，客戶編碼為1,2,…,L，數(shù)學模型如下。

建立數(shù)學模型：

其中：式⑴保證了總成本Z最??；式⑵為車輛的載重量約束；式⑶保證了每個客戶點的運輸任務僅由一輛車來完成，而所有的運輸任務則由K輛車共同完成；式⑷和式⑸保證每個客戶能且只能被一輛車服務一次。

3 蟻群算法在求解VRP中的應用

3.1 螞蟻的轉(zhuǎn)移策略

螞蟻的轉(zhuǎn)移策略是蟻群算法的重要組成部分，是螞蟻構(gòu)造路徑的過程，它在很大程度上決定了算法的性能。在求解TSP (旅行者問題) 時，由于每只螞蟻需要遍歷所有的結(jié)點，因此，初始狀態(tài)下，螞蟻可以位于任意結(jié)點，且在螞蟻轉(zhuǎn)移過程中，該只螞蟻沒有經(jīng)過的所有結(jié)點，均可作為轉(zhuǎn)移目標。而在求解VRP時，每只螞蟻遍歷路徑應是：僅包含部分結(jié)點；包含且僅包含一次配送中心；路徑必須滿足車輛容量和行駛距離的限制。因此，在求解時，螞蟻的初始位置與轉(zhuǎn)移策略如下。

（1）所有螞蟻的初始位置均為配送中心，每只螞蟻在滿足車輛容量和行駛距離限制的情況下，盡可能多地遍歷結(jié)點，并最終返回配送中心。此時，每只螞蟻的禁忌表中存放除配送中心以外的所有該螞蟻已經(jīng)遍歷的結(jié)點。

（2）螞蟻從任意結(jié)點出發(fā)，在完成一個包含配送中心，且滿足車輛容量和行駛距離限制的回路后，結(jié)束遍歷。此時，若某只螞蟻的初始位置不是配送中心，則該螞蟻的禁忌表中存放該螞蟻已經(jīng)遍歷的所有結(jié)點，否則存放除配送中心以外的該螞蟻已經(jīng)遍歷的所有結(jié)點。

3.2 可行解構(gòu)造

當使用蟻群算法求解VRP時，每只螞蟻只遍歷部分結(jié)點，因此，當所有螞蟻遍歷完成時，從中選擇滿足車輛數(shù)限制的若干條螞蟻遍歷路徑，即①這些螞蟻恰好遍歷了所有結(jié)點，且除配送中心外，每個結(jié)點僅被一只螞蟻遍歷；②這些螞蟻遍歷的路徑覆蓋了所有結(jié)點，但是除了配送中心以外，有的結(jié)點被多只螞蟻遍歷；③這些螞蟻遍歷的路徑并沒有覆蓋所有的結(jié)點，其中①中的路徑構(gòu)成一個可行解，但是這種情況出現(xiàn)的概率極小，而②和③中的路徑均不能構(gòu)成可行解，這就需要進行可行解構(gòu)造，即刪除除配送中心外被多只螞蟻遍歷的結(jié)點和插入未被螞蟻遍歷的結(jié)點。

3.3 算法優(yōu)化

通過“3.1”和“3.2”節(jié)的操作后，蟻群算法可用于求解VRP，但是算法的求解性能可能并不好?？梢詮囊韵聨追矫嫣岣咚惴ǖ那蠼庑阅?。

（1）為每個結(jié)點引入K鄰域以限制螞蟻在選擇轉(zhuǎn)移目標時，只在距當前結(jié)點較近的結(jié)點中選擇。但是可能存在一個結(jié)點的K鄰域中的結(jié)點均處于一只螞蟻的禁忌表中的情況，此時需要另外設計轉(zhuǎn)移規(guī)則，以防止該只螞蟻不能完成回路構(gòu)造。

（2）在“3.2”節(jié)中，刪除結(jié)點和插入結(jié)點時設計有利于算法收斂的規(guī)則。例如，刪除結(jié)點可按節(jié)約最大的原則，即保留重復結(jié)點中的一個而刪除其他所有重復結(jié)點，使刪除后總路徑長度減小最大；而插入結(jié)點可按增加最小的原則，即將在所有路徑中均未出現(xiàn)的結(jié)點插入到一條路徑的恰當位置，使插入后總路徑長度增加最小，如果節(jié)點不惟一時，任選一結(jié)點。

（3）設計有利于算法收斂的信息素更新策略。信息素更新策略是決定蟻群算法收斂與否的重要因素，傳統(tǒng)的信息素更新策略對所有螞蟻遍歷的路徑均增加信息素，而實際上，有些螞蟻遍歷的路徑對最優(yōu)解根本沒有貢獻，這樣導致傳統(tǒng)的信息素更新策略不利于蟻群算法的收斂。在信息素更新時，為了防止邊上信息素的過分懸殊會導致算法快速收斂于局部最優(yōu)解，為此，可以將信息素量限制于特定的范圍內(nèi)，對信息素量大于上限的邊，直接將該邊上的信息素量置為上限，而對信息素量小于下限的邊，直接將該邊上的信息素量置為下限。

（4）啟發(fā)函數(shù)的設計。設計更有利于信息素向存在于最優(yōu)解中的邊集中的啟發(fā)函數(shù)，從而加速算法的收斂速度。

4 引入啟發(fā)式函數(shù)

在蟻群算法的基礎上，采用啟發(fā)函數(shù)中的節(jié)約算法來提高算法的求解性能。節(jié)約算法屬于啟發(fā)式算法[3]，它的基本思想是首先把各個客戶單獨與車場相連，構(gòu)成n條“0→i→0”(i,j=1,2,…,n)，計算連接后費用的節(jié)約值。

s(i,j) 越大，說明把客戶i和客戶j連接在一起時總費用節(jié)約值越多，因此應優(yōu)先連接s(i,j) 值大的點i和j?；谶@一原則，Clarke和Wright在1964年提出C-K節(jié)約算法。約定把只有一個客戶的線路 (如“0→i→0”) 稱為初始化線路，把包含兩個或兩個以上客戶的線路 (如“0→...i→...→0”) 稱為已構(gòu)成線路。

4.1 轉(zhuǎn)移規(guī)則細化

應用節(jié)約算法對蟻群算法進行細化，定義如下形式的螞蟻轉(zhuǎn)移概率[4]：

其中：τij代表邊 (i,j) 上的信息素；ηij表示邊 (i,j) 上的啟發(fā)信息，常取邊(i,j)長度的倒數(shù)，即ηij=1/dij。

應用節(jié)約算法，首先將各點單獨與源點0相連，構(gòu)成1條僅含一個點的線路；然后計算將點i與j在滿足車輛載重量約束的基礎上，連接在同一條線路上的費用節(jié)約值，即μij=di0+d0j-dij，顯然，μij越大，收益越大，而選擇結(jié)點vj的概率也就越大。μij的值需要作最大值和最小值限制，以免μij過大或過小而影響整個路徑轉(zhuǎn)移概率，如,當μij等于0時，轉(zhuǎn)移概率為0，使得整個轉(zhuǎn)移概率公式的其他影響因素失去意義。kij= (qi+qj) /Q是考慮車輛容量約束和車輛載重量利用率而引入的變量。α,β,λ,γ為權(quán)重參數(shù)。p是個隨機數(shù)，取值在 (0,1) 區(qū)間內(nèi)。r0為取值在 (0,1) 區(qū)間內(nèi)的一個固定值。

4.2 信息素更新原則

采用全局更新規(guī)則，當所有螞蟻走完所有的客戶點，也就是完成一次遍歷后，各路徑上的信息素濃度要根據(jù)下式進行調(diào)整：

其中：ρ∈(0,1), (1?ρ)為信息素濃度的衰減系數(shù)，在本次遍歷（t,t+1）時間段中信息素濃度的增量?τij(t,t+1)表示為：

其中：?τij表示螞蟻k在本次遍歷（t,t+1）時間段中留在路徑（i，j）上的信息濃度，可用下式表示：

其中：Q為常數(shù)；Lk表示螞蟻k在本次遍歷中所走過的路徑的長度。

4.3 Min-Max思想的引入

Min-Max蟻群系統(tǒng)(MMAS)是德國學者Stützle等提出的一種ACO算法的改進方案[5]。由于信息素隨時間衰減因素的存在，在搜索陷入局部最優(yōu)時,某段路徑弧段的信息素相對其他路徑弧段的信息素而言,在數(shù)量上占據(jù)絕對的優(yōu)勢，以至于引起算法過早地收斂。因此本算法對各路徑弧段上的信息素,設定了最大和最小值的限制,從而避免了某段路徑的信息素過大或過小。即τij(t)∈τmin,τmax) ，若τij>τmax,則τij=τmax；若τij<τmin,則τij=τmin。

4.4 算法步驟

步驟1:初始化各參數(shù),輸入基礎數(shù)據(jù),給定n個客戶和每個客戶的需求量，得出各需求點之間的距離，將m個螞蟻平均分配到n個需求點，設定α、β、τij（0）車輛的額定載重量、最大循環(huán)次數(shù)Ncmax，計算出ηij,μij,kij的值并存放于相應的數(shù)組中，設置μij的最大值和最小值。

步驟2：將m個螞蟻置于初始點(即配送中心)，并將初始點置于當前解集中。

步驟3：對每只螞蟻k，隨機選擇除初始點外的任意節(jié)點f，并將f置于當前解集中。

步驟4：對每只螞蟻k，根據(jù)不同的p值選取相應的pijk,并根據(jù)剩余載重量選擇下一結(jié)點j,將j置于當前解集中。

步驟5：重復步驟4，直到每只螞蟻都訪問了每一結(jié)點，受到車輛載重量的限制，每只螞蟻將得到若干條由配送中心為起點的回路，每條回路就相當于一輛運輸車所經(jīng)過的路徑。

步驟6：計算每只螞蟻所走過的每條回路的路徑長度，按照全局更新規(guī)則對各邊的信息素進行更新。

步驟7：按照各螞蟻所得到的可行解，得出最優(yōu)解。

步驟8：依式τij(t+1) =ρτij(t) +?τij(t,t+1) 進行信息素的全局更新。

步驟9：Nc=Nc+1，所有螞蟻又回到初始位置，重復步驟2、3、4、5、6、7、8。每次迭代獲得的最優(yōu)解要與前面獲得的解比較，若優(yōu)于之前的解，則替換成當前最優(yōu)解。

步驟10：直至Nc>Ncmax或者出現(xiàn)退化行為(即每次迭代找到的都是相同的解)，則結(jié)束，輸出最優(yōu)路徑及路徑長度。否則轉(zhuǎn)步驟2。

5 應用分析

表1 實例計算結(jié)果

本文參照文獻[6]中的示例利用后的蟻群算法進行優(yōu)化。設某物流中心有5臺配送車輛,車輛的最大載重量均為8 t，一次配送的最大行駛距離均為50 km，需要向20個客戶送貨，物流中心的坐標為(14.5 km，13. 0 km)，20個客戶的坐標及其貨物需求量。

第一次蟻群算法控制參數(shù)為:

第二次蟻群算法控制參數(shù)為:M2=5,Ncmax2=30,τij2=1,τmax2=20,τmin2=1,α2=1,β2=5,Q2=50

程序運行10次，各次搜索結(jié)果如表1所示。

從表1中可以看出，采用本文的算法求解上述VRP均得到質(zhì)量很高的解。其平均配送最小距離為111. 6 km，平均使用的車輛數(shù)為4輛。從計算效率來看，10次求解的平均程序運行時間為345.4ms。在10次求解中，平均與最優(yōu)的差值比最優(yōu)解多3.522%，可見，該算法在求解VRP可得到較好的結(jié)果。算法找到的最好解的配送距離為107.8 km，對應的4條配送路線為I:0→8→19→15→16→13→6→0;II:0→5→14→2→12→9→10→7→1→0;III:0→4→3→17→11→20→0; IV:0→18→0。文獻[6]所設計的混合蟻群算法找到的最好解的配送距離為108.62 km，對應的4條配送路線為I: 0→5→14→2→12→9→10→7→1→0;II:0→8→19→15→16→13→6→0; III:0→18→20→11→17→3→0; IV: 0→4→0。相比之下，本算法能夠找到更好的可行解，比其最優(yōu)解少0.072 1%。

本文在傳統(tǒng)蟻群算法的基礎上，針對傳統(tǒng)算法的不足，引入啟發(fā)函數(shù)中的節(jié)約算法來對蟻群算法進行優(yōu)化，并借鑒Min-Max的思想，使算法得到優(yōu)化，通過實例證明了算法的優(yōu)良性，能夠較好地解決車輛路徑問題，而且計算出來的結(jié)果更穩(wěn)定。

[1] 彭 揚，伍 蓓. 物流系統(tǒng)優(yōu)化與仿真[M]. 北京：中國物資出版社，2007.

[2] 黃天赦，葉春明. 基于混合粒子群算法的車輛路徑優(yōu)化問題研究[J]. 物流科技，2008 (9)：26-27.

[3] 繆興鋒，秦明森. 物流運籌學方法[M]. 廣州：華南理工大學出版社，2007.

[4] 王俊鴻，修桂華. 二次蟻群算法在運輸調(diào)度問題中的應用[J]. 計算機應用與軟件，2008 (7)：71-73.

[5] Stützle T, HoosH. Improvements on the ant system:introducingMax-min ant system[A]. Proc. Int. Con.f ArtificialNeuralNetwork and GeneticAlgorithm,W ien:SpringerWerlag,1997.

[6] 李卓君. 混合蟻群算法求解物流配送路徑問題[J]. 武漢理工大學學報，2006 (2)：306-309.