求解帶時間窗車輛路徑問題的改進型煙花算法

牛群，劉 軍

(蘭州理工大學 機電工程學院，甘肅 蘭州 730050)

0 引言

車輛路徑問題(vehicle routing problem，VRP)由DANTZIG和RAMSER于1959年在研究卡車配送汽油行駛路徑問題時提出。當前VRP考慮實際生活中的約束，在基本VRP上增加客戶配送的時間窗要求，并提出帶時間窗車輛路徑問題(vehicle routing problem with time windows，VRPTW)，更貼近實際情況。

VRP自提出以來就受到廣泛關注。EKSIOGLU總結出常用求解方法可分為解析算法和啟發式算法[1]。解析算法包括分支界定法、動態規劃法等。由于VRP是NP-hard問題[2]，計算時間會隨著客戶數增多呈指數級增長，在實際應用中受限。啟發式算法在可接受的計算成本內能找到近優解，使用迭代方式實現尋優過程，通過反饋信息，根據搜索規則及時更新并縮小搜索范圍，當解或迭代次數達到預設值時終止。目前啟發式算法分為構造啟發式、改進啟發式和元啟發式。

G. CLARK和J.R.WRIGHT[3]的經典節約算法，GILLET[4]的高效掃描算法，SOLOMON[5]的插入啟發式、節約啟發式、鄰近啟發式等，都是根據相應插入準則，將客戶迭代地插入到當前可行路徑中，直到所有客戶都被安排。構造啟發式算法在解的質量上存在差距。LIN[6]的2-OPT和3-OPT算法，在插入過程暫時接受不可行解，然后改進使其可行。改進啟發式在構造啟發式的初始解的基礎上改進，擴大了初始解的搜索空間。改進型啟發式算法易陷入局部最優。為跳出局部最優，對搜索空間多樣化探索，發展了遺傳算法[7]、蟻群優化[8]和煙花算法[9]等算法。GILLETT[10]用自適應文化基因算法來求解VRPTW，并與遺傳算法作了比較。

當前煙花算法與其改進算法已被廣泛應用，例如油料作物施肥問題與電力系統重構問題[11]等，但在VRPTW中應用不多，本文將煙花算法用于求解VRPTW，為解決此類問題提供新思路。

1 帶時間窗的車輛路徑問題

基于VRP相關理論的基本假設：1) 對客戶僅進行送貨；2) 客戶需求量及時間窗一定；3) 每個客戶僅被一輛車服務一次；4) 給定配送中心及客戶位置；5) 車輛具有相同載重；6)車輛不得超過最大載重；7) 每個客戶在指定時間窗內進行，超過則不可行或加以懲罰；若早到需等待；8) 只有一個配送中心，車輛從配送中心出發并最終返回；9) 所有道路均暢通，不考慮突發情況。

VRPTW模型如下：用有向圖G=(C,E)定義，由客戶集C={0,1,2,…,n,n+1}和弧集E組成。節點0和n+1代表配送中心，其他n個頂點集合記為N。每個客戶i(i∈N)需求為di，服務時間為si和時間窗[ei，li]，ei和li分別代表最早和最晚開始時間。假設車速=1，則行駛距離等于行駛時間。tij表示客戶i到客戶j(i,j∈N)的行駛距離；Cij代表車輛每條弧的成本。引入決策變量x和s，車輛k從客戶i行駛到客戶j(i≠j,i≠0,j≠n+1)，則決策變量xijk等于1，否則為0。決策變量sik表示車輛k開始為客戶提供服務的時間。

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

sik+tij-(1-xijk)k=sjk,?jN,?iN,?kK

(8)

ei≤si≤li,?iN

(9)

目標函數式(1)表示最小化配送總成本；式(2)為確保每輛車需求總和不超過其最大載重； 式(3)-式(6)表示保證每輛車從配送中心離開，在服務完客戶后返回配送中心；式(7)表示保證每個客戶被一輛車服務一次；式(8)表示車輛從客戶i行駛到客戶j，不能在sik+tij之前到達客戶j；式(9)表示確保滿足所有時間窗。

2 求解VRPTW的改進型煙花算法

譚營在2010年提出煙花算法，通過模擬煙花爆炸行為建立相應模型。其思路是將初始生成煙花看作解空間中部分可行解，煙花爆炸生成火花過程類比為在原有煙花的鄰域搜索過程，爆炸半徑為相鄰煙花位置的選擇。通過煙花適應度值的信息交互，煙花對應的適應度值大，則在較大范圍內生成較少火花，擁有全局搜索能力；反之，適應度值小，在較小范圍內生成更多火花，具備更強局部搜索能力。

2.1 解決方案表示

在求解時，用一維向量表示解決方案，每一個數字代表一個客戶，解決方案的長度代表客戶總數，路徑數量等于“0”的個數減1。在圖1中，第一條路徑有3個客戶，第2、第3條路徑都有2個客戶。

圖1 解決方案表示

2.2 適應度評估函數

通過適應度評估個體質量優劣，因VRPTW是多目標優化問題，所以用加權求和將其轉化為單目標優化問題。適應度F(x)計算如下：

(10)

(11)

加權系數α和β分別是車輛數及行駛距離的權重參數。根據經驗確定為α=100，β=0.001。

2.3 爆炸產生火花數

對于每個煙火xi(對應問題解決方案)，生成火花數量需在爆炸之前計算。為使煙花差異化，根據適應度值來控制爆炸產生火花數目。公式如下：

(12)

其中：Ni為第i個煙花的火花數量；M是限制火花數量常數；Ymax是當前種群適應度最大值；f(xi)是個體xi適應度值；ε是避免分母為0的極小常數值；其中M為50，N為5。由于生成火花數是一個整數，因此通過式(13)將其轉換為整數，其中a為0.04，b為0.8。

(13)

2.4 爆炸操作

爆炸算子是將進行爆炸的煙花與目前存在的煙花及最優個體進行交叉重組產生新的火花。用示例給出解釋：p1為等待爆炸煙花，p2代表所有煙花及火花中最優個體。p1的3條路徑R1為4—8—2—9，R2為1—7和R3為3—5—6。步驟a)：從p1中選擇R2，p2中選擇R3。將給定個體在所選路徑中移除，在p1中移除5和9，產生C1。同樣，在p2中移除5和6，生成C2。步驟b)：將5和9重新插入到C1，同時將1和7重新插入到C2。首先插入哪個是隨機的，若插入之后路徑不滿足約束，則插入點不可行。步驟c)：5和9都被插入到C1中恰當位置。若沒找到可行插入點，則建立一條新路徑。客戶7沒有被插入到p2當前路徑中，因此創建新路徑。爆炸操作示意如圖2所示。

圖2 爆炸操作示意圖

自適應爆炸半徑核心是使用已產生火花來計算最優煙花的爆炸半徑，通過這一代信息來計算下一代最優煙花的半徑。自適應半徑是一種全新的控制步長方式，爆炸半徑是否具有自適應能力對算法性能至關重要。公式如下：

(14)

自適應半徑的計算，首先選擇一個個體，用它與最優個體之間的距離作為下一次爆炸半徑。必須滿足條件：1) 適應度值比這一代的煙花差；2) 到最優個體的距離是滿足1) 的個體中最短的；3) 確保目標函數至少比這一代進步要大，在下一次爆炸中找到更好位置；4) 確保半徑收斂。雖然無法保證半徑每次都減小，但當迭代次數足夠大、火花數量足夠多時，還是收斂的。

將計算的自適應半徑乘以特定系數λ=1.3(經驗值)以控制全局和局部搜索的平衡，A(g+1)←λ·A(g+1)，λ過小會過快收斂，λ過大將不會收斂。為減少火花數量有限的影響，采用簡單平滑機制A(g+1)←0.5·[A(g)+A(g+1)] ，將計算的自適應半徑和該代爆炸半徑的平均值作為下一代爆炸半徑。

2.5 變異操作

引入變異火花加強種群多樣性，變異算子主要作用是增強局部搜索能力，免于陷入局部最優。在此采用高斯變異火花位置，計算如下：

(15)

其中g是服從均值為1、方差為1的高斯分布的隨機數。

2.6 選擇策略

用基于距離的選擇策略選出剩余N-1個個體組成下一代群體。算法的分布式信息共享機制，是基于免疫濃度思想的選擇，使煙花分布在不同區域不聚集來避免早熟。采用歐氏距離度量兩個個體之間距離：

(16)

其中：d(xi，xj)表示任意兩個個體xi和xj之間的歐氏距離，R(xi)表示個體xi與其他個體的距離之和；K是由爆炸算子產生的火花位置和高斯變異產生的火花位置的集合。個體選擇采用輪盤賭的方式，個體被選中的概率p(xi)表示為：

(17)

得出個體距離更遠的個體具有更多的機會成為下一代個體，此選擇方式保證了算法的種群多樣性。

3 實驗結果與分析

通過對Solomon數據集的測試來驗證改進型煙花算法對VRPTW求解的適用性和有效性。此數據集包含100個客戶點，分為R1、R2、C1、C2、RC1和RC2 6個子類。C類在地理位置上是聚類的，R類是隨機的，RC是兩種情況的混合。對于R1、C1和RC1類問題，車輛載重小且時間窗緊，每輛車服務較少客戶；相反，R2、C2和RC2具有大載重和寬松時間窗，每輛車服務較多客戶。算法采用Matlab2014a編程，在Intel Core i5-3240MCPU@3.40GHz雙核處理器，操作系統為32位的Windows7環境下運行。

用車輛數和行駛總里程評價最優解，通常固定成本高于運輸成本，因此最小化車輛數優先級高于最小化行駛總里程，本文選取部分計算結果與已公布最優解比較。表1和表2得到的距離改進顯著，但以增加額外車輛為代價，如R103和RC102。在R2及RC2中，車輛數大多等于當前最優解，但行駛總里程得到很好優化，如R204和RC207。算法的群體多樣性使得算法跳出局部極值收斂到全局最優，另外自適應半徑作為時變趨化步長使得局部搜索與全局搜索達到適應性平衡，在搜索時首先從有前途的鄰域開展全局搜索，然后減慢開展局部搜索，從而得到最優解。

表3是IFWA的平均表現。通過比較表3、表1及表2，發現10次的平均結果與最優解相差不大，且平均結果都在可接受范圍內，說明算法求解整體性能穩定。對解質量而言，使用該算法求解VRPTW具有可行性和有效性。在爆炸和變異算子作用下，根據煙花適應度值產生不同個數的火花和不同的爆炸半徑，保證火花個數和爆炸半徑的多樣性；高斯變異保證爆炸的多樣性；通過選擇策略保留的煙花保證煙花的多樣性，以上群體多樣性的3個方面確保算法全局收斂。算法采用動態信息策略，保證在每次搜索中每個煙花都對搜索作出貢獻，以達到快速尋優。

表1 IFWA與硬時間窗最佳公布結果比較

表2 IFWA與軟時間窗最佳公布結果比較

表3 所羅門基準下的IFWA平均表現

4 結語

通過模擬煙花爆炸行為，設計了一種改進型煙花算法。求解帶時間窗車輛路徑問題。在迭代過程中通過優化控制策略對爆炸半徑提出改進，使得爆炸半徑實現自適應量化，有效提升算法的局部搜索能力。算法的分布式信息共享機制還避免了早熟。通過對測試算例與已知最優解比較，表明改進型煙花算法具有較好的求解精度，能夠有效處理帶時間窗車輛路徑問題。

研究表明，改進型煙花算法在VRPTW上的成功應用拓寬了實際應用領域，為求解實時動態、復雜VRP問題提供了新思路。在此基礎上，進一步考慮實際生活中客戶需求的動態變化、道路實際交通情況等影響因素，將會是下一步研究重點。