基于改進(jìn)鯨魚優(yōu)化算法的冷鏈配送路徑優(yōu)化

陸文星，王 璐，任少彤，李 華（合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009）

0 引 言

生鮮食品冷鏈物流路徑優(yōu)化問題實(shí)質(zhì)上可以簡(jiǎn)化為1959年被提出來的車輛路徑問題，已成為一個(gè)熱門研究課題。在具體研究?jī)?nèi)容上，學(xué)者們對(duì)車輛路徑規(guī)劃的研究主要集中在模型與算法兩方面[1-2]。研究從最初單目標(biāo)、單車型、少約束、靜態(tài)規(guī)劃模型，逐漸發(fā)展到如今的多目標(biāo)[3]、多車型[4]、多約束[5]、動(dòng)態(tài)規(guī)劃[6]模型，其難度和復(fù)雜程度在不斷增加，而且越來越接近實(shí)際應(yīng)用場(chǎng)景。同時(shí)，針對(duì)這類問題的研究也逐漸從傳統(tǒng)的、嚴(yán)格的求解算法轉(zhuǎn)變?yōu)榛趩l(fā)式的求解算法[7-10]。

近年來鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）、麻雀算法、灰狼算法等在路徑優(yōu)化問題的求解中表現(xiàn)出色，由于鯨魚優(yōu)化算法運(yùn)算簡(jiǎn)便、可調(diào)參數(shù)少、易于跳出局部極值，因此本文采用鯨魚優(yōu)化算法來解決路徑規(guī)劃問題。

文獻(xiàn)[11]將鯨魚優(yōu)化算法與Pareto適應(yīng)性多目標(biāo)優(yōu)化方法相結(jié)合，構(gòu)建了支持多目標(biāo)的多式聯(lián)運(yùn)路徑選擇模型并驗(yàn)證了該方法的有效性。文獻(xiàn)[12-13]顯示，鯨魚優(yōu)化算法對(duì)比一些基本的算法，在全局搜索方面有著更好的優(yōu)勢(shì)。文獻(xiàn)[14]利用混沌映射來調(diào)節(jié)鯨魚算法的控制參數(shù)，實(shí)驗(yàn)表明，改進(jìn)的算法能夠有效減輕早熟收斂的問題。

在以上研究成果的基礎(chǔ)上，本文構(gòu)建了一個(gè)旨在降低運(yùn)輸總成本的冷鏈路徑優(yōu)化模型，在基本鯨魚算法的基礎(chǔ)上采用Beta分布對(duì)種群進(jìn)行初始化并加入非線性收斂因子改善算法迭代后期易陷入局部最優(yōu)的情況，還引入變鄰域搜索算法來增加鄰域結(jié)構(gòu)的多樣性。通過與基本鯨魚算法進(jìn)行對(duì)比，結(jié)果表明改進(jìn)算法可以有效降低綜合配送成本。

1 模型建立

1.1 問題描述

本文對(duì)物流配送路徑規(guī)劃問題進(jìn)行了研究，設(shè)定場(chǎng)景為: 某城市物流配送系統(tǒng)有 1個(gè)配送中心和n個(gè)客戶需求點(diǎn)，已知配送中心和需求點(diǎn)的位置，并且該配送中心能夠滿足所有需求點(diǎn)所需要的供給量。該模型的目標(biāo)是在滿足車輛承載能力和顧客需求限制的條件下，對(duì)冷藏車的使用次數(shù)和運(yùn)輸路徑進(jìn)行優(yōu)化，實(shí)現(xiàn)配送中心的冷藏車的整體配送費(fèi)用最小化。具體假設(shè)如下：用于運(yùn)送農(nóng)產(chǎn)品的冷藏車完全相同；每個(gè)需求點(diǎn)的需求必須一次性得到滿足，且只能被訪問一次；由于新鮮農(nóng)產(chǎn)品的種類不同，其變質(zhì)規(guī)律也不相同，因此，本文僅針對(duì)一類新鮮農(nóng)產(chǎn)品進(jìn)行研究；每輛冷藏車農(nóng)產(chǎn)品的裝載量不超過其最大載重，在運(yùn)送時(shí)每個(gè)需求點(diǎn)的需求量不得超過冷藏車的最大載重量；冷藏車運(yùn)輸?shù)倪^程中速度保持恒定；冷藏車按規(guī)劃路徑行駛，交通意外、車輛故障、堵車耽誤的時(shí)間都忽略，因其他情況產(chǎn)生的懲罰費(fèi)用也忽略不計(jì)；本文只考慮生鮮農(nóng)產(chǎn)品的送貨情況，不考慮取貨的情況；且不考慮農(nóng)產(chǎn)品的倉儲(chǔ)成本和貨運(yùn)損失；生鮮產(chǎn)品新鮮度的變化僅和車輛到達(dá)客戶點(diǎn)所用的時(shí)間有關(guān)。

1.2 參數(shù)符號(hào)說明

U為配送中心與需求點(diǎn)集合，U={i}，i=1，2，...，n為需求點(diǎn)，i=0為配送中心；Vk為冷藏車集合，VK={k}，k=1，2，...，K（K為冷藏車總數(shù)）；v為冷藏車速度；Mk為配送車輛k服務(wù)路線所經(jīng)過的需求點(diǎn)集合；C1為生鮮農(nóng)產(chǎn)品運(yùn)輸過程的單位時(shí)間制冷成本；C2為生鮮農(nóng)產(chǎn)品預(yù)冷過程的單位時(shí)間制冷成本；tj為車廂預(yù)冷時(shí)間；dij為節(jié)點(diǎn)i、j之間的距離；Fs為配送車輛單位距離的配送成本；Ti為需求點(diǎn)i接受服務(wù)所需時(shí)間；Si為配送車輛到達(dá)需求點(diǎn)i的時(shí)間；Q為冷藏車的最大載重；t0為車輛k從配送中心出發(fā)的時(shí)間點(diǎn)；tik為到達(dá)需求點(diǎn)i的時(shí)間點(diǎn)；C0為碳稅；c為油價(jià)；eCO2為CO2排放系數(shù)；Fk為第k輛車的車輛使用成本；β為冷鏈產(chǎn)品的新鮮度衰減系數(shù)；pr為冷鏈產(chǎn)品單位重量的價(jià)格；Di為需求點(diǎn)i的生鮮農(nóng)產(chǎn)品需求量；Xkij為車輛k從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)j為1，否則為0；Yik為車輛k配送到需求點(diǎn)i為1，否則為0；Wk為車輛k配送時(shí)產(chǎn)生的碳排放量；ρe為車輛無負(fù)載情況下的耗油率；ρf為車輛滿載情況下的耗油率；Sik為第k輛車到達(dá)第i個(gè)需求點(diǎn)的時(shí)間；[ET，LT]為需求點(diǎn)對(duì)配送冷藏車的時(shí)間窗約束；ETi為需求點(diǎn)期望配送車輛的最早時(shí)刻；LTi為需求點(diǎn)期望配送車輛的最晚時(shí)刻；CTi為需求點(diǎn)能接受配送車輛的最早時(shí)刻；DTi為需求點(diǎn)能接受配送車輛的最晚時(shí)刻；D為在允許運(yùn)送區(qū)間內(nèi)，但不在需求點(diǎn)客戶期望的區(qū)間范圍的運(yùn)送時(shí)間的懲罰費(fèi)用系數(shù)；M為超過允許運(yùn)送區(qū)間范圍的懲罰費(fèi)用系數(shù)，本文設(shè)定為正無窮。

1.3 目標(biāo)函數(shù)

配送成本P1：

時(shí)間懲罰費(fèi)用的總成本P2，

當(dāng)Si∈[CTi，DTi]時(shí)，

當(dāng)Si?[CTi，DTi]時(shí)，

車輛使用成本P3：

制冷成本P4：

油耗成本P5，

用負(fù)載估計(jì)法[15]來計(jì)算油耗量。當(dāng)冷藏車內(nèi)農(nóng)產(chǎn)品重量為M時(shí)，其單位距離燃油量為：

當(dāng)車輛從配送中心完成對(duì)所有需求點(diǎn)的配送任務(wù)時(shí)，整個(gè)過程燃油消耗量為：

其中，ρ（Qij）為載有重量為Qij的冷藏車由需求點(diǎn)i直接行駛到需求點(diǎn)j單位距離的消耗量。所以，整個(gè)過程中的油耗成本為：

碳排放成本P6：

生鮮農(nóng)產(chǎn)品損耗成本P7，

采用新鮮度衰減函數(shù)[16]η（t）=η0exp（-βt）對(duì)冷鏈?zhǔn)称沸迈r程度的變化進(jìn)行描述，η（t）和η0分別表示t時(shí)刻和初始時(shí)刻的產(chǎn)品新鮮度，本文η0取固定值100%，則如下公式：

1.4 模型建立

使冷藏車運(yùn)輸費(fèi)用最小化的目標(biāo)函數(shù)：

約束條件：確保每個(gè)需求點(diǎn)都能被冷藏車配送：

確保每輛車載重量不超出其最大載重量：

確保每個(gè)需求點(diǎn)都只能有一輛車對(duì)其進(jìn)行運(yùn)送：

確保每輛車從配送中心出發(fā)，完成配送后返回配送中心：

確保冷藏車在對(duì)某一節(jié)點(diǎn)完成服務(wù)后須轉(zhuǎn)往下一節(jié)點(diǎn)：

確保從配送中心出發(fā)的車數(shù)和不能超過配送中心所能使用的車輛總數(shù)：

確保需求點(diǎn)總需求不超過車輛的最大載重：

確保第k輛車到達(dá)第i個(gè)需求點(diǎn)在可承受時(shí)間范圍內(nèi)：

2 算法設(shè)計(jì)

如何精確高效地解決路徑優(yōu)化問題一直是一個(gè)重大難題。在現(xiàn)有的研究中，啟發(fā)式算法經(jīng)常被用來解決類似的問題，而鯨魚優(yōu)化算法作為一種啟發(fā)式算法，因其機(jī)制簡(jiǎn)單、參數(shù)少、尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)得到廣泛的發(fā)展和應(yīng)用。故通過對(duì)標(biāo)準(zhǔn)的鯨魚優(yōu)化算法進(jìn)行改進(jìn)，可以實(shí)現(xiàn)更快速有效的模型求解。

2.1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法[17]是模仿自然界中鯨魚捕食行為的一種新的群智能優(yōu)化算法。鯨魚捕食行為主要有：包圍獵物、捕獲獵物、搜索獵物。以上捕食過程可以應(yīng)用到鯨魚優(yōu)化算法的求解過程，也就是一個(gè)解可以由一個(gè)鯨魚個(gè)體來表達(dá)，多個(gè)解就可以由多個(gè)鯨魚個(gè)體來表達(dá)?？梢詫ⅥL魚算法的求解思路類比為多條鯨魚個(gè)體在不斷變換位置，直到搜索到一個(gè)滿意的解。

2.1.1 包圍獵物

假定在d維空間中，目前最優(yōu)鯨魚個(gè)體X*的位置為，鯨魚個(gè)體Xj的位置為。則鯨魚個(gè)體Xj在最優(yōu)鯨魚個(gè)體的影響下的下一個(gè)位置Xj+1的計(jì)算公式如下：

2.1.2 捕獲獵物

當(dāng)鯨魚個(gè)體以螺旋式的方式向當(dāng)前最佳鯨魚個(gè)體靠近捕獲獵物時(shí)，一半的個(gè)體會(huì)選擇收縮包圍圈，另外一半的個(gè)體則選擇以螺旋的形式奔向獵物。

當(dāng)p＜0.5時(shí)，

當(dāng)p≥0.5時(shí)，

其中，b為對(duì)數(shù)螺旋形狀常數(shù)，l為[-1，1]區(qū)間內(nèi)的隨機(jī)數(shù)。

2.1.3 搜索獵物

在捕獲獵物行為數(shù)學(xué)模型中，A1的取值被限定在[-1，1]，當(dāng)A1的取值不屬于該范圍，鯨魚個(gè)體則會(huì)從當(dāng)前鯨魚個(gè)體中隨機(jī)選取一條鯨魚個(gè)體靠近。假定在空間中，鯨魚群體中隨機(jī)鯨魚個(gè)體Xs的位置為，則搜索獵物行為的數(shù)學(xué)模型如下：

2.2 鯨魚優(yōu)化算法的改進(jìn)思想

2.2.1 種群初始化

在某種程度下，種群初始化位置的設(shè)定會(huì)對(duì)搜索過程產(chǎn)生一定的影響，以均勻分布為基礎(chǔ)隨機(jī)生成初始位置的傳統(tǒng)方法雖然簡(jiǎn)單易操作，但它不利于使初始解的分布盡可能均勻。為了解決這一問題，本文采用Beta分布，并將其應(yīng)用于種群的初始化過程，盡量使初始解的分布均勻化。

Beta分布是在[0，1]中定義的連續(xù)概率分布族，其形狀參數(shù)α和β（均為正數(shù)），它的概率密度函數(shù)為：

大量實(shí)驗(yàn)表明，當(dāng)α=β=0.5時(shí)，具有很好的初始化效果。所以本文利用α=β=0.5時(shí)Beta分布的概率密度函數(shù)不斷迭代，生成一系列連續(xù)的點(diǎn)，該函數(shù)表達(dá)式為：

2.2.2 引入非線性收斂因子

鯨魚優(yōu)化算法的全局搜索和局部搜索都受到收斂因子a的影響，如果按照原有算法的迭代次數(shù)線性減少a，則容易陷入局部極值，從而使算法收斂的速度減慢。并且當(dāng)收斂因子a作線性改變時(shí)，其對(duì)全局尋優(yōu)和局部尋優(yōu)的影響不大。如果在初始階段適當(dāng)增大a值，則可以有效改善系統(tǒng)的整體搜索性能，并防止出現(xiàn)“早熟”現(xiàn)象；在算法執(zhí)行的后期，將a值適當(dāng)減小，可以改善局部求解能力和收斂速度[18]。

為此，本文引入了一種非線性收斂因子[19]來實(shí)現(xiàn)初始階段a值的增大和算法后期a值的減小，其表達(dá)式如下：

其中，e為自然對(duì)數(shù)底數(shù)；t為當(dāng)前迭代次數(shù)。

2.2.3 結(jié)合變鄰域搜索算法

變鄰域搜索算法的底層基礎(chǔ)運(yùn)算邏輯是將相異動(dòng)作所構(gòu)建的鄰域結(jié)構(gòu)進(jìn)行交替搜索，以此達(dá)成分散和集中的良好平衡。因此眾多學(xué)者將變鄰域搜索算法與其他算法結(jié)合起來解決VRP問題[20-21]。

本文引用變鄰域搜索算法中的兩元素操作（2-opt）鄰域結(jié)構(gòu)操作與傳統(tǒng)的鯨魚算法結(jié)合。在此基礎(chǔ)上，本文選取一條路徑上的任意兩個(gè)節(jié)點(diǎn)，把兩個(gè)節(jié)點(diǎn)之間的路徑進(jìn)行翻轉(zhuǎn)操作，得到一條新路徑，從而增加了鄰域結(jié)構(gòu)的多樣性，也提高了尋優(yōu)的效率。

舉例說，假定顧客點(diǎn)是1、2、3、4、5、6，s是目前的最佳方案，s為路徑1-2-3-4-5-6。首先，從s中隨機(jī)選取兩個(gè)并不鄰近的節(jié)點(diǎn)2、5，再將這兩個(gè)節(jié)點(diǎn)之間的路徑逆序，得出新的路徑，向新路徑中添加節(jié)點(diǎn)2以前的路徑，再翻轉(zhuǎn)2、5之間的路徑，5以后的路徑以相同的方式被加到新的路徑中，最后，得出新路徑s’1-5-4-3-2-6。

2.3 算法描述

改進(jìn)的鯨魚優(yōu)化算法流程可描述為如下所示。

初始化算法參數(shù)：種群大小E，種群搜索空間[S1，S2]，迭代次數(shù)t。

采用Beta分布來初始化種群。

計(jì)算個(gè)體適應(yīng)度值，并找出最優(yōu)適應(yīng)度值和相應(yīng)的最優(yōu)個(gè)體。

更新非線性因子a，進(jìn)而更新A1，C1。

更新最優(yōu)的鯨魚個(gè)體并更新鯨魚的位置。

當(dāng)p<0.5時(shí)，若|A|≥1，搜索獵物，若|A|＜1，捕獲獵物；當(dāng)p≥0.5時(shí)包圍獵物。

記錄最優(yōu)目標(biāo)值。

對(duì)當(dāng)前最優(yōu)鯨魚調(diào)用變鄰域算法。

更新局部最優(yōu)解，檢查并修改超出搜索空間的鯨魚個(gè)體。

計(jì)算并評(píng)估鯨魚個(gè)體的適應(yīng)度值，對(duì)全局最優(yōu)解進(jìn)行更新。

判斷是否滿足終止條件：如果是，輸出最優(yōu)目標(biāo)值，流程終止；如果否，則轉(zhuǎn)入第五步。

3 實(shí)例求解與結(jié)果分析

3.1 算例概述

為了對(duì)比傳統(tǒng)鯨魚算法和改進(jìn)鯨魚算法對(duì)該模型的求解結(jié)果，并驗(yàn)證改進(jìn)鯨魚算法的可行性，本文采用Solomon數(shù)據(jù)集里的C101數(shù)據(jù)，設(shè)定冷藏車的總數(shù)為10，速度為50km/h，其余參數(shù)如表1所示。

表1 參數(shù)說明

3.2 仿真分析

本文分別使用傳統(tǒng)鯨魚優(yōu)化算法和改進(jìn)的鯨魚優(yōu)化算法來求解上述模型，兩個(gè)算法分別在初始種群大小設(shè)置為30、迭代次數(shù)設(shè)置為100的情況下運(yùn)行了50次，并從中挑選出最優(yōu)配送方案。所得收斂圖如圖1、圖2所示，配送路徑見表2、表3所列。圖3給出了傳統(tǒng)鯨魚優(yōu)化算法和改進(jìn)鯨魚優(yōu)化算法求解模型的算法收斂曲線，圖1、圖2、圖3的縱坐標(biāo)為成本值，橫坐標(biāo)為迭代次數(shù)。

圖1 傳統(tǒng)鯨魚算法收斂圖

圖2 改進(jìn)后鯨魚算法收斂圖

圖3 傳統(tǒng)鯨魚算法與改進(jìn)后鯨魚算法收斂比較

表2 傳統(tǒng)鯨魚算法配送路徑

表3 改進(jìn)鯨魚算法配送路徑

從以上算法的運(yùn)行結(jié)果可以看出：改進(jìn)的鯨魚優(yōu)化算法在性能上有了很大的提高。從圖3可以看出改進(jìn)的鯨魚優(yōu)化算法比傳統(tǒng)鯨魚優(yōu)化算法先達(dá)到收斂，隨著迭代次數(shù)的增加而不斷向最優(yōu)解逼近，而傳統(tǒng)鯨魚算法則在65代左右出現(xiàn)了算法早熟現(xiàn)象。結(jié)果可知，改進(jìn)算法在收斂速度、全局尋優(yōu)方面具有很大的優(yōu)勢(shì)。

鯨魚優(yōu)化算法求得的配送路徑總成本為171 294.10元，改進(jìn)鯨魚算法求得的配送路徑總成本為167 962.58元，另外根據(jù)表4提供的其他成本比較，證明了改進(jìn)算法的有效性，能夠在油耗、制冷、碳排放方面實(shí)現(xiàn)更好的均衡。

表4 傳統(tǒng)鯨魚算法與改進(jìn)后鯨魚算法成本比較

4 結(jié) 論

本文從解決冷鏈物流運(yùn)輸高要求出發(fā)，建立了冷鏈物流配送優(yōu)化模型，并在傳統(tǒng)鯨魚算法的基礎(chǔ)上采用Beta分布對(duì)種群進(jìn)行初始化，之后再加入非線性收斂因子改善算法迭代后期易陷入局部最優(yōu)的情況，最后引入變鄰域搜索算法使鄰域結(jié)構(gòu)更加多樣化。利用Matlab實(shí)驗(yàn)，將原來的鯨魚優(yōu)化算法與改進(jìn)鯨魚算法進(jìn)行了比較。結(jié)果表明，與傳統(tǒng)鯨魚算法相比，改進(jìn)鯨魚算法得到的收斂速度快、成本低。本文構(gòu)建的模型和它的求解方法可以為冷鏈物流企業(yè)考慮碳排放成本的配送路徑優(yōu)化提供參考，下一步將利用提出的改進(jìn)鯨魚算法優(yōu)化策略對(duì)多目標(biāo)路徑規(guī)劃進(jìn)行深入的應(yīng)用研究。