基于改進蟻群算法的逆向物流車輛路徑優化

陳秀娟，高更君，馮媛媛

（上海海事大學 物流研究中心，上海 201306）

0 引言

在提倡節約型社會，大力發展循環經濟的趨勢下，供應鏈閉環管理視角下的逆向物流得到了國內外業界專家的普遍重視。逆向物流車輛路徑問題（Vehicle routing problem in reverse logistics，VRPRL）是派車和路徑優化的整合，一直以來都是逆向物流領域中的熱點問題，研究如何優化逆向物流車輛路徑具有重要的理論及經濟意義。

目前很多學者對路徑優化問題已有一定深入研究，例如，Thibaut Vidal等[1]用一種混合遺傳算法解決帶時間窗的VRP問題；Chao[2]利用禁忌搜索算法求解了多車型的VRP問題；劉志碩等[3]提出基于可行解兩階段構造策略的自適應蟻群算法求解VRP問題。這些啟發式算法在解決車輛路徑問題上都取得了一定成果，但也有不足，例如遺傳算法可行解質量一般，禁忌搜索算法過于依賴初始解。蟻群算法憑借其魯棒性和搜索較好解強的特點在解決車輛路徑問題方面備受青睞，但蟻群在解決大規模問題時，也有一定局限性。對此，很多學者在逆向物流車輛路徑優化中對基本蟻群算法進行了改進。劉艷秋等[4]提出逆選擇操作蟻群算法，對蟻群概率選擇進行改進，考慮到物流節點間存在不可行路徑的問題，但未涉及信息素更新方式和啟發因子的改進；胡天軍等[5]解決回程取貨逆向物流車輛路徑問題時，吸收外激素平滑思想，減少信息素各邊差異性，有利于產生新的搜索路線，但頻繁更新局部信息素的方式降低螞蟻的收斂速度；于雷等[6]在信息素更新方面融合并行思想，擴大了解的范圍，但啟發因子的設置只考慮到局部，不利于整體尋優；陳迎欣等[7]提出混合改進蟻群信息素更新的策略，但更新方式非動態，忽略了迭代次數增多的影響。基于此，本文擬提出動態改進信息素更新方式和啟發因子的新思路，兩者同時分階段進行，有機結合，再結合2-opt算法進行優化，以期更高效準確地解決逆向物流回收路徑問題。

1 VRPRL問題描述

逆向物流是一種包含退貨、維修、廢棄處理、等流程的物流活動，主要分為退貨逆向物流和回收逆向物流兩大類。本文主要研究的是廢舊產品通過再循環、再生產從而重新再利用的回收逆向物流。在這一物流系統中，客戶向逆向物流中心（以下簡稱“回收中心”）發出大批回收訂單，回收中心接收訂單并根據各個客戶點的回收量，合理規劃路線，安排車輛到各個客戶點回收物資，并返回回收中心。本文研究對象為一個回收中心，n個回收客戶，m輛車。問題目標是在滿足回收要求的前提下，合理調度車輛，最小化車輛總行程。回收基本示意圖如圖1所示。

圖1 回收示意圖

2 VPRL模型建立

2.1 模型假設及參數設定

2.1.1 模型假設

1）回收中心和客戶點坐標已知；

2）各客戶點回收量已知，均不會超過一輛車的標準載容量；

3）每個客戶點必須被且只能被一輛車服務一次；

4）回收貨物類型相同；

5）路況對車輛的行駛距離沒有影響；

6）回收中心的車輛型號相同，數量充足，每次回收任務行駛里程均不超過車輛最大行駛距離；

7）回收中心的容量足夠大。

2.1.2 參數定義

0：配送中心；

Z：遍歷所有客戶行駛的總距離；

m：客戶數量；

n：車輛數量；

dij：客戶i,j之間的距離，dij=dji；

qi：客戶i的回收量，q0=0；

Q：每輛車的最大裝載量；

xijk：0-1變量，車輛k由客戶vi出發后開向vj取值為1；否則取值為0；

yik：0-1變量，車輛k服務客戶點i時取值為1；否則取值為0。

2.2 模型建立

根據上述VPRL問題描述，基于參數設定和模型假設，構建VRPL模型如下：

上式中，式(1)式為目標函數，求最小化行程；式(2)表示車輛載重約束，每個客戶點的回收量都不能超過車的標準載容量；式(3)保證每個客戶有且僅有一輛車為之服務；式(4)保證每輛車服務完某客戶點后必須離開；式(5)和式(6)是變量取值。

3 模型求解

自然界中螞蟻的初始運動是隨機的，他們通過感知彼此釋放的信息素濃度進行交流，并根據濃度大小選擇下一步的運動方向，濃度越高表示距離越短，最后在正反饋作用下螞蟻總能找到從蟻穴到食物源的最短路徑。蟻群算法憑借其尋找較優解能力強和穩健性優的特點在優化車輛路徑問題方面頗有優勢，但蟻群在求解大規模問題時計算效率不高，容易陷入局部最優，針對其不足，本文對基本蟻群算法做一些改進。

3.1 改進蟻群算法

采用“可行解先行策略”，每只螞蟻都遍歷所有點，均構造一個可行解，在保證解空間存在及豐富的情況下，對信息素更新策略和啟發因子進行動態改進，再對較優解利用2-opt算法優化，以期提高螞蟻搜索質量，避免陷入局部最優。

3.1.1 改進信息素更新策略

基于文獻[8]混合策略“實時更新和全局更新”的啟發，本文考慮到蟻群迭代次數對算法的收斂性起重要作用，只將第10次作為實時更新和局部更新的切換點，不能更好得研究迭代次數更新的影響。本文將兩者“動態”結合，20次一循環，前10次循環，區別于文獻[8]選取本次循環中最優的可行解，均采用本次循環中所有螞蟻搜索回路中的最短回路進行信息素更新，更好地引導螞蟻進入優質循環中，找到更多可行解；后10次循環時，可以提高收斂速度，找出螞蟻循環以來的最短的可行解進行信息素的更新，對最優解進一步搜索。這種局部與全局更新動態結合的策略，很大程度上避免了算法收斂過慢以及陷入較差解的情況。

信息素更新規則如下：

其中：

f(Sbest)表現本次迭代的最短回路Sib或者全局最優解Sob。

借鑒MIN-MAX思想，將各路徑上的信息素濃度限定在某固定的范圍內，減少濃度差距，避免算法陷入局部最優。

信息素更新前：

信息素更新后：

其中，L(Sbest)表示全局最優解或本次迭代最短回路，1/L(Sbest)表示每次迭代路徑上新增的信息素最高值。

3.1.2 改進啟發因子

啟發函數的作用是幫助螞蟻以更大的概率選擇較短路徑。目前大多文獻采用以下三種方法：一種僅考慮局部因素（兩點間距離）；第二種僅從全局最優解出發（配送中心和下一個目標城市距離）；第三種是將局部和全局結合起來考慮。前兩種方法都有局限性，第三種考慮比較全面，但是一開始限制因素太多，容易過早陷入局部最優解，不利于整體尋優。本文啟發因子結合信息素更新規則，動態調整，20次一循環，前10次循環，啟發函數設為：

其中dij為i、j之間的距離，這校利于擴大解空間，增強蟻群搜索能力；后10次循環，啟發函數設為：

基于局部，定位全局，尋找最優解。

3.1.3 2-opt算法

2-opt算法是在蟻群算法求得的原始解基礎上，交換所得解的兩邊，再將新解和原始解進行比較，新解更優則保留，反之舍棄。一直循環代替，直至完成。為減少工作量，降低算法效率，每只螞蟻完成搜索后，將全部螞蟻走過的路徑長度按降序排列，對后1/2的路徑利用2-opt算法優化。基本示意圖如圖2所示。

圖2 2-opt示意圖

3.2 算法步驟

根據改進蟻群算法，設計具體實現步驟如下：

1）從文件中導入回收中心和客戶點的坐標等基礎數據；

2）初始化蟻群各參數；

3）迭代次數nc=nc+1；

4）隨機將m只螞蟻放在n個城市上，初始化禁忌表tabuk和候選點集allowedk；

5）判斷allowedk是否為空,若為空則跳到步驟10；否則判斷allowedk表中剩余節點的回收量是否大于車輛的剩余載重量，假如車輛k的剩余載重量不能滿足任何節點，則回到回收中心重新出發；假如存在滿足的節點，則根據概率公式：

選擇下一個客戶點；

6）螞蟻從i點出發到j點時，計算車輛k到客戶點i后的剩余載重量；同時修改tabuk；

7）所有螞蟻都找到一條包含所有節點的可行路徑后，對路徑長度進行降序排列，選取后1/2進行2-opt局部搜索，更新螞蟻此次的最優路徑長度和迄今為止最優路徑；

8）計算Int（ncmax/20），若為奇數，則局部進行信息素更新；反之，按照全局信息素更新；

9）循環執行3）～8），判斷循環次數是否超過ncmax,若不超過，則轉步驟3）；若超過則跳轉到步驟10）；

10）計算循環迭代ncmax后所得到的最短路徑長度和最短路路徑，得出算法結果并輸出最優解路徑，算法終止，輸出最優路徑長度。

根據此算法可通過Java語言編程求解得到車輛完成回收任務的最短行駛距離。

4 實例驗證

為了方便比較和驗證算法的有效性，本文采用文獻[8]的逆向物流回收實例代入模型進行計算。該回收中心的車輛種類統一，車輛標準載容量為12t，回收中心與客戶點，客戶點與客戶點之間的距離為兩點間歐式距離，有1個回收中心和20個客戶點，回收中心與客戶點數據如表1所示。采用運行參數如下：M=60，α=1，β=2，ρ=0.5。

表1 客戶及回收中心基礎數據

本文根據設計算法，運用Java語言編程求解，在win8 64（intel(R)Core?i7-7500U CPU @2.70GHz處理器）系統下運行時間約0.1s，得到車輛的最短行駛距離為468.967km，車輛回收路徑為0-12-13-15-11-14-10-0-1-2-3-4-5-18-0-19-16-20-17-0-8-7-6-9-0。最優回收方案如下表2所示。文獻[8]利用基本蟻群算法，求解車輛回收路徑最短距離479km，回收路徑為：0-1-2-3-4-5-0-8-7-6-9-10-0-14-11-15-13-12-0-17-18-20-16-19-0。

表2 最優回收方案

改進的蟻群算法求解結果相比基本蟻群求解結果，優化了10.003km。由圖3可知，由最短距離趨勢圖可以看出，本文算法首次搜索到最優解的迭代次數為140次，收斂速度較快；從平均距離趨勢圖可以看出，均值大多低于479km，即優于文獻[8]的最優解，且整體逐漸呈平穩趨勢，解的質量越來越佳并趨于穩定。

圖3 算法收斂圖

5 結論

逆向物流車輛路徑優化是逆向物流領域研究的重難點。有效提高物流回收效率，減少車輛行駛距離以降低物流回收成本，彰顯逆向物流的經濟價值，對整個社會的綠色發展具有重大意義。本文針對基本蟻群算法進行動態改進，混合2-opt算法，實驗結果表明改進的蟻群算法不僅尋優能力強，收斂速度快且結果比較穩定，對解決逆向物流車輛路徑問題有一定參考價值。