基于改進遺傳算法的冷鏈物流路徑優化研究*

□ 解玉蝶

(江南大學 商學院，江蘇 無錫 214122)

1 緒論

十三五規劃指出“要大力發展城鄉配送、冷鏈物流、第三方物流和綠色物流”，這代表著冷鏈綠色物流受到政府的高度關注和支持，有利于冷鏈物流行業的快速發展，但是我國冷鏈物流發展仍存在配送成本高、貨損率高、環境污染嚴重等問題。因此，如何在冷鏈物流配送過程中合理調度車輛達到較高的企業效益和社會效益具有十分重要的意義。

車輛路徑問題(VRP)是由Dantzig和Ramser于1959年首次提出[1]。隨著冷鏈物流的不斷發展，近年來，國內外眾多學者對冷鏈物流VRP問題進行了廣泛的研究。在考慮碳排放方面，方文婷等將節能減排轉化為綠色成本，建立了以總成本最小為研究目標的冷鏈物流VRP模型，并將A*算法與蟻群算法相結合構造了一種混合蟻群算法進行求解[2]；陶帝豪、康凱、姚臻等考慮了冷鏈配送過程中的碳稅成本，并設計了相應算法求解[3-5]；Liu G等在考慮碳稅政策的情況下，構建了聯合配送-綠色車輛路徑問題(JD-GVRP)模型[6];Li L等研究了碳排放下的冷鏈綜合庫存路徑優化問題[7]。在考慮顧客滿意度方面，任騰等考慮了顧客滿意度和道路擁堵狀況，并設計了新的知識型蟻群算法[8]；Song M等研究了一個典型的冷鏈物流系統車輛路徑問題(VRP)并提出一種改進人工魚群(IAFS)算法[9]。在考慮不確定因素對冷鏈物流配送的影響方面，姚源果、吳欣等都考慮了實時路況對于冷鏈配送的影響[10-11]；繆小紅、周新年等在保證貨物不超載的情況下建立了配送模型[12]。在優化研究方法方面，Raut R.D.提出模糊多準則決策方法，并通過冷鏈第三方物流供應商(CTPLs)的評價和選擇過程來改善食品損失[13]；Brito J.和Martinez F.J.等在建模和求解問題時，使用了一種軟計算方法[14]；王維軍等構建了帶時間窗的冷鏈物流配送路徑優化模型，用改進的智能水滴算法進行了求解[15]。

從以上分析可以發現，目前大多數關于冷鏈物流路徑優化的研究范圍已經很廣泛，本文在現有研究的基礎上，建立了以配送總成本最小為目標函數的冷鏈路徑優化模型，并對傳統遺傳算法進行改進，對A企業冷鏈物流配送問題進行實證研究，證實了模型和算法的有效性和可行性，以期豐富冷鏈物流路徑優化方面的研究。

2 模型構建與算法求解

2.1 問題描述與研究假設

在本文研究的冷鏈物流配送過程中，需要對六個方面的成本進行考慮，分別是車輛固定成本、運輸成本、制冷成本、時間窗懲罰成本、貨損成本以及碳排放成本。在顧客服務時間窗要求、車輛載重等約束條件下，構建以配送總成本最小為目標的冷鏈VRP模型，并求得最優配送方案。

本文假設條件如下：

①一個配送中心和多個客戶點，位置、時間窗要求等信息都己知，且配送中心不會發生缺貨現象；

②配送中心車輛充足且都是同一型號的汽油冷藏車；

③除極少數極端情況之外，配送車輛全程勻速行駛；

④所有配送車輛的實際載重不能超過其額定載重；

⑤所有車輛配送完成后不去其他地方，立即返回出發點；

⑥每個客戶僅由一輛配送車輛為其提供服務；

⑦產品腐壞率一樣，配送時間的增加以及環境溫度的升高會導致變質致使成本增加；

⑧交通狀況良好，不考慮交通擁堵情況，配送車輛平均速度己知；

⑨顧客的需求是靜態的，一旦確定便不會發生改變。

2.2 符號及參數變量的設置

表1 變量設置及其含義

2.3 冷鏈物流配送路徑優化目標函數構建

本文目標函數由固定成本、運輸成本、制冷成本、時間窗懲罰成本、貨損成本以及碳排放成本六部分組成，構建出考慮碳排放的冷鏈物流VRPTW模型為

(1)

s.t

(2)

(3)

EETi≤ti≤LLTi,i=1,2,…,n

(4)

(5)

xijk(1-xijk)=0,i,j=0,1,…,n;k=1,2,…,m

(6)

xik(1-xik)=0,i=0,1,…,n;k=1,2,…,m

(7)

yk(1-yk)=0,k=1,2,…,m

(8)

zik(1-zik)=0,i=0,1,…,n;k=1,2,…,m

(9)

式(1)表示目標函數，即固定成本、運輸成本、制冷成本[16]、時間窗懲罰成本、貨損成本以及碳排放成本[17]之和最小；式(2)表示每個客戶僅由一輛冷藏車輛為其提供配送服務；式(3)表示車輛在執行配送任務時，裝載的貨物重量必須小于車輛額定載重;式(4)表示顧客收貨時間窗要求；式(5)表示冷藏車輛均從配送中心出發，完成所有配送任務后均回到配送中心，形成一條閉合的配送路線；式(6)-(9)是變量取值約束，表示xijk、xik、yk、zik均為0-1變量。

2.4 改進遺傳算法設計

本文選擇遺傳算法進行求解，遺傳算法作為智能算法的一種，具有全局搜索能力強、應用范圍廣等優點，但是存在易早熟收斂、陷入局部最優解的不足，本文在傳統遺傳算法基礎上引入了精英保留策略、逆轉算子和移民策略。精英保留策略可以避免遺傳操作過程中丟失潛在的最優解，逆轉操作可以彌補其局部搜索不強的缺陷，移民操作可以在算法運行后期增加種群多樣性，有效避免求解結果陷入局部最優。

本文改進遺傳算法的求解步驟如下：

Step1：編碼和解碼。通過參數編碼將解序列反映到遺傳空間；再應用解碼將處理過的遺傳空間反映到解序列；

Step2：相關參數設置。確定了適應度函數，包括種群大小，交叉、變異概率以及算法終止最大迭代次數；

Step3：初始化種群。隨機生成一合適數量的初始解；

Step4：計算個體適應度值。適應度高的遺傳到下一代，本文設置總成本的倒數為適應度函數：

Step 5：選擇。本文選擇最常用的輪盤賭選擇法來篩選染色體，同時，為避免交叉、變異過程中丟失和破壞上一代種群中的優秀個體，采用精英保留策略來儲存算法求解過程中的優秀個體。本文保留父代個體中適應度取值排序處于前10%的個體，并用其替代后續子代中適應度取值排序處于后10%的個體，避免遺傳操作過程中丟失潛在最優解。

Step 6：交叉。將群體內的各個個體隨機搭配成對，對每一對個體以某種概率(稱為交叉概率)遵循某一種規則交換它們之間的部分染色體，產生新的個體，本文采用OX交叉。

Step 7：變異。將變異算子作用在群體上，對選中的個體以某種概率改變某一個或某幾個基因值。

Step8:逆轉操作。變異操作后，對每個個體的兩條染色體分別進行逆轉操作，并根據逆轉后適應度取值的大小決定是否保留逆轉結果。

Step 8：移民操作。通過設定閾值判定當前的算法是否陷入了早熟收斂，如果是，則實施“移民策略”引入外部個體，以此來增加種群多樣性，從而進一步增強種群搜索能力。為了解決遺傳算法容易陷入局部最優解問題，本文采用“移民策略”將部分較為優秀的個體移植到目前保留的群體中，增加現有種群的多樣性，從而提高算法搜索的高效性。首先需要判斷算法當前是否出現了早熟收斂現象,當遺傳算法表現為早熟收斂時,說明當前群體中個體的適應度非常相似，因此我們可以根據各群體的適應度方差來判斷算法是否陷入了早熟收斂。為了便于計算,令

式中:fi為第i個個體的適應度;favg為群體的平均適應度;N為種群規模。當E小于某一閾值時,我們就認為當前的算法出現了早熟收斂現象,進而對其實施“移民操作”[18]。

Step9：回到步驟4重新循環，直至滿足終止條件，跳出算法。

3 實證分析

本文以無錫市A企業冷鏈物流配送問題為例，對其在無錫地區的配送活動進行分析研究。A企業是無錫一家專業從事生鮮農產品批發配送業務的企業，雖然近年來以專業化的操作和科學化的管理在無錫發展壯大，但是在當前的冷鏈配送過程中仍然存在配送路徑規劃不科學、成本高等問題。本文用設計的改進遺傳算法對于A企業進行實證求解，為今后配送路徑規劃提供參考。

3.1 配送數據及參數設置

A企業顧客信息表如表2所示，表中序號0為配送中心，1-20為A企業顧客門店。

表2 A企業冷鏈配送信息表

表3 模型相關參數取值

表4 遺傳算法相關參數取值

3.2 求解結果分析

論文采用Matlab R2019a對算例進行仿真求解，用傳統遺傳算法與改進遺傳算法分別對程序運行 10 次，結果對比如表5所示。

表5 傳統遺傳算法與改進遺傳算法求解冷鏈路徑優化結果對比

由表5可得，Matlab運行10次，傳統遺傳算法求解A企業冷鏈物流配送路徑優化需要7輛車，平均總成本為6994.71元，平均運行時間為17.85s。改進后的遺傳算法求解綠色視角下A企業冷鏈物流配送路徑優化需要5輛車，平均總成本為5910.69元，平均運行時間為28.25s。這說明改進遺傳算法雖然求解時間增長，但是求得的配送方案所用車輛數更少，總成本更小，這說明改進遺傳算法的求解結果比傳統遺傳算法更優。

取傳統遺傳算法與改進遺傳算法求解10次中結果最優的一次迭代函數如圖1、圖2所示。

圖1 傳統遺傳算法求解迭代圖

圖2 改進遺傳算法求解迭代圖

兩種算法求解路徑優化問題迭代圖顯示，傳統遺傳算法于80代左右便開始收斂，而改進遺傳算法大約在134代左右開始收斂。與傳統遺傳算法相比，改進后的遺傳算法雖然求解時間加長，但是改善了傳統遺傳算法容易早熟收斂的缺陷，使得求解總成本比傳統遺傳算法更小，最優解更優，這充分說明了本文設計的改進遺傳算法的有效性。

傳統遺傳算法與改進遺傳算法求解10次中結果最優的一次配送方案路線如圖3、圖4所示。

圖4 改進遺傳算法求解最優配送方案路線圖

傳統算法和改進遺傳算法求解最優的一次配送方案行駛總里程以及總成本詳細信息如表6所示。

表6 傳統遺傳算法和改進遺傳算法求解最優配送方案詳細信息

通過表6可得，傳統遺傳算法求解最優配送方案配送總里程為240.426km,配送總成本為6886.1元，需要7輛車進行配送，7條配送路線分別為：0→7→4→11→0；0→20→17→0；0→16→14→15→0；0→13→1→12→0；0→2→5→3→6→0；0→19→8→10→0；0→9→18→0。改進遺傳算法求解最優配送方案配送總里程為219.84 km,配送總成本為5812.6元，需要5輛車進行配送，5條配送路線分別為：0→19→5→7→4→0；0→11→13→16→15→0；0→8→2→6→3→0；0→18→9→17→20→0；0→10→1→14→12→0,配送總距離和總成本分別降低了9.4%和18.5%。由此可得,改進的遺傳算法對A企業配送周邊生鮮需求點的冷鏈物流配送路徑求解比傳統遺傳算法求解配送路徑總距離更短、總配送成本更低。

4 結論

本文將冷鏈物流車輛路徑優化問題作為研究方向，目標是如何安排車輛調度進行配送以達到配送總成本最小。為了改善傳統遺傳算法容易陷入局部最優解和早熟收斂的缺陷，引入精英保留策略和移民策略進行改進，通過改進遺傳算法對A企業冷鏈物流配送案例進行求解，驗證了本文設計的改進遺傳算法能夠改善傳統遺傳算法的不足，并且使得求解結果更優，為解決相關冷鏈物流配送路徑優化問題提供了參考。