混合蟻群算法求解帶軟時間窗的車輛路徑問題

李 卓 李文霞 巨玉祥 陳曉明 何曉平

(蘭州交通大學交通運輸學院 蘭州 730070)

0 引 言

車輛路徑問題(vehicle routing problem,VRP)是物流供應鏈研究領域的經典核心問題[1]，帶軟時間窗的車輛路徑問題(vehicle routing problem with soft time window,VRPSTW)是組合優化中在物資送達各客戶點設置了帶有懲罰性質的軟時間窗約束，是經典VRP中的一種變體，現實中快遞配送[2]、應急物資調度[3]、人員救護[4]等路徑規劃問題均可被歸納為VRPSTW問題.

考慮到VRPSTW問題的NP-hard性質，精確算法在求解具有一定規模的問題時已不適用，而啟發式算法在求解大規模VRP問題的適用性凸顯，已被學術界廣泛認可，且不少學者在傳統算法的基礎上進行了改進.范厚明等[5]將變領域下降搜索應用于粒子群算法的擾動，提高了算法的搜索性能，并將其應用于求解同時集配車輛路徑問題.郭詠梅等[6]針對應急物流背景下的車輛路徑問題，將人工魚群算法中擁擠度因子引入蟻群算法來指導蟻群的聚集，提高了算法性能.值得注意的是，蟻群優化算法在計算復雜性和收斂速度方面比較適用于求解VRP及其變體問題，且解的質量不依賴于解的初始化，具有較好的魯棒性[7]；然而，由于蟻群算法較強的自組織性和正反饋性，表現出良好收斂性的同時易陷入局部最優，因此，部分學者通過引入領域搜索[8-9]、精英保留策略或混合其他經典啟發式算法優勢[10-11]來改進蟻群算法.近些年來，隨著新興群智能優化算法的興起，不少學者考慮將其應用于各自的研究領域[12]，其中螢火蟲算法在許多連續型優化問題中表現出較好的性能[13].由于VRP的離散特性，螢火蟲編碼與解碼是關鍵環節，已有文獻考慮到該問題并對算法進行了改進.孫俊成等[14]對解決連續問題的螢火蟲算法進行離散化改進，以適應于開放式車輛路徑問題的求解.既有研究表明，螢火蟲算法全局搜索能力較強，但獲得解的質量高度依賴于解的初始化，算法穩健性和收斂性較差.

綜合上述蟻群算法和螢火蟲算法的優勢與不足，為混合算法設計提供了思路.基于此，考慮兩種算法的優勢互補，將二者結合設計一種混合算法，算法應用于VRPSTW模型的求解，以期保持求解效率的同時提高求解精度.

1 VRPSTW描述和數學模型

1.1 問題描述

基于物流體系中的末端配送，可歸結為帶軟時間窗的車輛路徑問題(VRPSTW).具體而言，一個物資調度中心，配有足夠數量的同質車輛，路網中有一組客戶需求點，每個客戶的需求量和服務持續時間必須滿足，考慮盡可能滿足客戶服務時間窗的同時合理規劃車輛路徑，使總配送成本最小.

需要解決的問題及基本假設：①車輛從物資調度中心出發，服務若干客戶需求點后返回調度中心；②每個客戶點僅由一輛車訪問且只能被訪問一次，其需求量不能超過車輛容量；③車輛為相同車型且運輸總量不能超出中心容量限制；④每個客戶的坐標、需求量和服務持續時間已知，且都有服務時間窗限制.

1.2 數學模型

1.2.1模型參數

運輸網絡G=(V,A)，主要參數及相關變量見表1.

表1 模型參數及變量

1.2.2模型構建

參照傳統車輛路徑問題的優化方向，以配送總成本最小為目標，構建帶軟時間窗的車輛路徑優化模型.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Tik+ui+tijk≤Tjk+C(1-xijk),

?i,j∈V0,k∈K

(8)

xijk∈{0,1},?i,j∈V,k∈K

(9)

Qk,qi,ui>0,i∈V0,k∈K

(10)

式(1)為最小化配送成本的目標函數；式(2)～(3)為每個客戶需求點僅被一輛車服務且僅訪問一次；式(4)為子回路消去約束；式(5)為車輛從調度中心出發最終返回調度中心；式(6)為節點平衡約束；式(7)為車輛容量限制；式(8)為車輛從服務上一需求點到訪問下一需求點所要滿足的時間條件；式(9)～(10)為決策變量和參數約束.

2 求解VRPSTW的混合蟻群算法

VRPSTW問題是經典VRP問題的子問題之一，被認為是NP-hard問題.由于該問題的求解規模較大，精確算法無法解決指數爆炸問題，難以求得最優解.而傳統啟發式算法求解VRP問題已得到廣泛應用，如遺傳算法、蟻群算法、禁忌搜索和模擬退火等均表現出良好的求解效果.因此，通過設計改進的啟發式算法以求解VRPSTW問題.

2.1 蟻群算法

(11)

式中：α為信息素重要度因子；β為啟發式信息重要度因子；alloweds=V/{tabus}為螞蟻s下一步允許訪問的節點集合，tabus為螞蟻s訪問過的節點集合，即路徑禁忌表.

啟發式函數ηij(t)越大，螞蟻選擇節點j的概率越大.隨著迭代次數的增加，路徑(i,j)的信息素濃度τij不斷疊加，同時殘留的信息素將持續揮發，則(t+1)時刻路徑(i,j)的信息素τij(t+1)濃度更新規則為

(12)

式中：ρ為信息素揮發系數；Q為全局信息素常量；由于模型目標是成本最小，則cost(i,j)為路徑(i,j)上的成本.

2.2 螢火蟲算法

螢火蟲算法(firefly algorithm,FA)將搜索空間的每個可行解模擬為自然界中的螢火蟲個體，將迭代搜索過程模擬為螢火蟲個體間的吸引和移動過程.其基本原理涉及兩個主要因素：種群個體的發光亮度和個體間的相互吸引度.發光亮度與個體的適應值有關，適應值越好，亮度越強；吸引度與發光亮度成正比，與個體間的距離成反比；亮度更高的螢火蟲吸引種群中其他個體朝著其搜索領域內更優的位置移動，以此來完成優化過程中螢火蟲個體位置的更新.

個體i的發光強度Ii用適應值表示，適應函數一般為目標函數，表示為

Ii=f(Xi),Xi=(xi1,xi2,…,xid)

(14)

若個體i的亮度大于個體j，則螢火蟲i對螢火蟲j的吸引度βi,j隨距離變化

(15)

式中：β0為最大吸引度，即光源處(r=0)；γ為光吸收系數，γ∈[0.01,100]；ri,j為個體i與個體j間的歐式距離.

個體j被個體i吸引，位置更新公式為

Xj(t+1)=Xj(t)+

βi,j(Xi(t)-Xj(t))+α

(16)

式中：α為隨機控制參數，α∈[-1,1].

2.3 螢火蟲-蟻群混合算法

蟻群算法在VRPSTW問題中得到成功的應用[15]，由于其具有較強的信息反饋機制，對大規模問題具有較高的求解效率，但當迭代后期信息素濃度過高時易產生信息素停滯，導致過早收斂，從而陷入局部最優.針對此問題，考慮螢火蟲優化中較劣個體自組織性地向較優個體的移動，促使種群在向優勢個體聚集的過程中完成個體位置的迭代更新，在此過程中能搜索到新的解空間.基于此，提出將以上螢火蟲個體間的尋優過程引入蟻群優化，綜合二者的優勢提出螢火蟲-蟻群混合算法(ACO_FA)，以期在每次迭代中產生額外的滿意解，用來進行螞蟻信息素擾動，避免信息素的停滯，改善算法過早收斂的情況并跳出局部最優.

算法以蟻群算法為基本框架，將螢火蟲個體的尋優過程用于擴大搜索的解空間，通過控制迭代過程中信息素的聚集，提出一種信息素交換過程(以下簡稱FA搜索過程).算法流程見圖1.

圖1 算法流程圖

2.3.1FA搜索過程

提出的算法首先調用蟻群算法，構造各次迭代的可行解集，然后調用FA搜索過程，對得到的額外的可行解集進行擇優處理后與原可行解集結合，來更新路徑上螞蟻信息素濃度.

由于VRPSTW問題是離散優化問題，而螢火蟲算法在求解連續型問題更為適用，因此，為了使螢火蟲適應離散優化問題，提出對初始可行解進行重新編碼與解碼，以此將螢火蟲算法應用于離散優化問題中.

1) 螢火蟲編碼 蟻群算法構造各代的初始可行解s；將整數1～n(n為客戶數量)按升序形成序列sq1=(0,1,2，…，n)；將蟻群算法中得到的可行解s與序列sq1一一對應后，sq1按可行解s中客戶序號升序排列，得到客戶點1～n的訪問次序sq2，即編碼的螢火蟲個體.

2) 位置更新 通過上述編碼方式對可行解集進行螢火蟲編碼，并按式(14)計算各個螢火蟲個體的發光強度，例如個體i被編碼為216354，個體j被編碼為315462，且個體i的亮度大于個體j，計算個體間各元素的距離，見圖2，rij=6.按式(15)～(16)進行螢火蟲個體各元素位置的更新，形成新的序列sq3，即新的螢火蟲個體.

圖2 螢火蟲個體間的距離

3) 螢火蟲解碼 更新后，序列sq3可能出現非整數或負數，對其進行合法化處理：序列sq1與sq3一一對應后，序列sq1按序列sq3升序排列得到序列sq*；判斷sq*是否可行，即是否滿足模型約束，滿足，則輸出，否則，進行插入1(客戶點)操作修復不可行解，以此得到FA搜索后的可行解，見圖3.

圖3 FA搜索編碼與解碼

由圖3可知，原可行解為261 435，經過FA搜索，更新過的可行解為261 453，在向最優個體移動的過程中，原可行解進行了領域搜索，改善了解的多樣性.

2.3.2全局信息素更新

對經過FA搜索后獲得的可行解集執行精英保留策略，得到的優勢解與原可行解集共同用于更新路徑信息素濃度，在弧段上沉積信息素，以指導后來螞蟻的路徑尋找機制.路徑(i,j)的信息素濃度τij(t+1)按下式更新：

(17)

(18)

3 算例分析

3.1 實驗設置

算例的實驗數據通過Matlab隨機生成一個配送中心和19個客戶點.所有客戶點隨機分布在(0,70)2的平面坐標內；客戶需求是區間[0,20]隨機產生的整數(t)，時間窗等其他信息見表2；車輛行駛速度v=2 km/min；單車載重60 t；客戶單位需求量的服務時間為1 min/t；單位距離成本為5元/km.提出的算法相關參數見表3.

表2 客戶信息表

表3 提出的算法相關參數

3.2 模型計算結果及分析

對于混合蟻群算法的性能，以軟時間窗條件下的配送總成本最小化為目標，通過Matlab軟件編寫程序，在相同的參數設置及實驗條件下，分別對傳統蟻群算法與文中提出的混合算法進行500次迭代，并針對給定的數值實驗分別運行10次程序，統計結果見表4.

所有算法在一臺搭載1.6 GHz的Intel Core i5處理器和4 GB內存的計算機平臺上實現，算法收斂曲線和模型優化結果見圖4～5.

表4 ACO_FA算法與ACO算法數值實驗統計結果

圖4 ACO_FA算法與ACO算法收斂曲線對比

圖5 ACO_FA算法優化結果

由表4可知，混合算法相較于傳統蟻群算法在解的準確度上有顯著提高，全局最優解優化了約15.4%，全局平均解優化了約15.6%，反映出算法在優化過程中解決了螞蟻信息素停滯的弊端，避免陷入局部最優狀態；其次，解的平均偏差降低了約0.21%，最大偏差降低了約0.48%，說明算法在提高最優解質量的同時，對算法的穩健性也有改善，表現出良好的求解性能.由于提出的算法在原有蟻群算法的基礎上增加了FA搜索過程，故需要在領域搜索中花費額外的時間，因此，在計算中需要更多的時間.

不同于一般領域搜索的隨機性擾動，算法中的FA搜索過程是有方向的領域搜索，是以本次迭代種群中較優解為目標進行擾動，改善每代可行解多樣性的同時，使搜索過程更有目的性，加快算法的收斂，以期在保持原有的求解效率的同時提高求解準確度.由圖4可知，此算法在迭代177次時達到最優，蟻群算法在迭代158次時達到最優，基本保持了良好的收斂性.

顯然，此模型可以有效的解決帶軟時間窗的車輛路徑問題.配送中心在車輛有限載重的條件下，盡可能滿足客戶時間窗的同時，使總成本最小，配送最低成本為3 342元，配送路徑1為1-14-2-16-4-5-9-3-1，車輛滿載率為100%；配送路徑2為1-7-6-10-18-8-1，車輛滿載率為95%；配送路徑3為1-15-11-12-17-13-1，車輛滿載率為88.33%；配送路徑4為1-20-19-1，車輛滿載率為43.33%.

4 結 論

1) 考慮到蟻群算法在迭代過程中的信息素停滯問題，將螢火蟲算法中螢火蟲的尋優機制引入蟻群算法，有目的性的擴大搜索的解空間，保持每代解具有多樣性，以此來優化螞蟻信息素濃度的更新機制，克服了陷入局部最優的瓶頸，最終提高解的精確度，并且在一定程度上保持了原有算法的求解效率.

2) 改進蟻群算法在精確性上有顯著提高，在算法穩健性也有較大改進.僅考慮了單目標蟻群算法的性能，設計求解多目標優化問題的蟻群算法將是下一步研究方向.