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

□ 解玉蝶

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

1 緒論

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

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

從以上分析可以發(fā)現(xiàn)，目前大多數(shù)關(guān)于冷鏈物流路徑優(yōu)化的研究范圍已經(jīng)很廣泛，本文在現(xiàn)有研究的基礎(chǔ)上，建立了以配送總成本最小為目標函數(shù)的冷鏈路徑優(yōu)化模型，并對傳統(tǒng)遺傳算法進行改進，對A企業(yè)冷鏈物流配送問題進行實證研究，證實了模型和算法的有效性和可行性，以期豐富冷鏈物流路徑優(yōu)化方面的研究。

2 模型構(gòu)建與算法求解

2.1 問題描述與研究假設(shè)

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

本文假設(shè)條件如下：

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

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

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

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

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

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

⑦產(chǎn)品腐壞率一樣，配送時間的增加以及環(huán)境溫度的升高會導(dǎo)致變質(zhì)致使成本增加；

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

⑨顧客的需求是靜態(tài)的，一旦確定便不會發(fā)生改變。

2.2 符號及參數(shù)變量的設(shè)置

表1 變量設(shè)置及其含義

2.3 冷鏈物流配送路徑優(yōu)化目標函數(shù)構(gòu)建

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

2.4 改進遺傳算法設(shè)計

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

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

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

Step2：相關(guān)參數(shù)設(shè)置。確定了適應(yīng)度函數(shù)，包括種群大小，交叉、變異概率以及算法終止最大迭代次數(shù)；

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

Step4：計算個體適應(yīng)度值。適應(yīng)度高的遺傳到下一代，本文設(shè)置總成本的倒數(shù)為適應(yīng)度函數(shù)：

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

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

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

Step8:逆轉(zhuǎn)操作。變異操作后，對每個個體的兩條染色體分別進行逆轉(zhuǎn)操作，并根據(jù)逆轉(zhuǎn)后適應(yīng)度取值的大小決定是否保留逆轉(zhuǎn)結(jié)果。

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

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

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

3 實證分析

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

3.1 配送數(shù)據(jù)及參數(shù)設(shè)置

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

表2 A企業(yè)冷鏈配送信息表

表3 模型相關(guān)參數(shù)取值

表4 遺傳算法相關(guān)參數(shù)取值

3.2 求解結(jié)果分析

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

表5 傳統(tǒng)遺傳算法與改進遺傳算法求解冷鏈路徑優(yōu)化結(jié)果對比

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

取傳統(tǒng)遺傳算法與改進遺傳算法求解10次中結(jié)果最優(yōu)的一次迭代函數(shù)如圖1、圖2所示。

圖1 傳統(tǒng)遺傳算法求解迭代圖

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

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

傳統(tǒng)遺傳算法與改進遺傳算法求解10次中結(jié)果最優(yōu)的一次配送方案路線如圖3、圖4所示。

圖4 改進遺傳算法求解最優(yōu)配送方案路線圖

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

表6 傳統(tǒng)遺傳算法和改進遺傳算法求解最優(yōu)配送方案詳細信息

通過表6可得，傳統(tǒng)遺傳算法求解最優(yōu)配送方案配送總里程為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。改進遺傳算法求解最優(yōu)配送方案配送總里程為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企業(yè)配送周邊生鮮需求點的冷鏈物流配送路徑求解比傳統(tǒng)遺傳算法求解配送路徑總距離更短、總配送成本更低。

4 結(jié)論

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