基于改進(jìn)蟻群算法的逆向物流車輛路徑優(yōu)化

陳秀娟，高更君，馮媛媛

（上海海事大學(xué) 物流研究中心，上海 201306）

0 引言

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

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

1 VRPRL問題描述

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

圖1 回收示意圖

2 VPRL模型建立

2.1 模型假設(shè)及參數(shù)設(shè)定

2.1.1 模型假設(shè)

1）回收中心和客戶點坐標(biāo)已知；

2）各客戶點回收量已知，均不會超過一輛車的標(biāo)準(zhǔn)載容量；

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

4）回收貨物類型相同；

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

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

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

2.1.2 參數(shù)定義

0：配送中心；

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

m：客戶數(shù)量；

n：車輛數(shù)量；

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

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

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

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

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

2.2 模型建立

根據(jù)上述VPRL問題描述，基于參數(shù)設(shè)定和模型假設(shè)，構(gòu)建VRPL模型如下：

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

3 模型求解

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

3.1 改進(jìn)蟻群算法

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

3.1.1 改進(jìn)信息素更新策略

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

信息素更新規(guī)則如下：

其中：

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

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

信息素更新前：

信息素更新后：

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

3.1.2 改進(jìn)啟發(fā)因子

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

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

基于局部，定位全局，尋找最優(yōu)解。

3.1.3 2-opt算法

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

圖2 2-opt示意圖

3.2 算法步驟

根據(jù)改進(jìn)蟻群算法，設(shè)計具體實現(xiàn)步驟如下：

1）從文件中導(dǎo)入回收中心和客戶點的坐標(biāo)等基礎(chǔ)數(shù)據(jù)；

2）初始化蟻群各參數(shù)；

3）迭代次數(shù)nc=nc+1；

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

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

選擇下一個客戶點；

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

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

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

9）循環(huán)執(zhí)行3）～8），判斷循環(huán)次數(shù)是否超過ncmax,若不超過，則轉(zhuǎn)步驟3）；若超過則跳轉(zhuǎn)到步驟10）；

10）計算循環(huán)迭代ncmax后所得到的最短路徑長度和最短路路徑，得出算法結(jié)果并輸出最優(yōu)解路徑，算法終止，輸出最優(yōu)路徑長度。

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

4 實例驗證

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

表1 客戶及回收中心基礎(chǔ)數(shù)據(jù)

本文根據(jù)設(shè)計算法，運用Java語言編程求解，在win8 64（intel(R)Core?i7-7500U CPU @2.70GHz處理器）系統(tǒng)下運行時間約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。最優(yōu)回收方案如下表2所示。文獻(xiàn)[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 最優(yōu)回收方案

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

圖3 算法收斂圖

5 結(jié)論

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