陳鑫影，李依琳，肖司義

(大連交通大學 計算機與通信工程學院，遼寧 大連 116028)

車輛路徑問題(Vehicle Routing Problem，簡記VRP)是指在一定的約束條件下，以形成最小化配送成本為目標的配送路徑方案.約束包括但不僅限于以下幾點：客戶需求量，客戶要求時間，車輛容量等.需對配送車輛拜訪客戶的順序進行合理的規(guī)劃安排，最終得到實現(xiàn)上述目標最大化的車輛配送路徑方案[1].在生鮮農(nóng)產(chǎn)品的配送中，需要使用冷鏈物流進行配送，在傳統(tǒng)的車輛路徑問題的數(shù)學模型上加入冷鏈運輸成本，就構成了生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化問題[2].由于利用傳統(tǒng)方法解決車輛路徑問題存在一些局限性，所以國內(nèi)外學者多采用融合算法來解決該問題.Roberto等[3]在綠色車輛路徑問題中，采用了遺傳算法，以3-OPT局部搜索作為變異算子，并在碳排放模型中引入了道路坡度系數(shù)，以減少碳排放量.Altabeeb等[4]提出了一種新的混合螢火蟲算法,將螢火蟲算法與兩種局部搜索和遺傳算子相結合,解決受車輛容積限制的VRP問題.Saxena等[5]提出了一種遺傳算法解決針對OpenMP編程模型的車輛路徑問題.Lee等[6]針對電磁優(yōu)化問題,設計了一種帶有混合優(yōu)化策略的改進新型遺傳算法.Zhang等[7]提出了一種改進煙花算法，該方法基于生物地理學優(yōu)化的遷移算子(BBO)得到爆炸算子，并開發(fā)了一種新的高斯變異算子，以解決高速列車調(diào)度問題.

上述研究雖取得了一定進展，但仍存在一些問題，如求解質量差、容易陷入局部最優(yōu)等.遺傳算法擁有極強的全局搜索能力，但容易陷入早熟收斂.煙花算法具有爆發(fā)性和多樣性，可以跳出局部最優(yōu)[8].因此本文融合遺傳算法和煙花算法，設計一種改進型煙花遺傳算法(Improved Fireworks-Genetic Algorithm,簡稱IFWGA),用以解決生鮮農(nóng)產(chǎn)品配送的車輛路徑問題.

1 生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型

本文主要研究生鮮農(nóng)產(chǎn)品同城配送的車輛調(diào)度的物流路徑優(yōu)化問題，其問題可表述為：已知同城農(nóng)產(chǎn)品的冷鏈物流配送車型，并且車輛數(shù)量足夠，同時已知客戶點的數(shù)量及需求量、客戶期望送達時間和能接受的時間區(qū)間的條件下，建立該問題的數(shù)學模型.在完成客戶需求量的情況下，盡量最小化成本，計算出一個物流配送方案[9].本文參考文獻[10]，將碳排放成本和開/關門兩種狀態(tài)的貨損率引入生鮮農(nóng)產(chǎn)品配送路徑的傳統(tǒng)模型，提出了改進模型.該模型總成本包括以下5點:

(1)固定成本

固定成本包括租車和司機工人的工資等.若配送中心共有K輛車,則配送過程中的固定成本可用C1表示，見式(1).

(1)

式中：fk為來自第k輛車的固定成本;sk=1表示所生成的配送方案里有第k輛車的參加，sk=0代表第k輛車不參加.

(2)運輸成本

運輸成本是指車輛在物品配送的途中所產(chǎn)生的與距離相關的費用，如油耗、車輛保養(yǎng)等.由油耗量決定的運輸成本C2，見式(2).

(2)

(3)懲罰成本

由于生鮮農(nóng)產(chǎn)品新鮮易腐敗的特性，其新鮮度會隨著時間延長而逐漸下降，因此本文引入了懲罰函數(shù)這一概念.將客戶可接受的遲到時間作為軟時間窗，如果生鮮農(nóng)產(chǎn)品超出了硬時間窗但未超出軟時間窗，則用懲罰函數(shù)計算出懲罰成本并加入總成本之中.懲罰成本C3見式(3).

(3)

(4)貨損成本

生鮮農(nóng)產(chǎn)品具有易腐壞變質的特性.貨損成本就是生鮮貨品腐敗變質、造成浪費時所形成的成本.在本文設計的模型中，貨損成本共包括車門開啟時的貨損成本和車門關閉時的貨損成本.

D(t)=D0e-?t是一個計算腐敗率的函數(shù).其中，某生鮮食品在t時間的新鮮程度由D(t)表示；該生鮮食品的原始新鮮程度由D0表示；?表示腐敗率；車輛的運輸時間由t來表示.

車輛在關門狀態(tài)下行駛時，?可設置為一個常數(shù)，車輛在行駛過程中?也會變大.基于函數(shù)D(t)，得到關門狀態(tài)下的貨損成本C41，見式(4).

(4)

在車輛到達客戶點時需要開門卸貨，開門狀態(tài)下的貨損成本C42,見式(5).

(5)

C4=C41+C42

(6)

(5)制冷成本

冷鏈物流車的制冷劑費用就是制冷成本.車輛在送貨途中有開門、關門兩種狀態(tài)，在開門狀態(tài)下冷氣外泄會導致溫度升高,因此本文的制冷成本分為開門、關門兩種狀態(tài)下的制冷成本.

用熱負荷來表示關門狀態(tài)的制冷劑消耗量.本文引入轉化系數(shù),用Qk1來表示k車運行時的熱負荷，Qk2表示k車開門狀態(tài)下傳入的熱量，C51表示關門狀態(tài)下的制冷成本，C52表示開關門過程中的制冷成本，見式(7)～式(10).

Qk1=(1+β)RS(Tw-Tn)

(7)

(8)

Qk2=α(0.54Vk+3.22)(Tw-Tn)

(9)

(10)

式(7)～式(10)中：β∈[0.1，0.2]；P2表示單位距離行駛下的制冷成本；S表示車廂的表面積；Sw表示外部的車廂面積；Sn表示內(nèi)部的車廂面積；R表示傳熱系數(shù)；Tw表示外部的溫度；Tn表示內(nèi)部的溫度；tij表示客戶i行駛到客戶j的時間；α代表了開門的頻率,其取值見表1.

表1 開門頻度系數(shù)

因此，總制冷成本C5見式(11).

C5=C51+C52

(11)

(6)碳排放成本

本模型考慮了碳排放所帶來的成本.車輛制冷和正常行駛排放的尾氣都會造成碳排放的增加.車輛的燃油消耗量是由載重和距離決定的，載貨量X的車輛在固定距離中的燃油消耗ρ(X)，見式(12).

(12)

式中：車輛的負載由X表示;ρ*是車輛滿載狀態(tài)的燃油消耗;ρ0是車輛在不裝載貨物時的燃油消耗;Q是額定載重.

E1表示由車輛載貨行駛產(chǎn)生的燃油消耗量所產(chǎn)生的碳排放量，E2表示制冷產(chǎn)生的碳排放，基于E1和E2得出總碳排放成本C6，見式(13)～(15).

E1=e0ρ(X)d

(13)

E2=wXd

(14)

(15)

式中：車輛的負載由X表示，ρ(X)表示燃油消耗；e0是二氧化碳排放系數(shù)；車輛行駛的路程由d來表示；w是單位路程的由制冷劑導致的碳排放量.其他變量含義見式(2).

因此，總成本目標函數(shù)Z可由式(16)表示：

Z=Min(C1+C2+C3+C4+C5+C6)

(16)

2 車輛路徑優(yōu)化算法

2.1 算法設計思路

目前，生鮮農(nóng)產(chǎn)品配送領域存在的主要問題包括求解結果差、運行時間長、陷入局部最優(yōu)等.遺傳算法[11]全局搜索能力強，但易陷入早熟收斂.煙花算法[12]具有機理簡單和尋優(yōu)能力強等優(yōu)點.因此本文采用遺傳算法為主框架，利用遺傳算法全局搜索能力強的優(yōu)點,結合煙花算法爆炸性的特點，在較優(yōu)解附近產(chǎn)生更多解，在較差解附近產(chǎn)生較少解，以解決易陷入局部最優(yōu)和早熟收斂的問題.

車輛路徑問題要求算法前期具有較強的全局搜索能力，后期具有較強的局部搜索能力.結合高斯變異算子和柯西變異算子，“變異步長較大能提高算法的全局搜索能力.變異步長較小則能提高局部搜索能力”[13].

因此，本文將煙花算法的變異算子設計為兩種步長，步長較大的變異算子(long step-size mutation operator，簡稱LSMO)和步長較短的變異算子(short step-size mutation operator，簡稱SSMO).為實現(xiàn)不同求解階段兩種變異算子的切換，引入動態(tài)切換概率，根據(jù)迭代次數(shù)不同，算法前期使用LSMO的概率較大，算法后期使用SSMO的概率較大.

2.2 算法流程

本算法將遺傳算法與煙花算法相結合，并引入兩種變異算子，生成的改進型煙花遺傳算法流程如下:

2.2.1 染色體編碼

編碼采用自然數(shù)編碼，0代表配送中心，n表示客戶點數(shù)量，k為配送車輛數(shù)量.對于有n個顧客，k輛車的VRP問題來說，染色體長度為n+k+1.例如：有10個客戶分別由4輛車進行服務,一條可能的染色體如下：

0，5，0，1，2，3，7，0，8，9，6，0，4，10，0

這條染色體表示的四輛車的行駛路線為：

第一輛車：0-5-0

第二輛車：0-1-2-3-7-0

第三輛車：0-8-9-6-0

第四輛車：0-4-10-0

2.2.2 選擇

選擇操作采用輪盤賭選擇法,并在選擇過程中引入精英保留策略.

2.2.3 交叉

采用PMX交叉(部分匹配交叉)，隨機抽取兩條父代染色體的位置相同的片段.交換該片段，由于交換后的染色體中會出現(xiàn)重復值，需要根據(jù)映射關系去掉重復值，找到該重復值在另一個片段的對應位置，替換掉該重復值，如果繼續(xù)出現(xiàn)重復值，則一直循環(huán)此步驟，直到?jīng)]有重復值.

2.2.4 變異

變異操作采用交叉變異,將兩個隨機選中的點進行交叉變異 ,這種變異方法適用于固定位置關系的問題[14].

2.2.5 煙花算法

對每代遺傳算法的最優(yōu)解和最差解執(zhí)行煙花算法.具體步驟如下：

(1)計算爆炸數(shù)目

在煙花算法中,每個煙花的爆炸半徑和爆炸產(chǎn)生的火花數(shù)目是根據(jù)其相對于煙花種群中其他煙花適應度值計算得到的[15],適應度優(yōu)的個體爆炸數(shù)目更多.對于煙花xi,爆炸火花數(shù)目Si見式(17).

(17)

式中：f(xi)表示個體xi的適應度值；ymax是當前種群中適應度的最大值；常數(shù)M控制最大火花數(shù)量不會超過10,為了防止除0操作設置了一個非常小的常數(shù)ε.

為了平衡較優(yōu)秀的火花和較差的火花周圍產(chǎn)生的火花數(shù)目,做出了一些限制，Smax為最大火花數(shù)目，Smin為最小火花數(shù)目,見式(18)、式(19).

Smax=round(M·0.8)

(18)

Smin=round(M·0.1)

(19)

(2)計算爆炸半徑

爆炸半徑與個體適應度有關，適應度優(yōu)的個體半徑更小，爆炸半徑Ai見式(20).

(20)

(3)產(chǎn)生爆炸火花

本文的爆炸算子的設計為三種方式，每個煙花隨機采用其中的一種.第一種是單點交換，隨機選擇染色體中兩個除配送中心以外的點，即非0點，交換兩個點的位置；第二種是插入，隨機選擇一個點，插入到路徑中其他位置；第三種是反轉，將已經(jīng)生成的路徑的點反向排列生成新的路徑.

(4)產(chǎn)生變異火花

本算法的變異算子設計與爆炸算子相同，不再贅述.根據(jù)路徑優(yōu)化問題的特點,為平衡局部搜索能力與全局搜索能力，本算法設計了兩種不同步長的變異:第一種變異算子步長為1(SSMO)，分別對當前種群的最優(yōu)解和最差解進行變異操作，其變異操作與產(chǎn)生爆炸火花的方式相同，上文已經(jīng)做出了詳細介紹；第二種變異步長為6(LSMO)，對當前最優(yōu)解和最差解進行變異操作，如果在6步中，最優(yōu)解更新，則重新計算6步，否則輸出當前解.

算法生成一個隨機數(shù)r∈[0,1]，當r小于當前變異概率p，則選擇SSMO，否則選擇LSMO.變異概率隨著迭代次數(shù)增加變大，計算見式(21)：

(21)

式中:p為當前個體變異概率;max gen為最大迭代次數(shù);gen為當前代數(shù).

3 某生鮮連鎖超市的案例分析

3.1 數(shù)據(jù)與參數(shù)設置

本文采用某生鮮連鎖超市的案例測試IFWGA算法在生鮮農(nóng)產(chǎn)品物流配送路徑優(yōu)化問題中的可行性.該超市坐標數(shù)據(jù)來自百度地圖，共收集了50家分店坐標，選擇最中心的一個點作為配送中心.客戶需求量和時間約束均為虛擬數(shù)據(jù)，使用excel的rand函數(shù)隨機生成.根據(jù)市場調(diào)查，生鮮食品均在上午進行配送，因此時間在6∶00—12∶00中隨機生成.由于車容量是6，因此每個客戶的需求量不宜過大，在0～2之間隨機生成.考慮到貨物以噸為單位，服務時間在0～40 min內(nèi)隨機生成.

相關參數(shù)設置：種群大小為100，迭代數(shù)為1 000，交叉概率為0.8，變異概率為0.2，代溝概率為0.9，爆炸數(shù)目為10，最大爆炸半徑為10.

在內(nèi)存為4GB、CPU為10代i5、500GB固態(tài)硬盤的電腦上，采用MATLAB 2020進行仿真實驗.實驗分別從運行時間、求解質量、收斂速度方面測試了GA、FWA-EI、IFWGA和FWGA算法.其中FWGA算法是IFWGA刪除LSMO和SSMO兩種變異算子的算法.利用FWGA算法進行對比實驗，旨在測定兩種變異算子對結果的影響.

3.2 實驗結果

3.2.1 求解質量對比

為驗證IFWGA算法的求解質量，分別截取了GA、FWA-EI、FWGA、IFWGA算法的結果路徑圖，并記錄了十次求解結果，見圖1和表2.

試驗結果表明：IFWGA得到的最優(yōu)解比較穩(wěn)定，4次達到最優(yōu)解，對GA、FWA-EI和FWGA的結果都有明顯的優(yōu)化，僅有一次FWGA的運行結果略優(yōu)于IFWGA.結合表2可計算得出，在總成本方面，IFWGA比GA優(yōu)化了39.8%，比FWA-EI優(yōu)化了16.9%，比FWGA優(yōu)化了16.2%.

(a) 遺傳算法(GA)

表2 總成本對比

3.2.2 收斂速度對比

為對比GA、FWA-EI、FWGA和IFWGA的收斂速度，截取了4種算法的迭代曲線圖，并總結了4種算法達到最優(yōu)解的代數(shù)，見圖2.

圖2 迭代曲線圖

可以看出，IFWGA的收斂速度明顯高于FWGA、GA和FWA-EI，GA在800代之后陷入局部最優(yōu)，F(xiàn)WA-EI在900代陷入局部最優(yōu)，F(xiàn)WGA在580代之后陷入局部最優(yōu)，IFWGA在250代就達到最優(yōu).

3.2.3 運行時間對比

為了驗證GA、FWA-EI、FWGA和IFWGA的運行時長，分別對4種算法運行了10次，運行時間對比見表3.其中，GA平均運行時間為54.38 s，F(xiàn)WA-EI的平均運行時間為76.23 s，F(xiàn)WGA的平均運行時間為65.72 s，IFWGA的平均運行時間為63.44 s.FWGA較FWA-EI運行時間快了10.51 s，優(yōu)化了13.8%；IFWGA較GA慢了9.06 s；IFWGA較FWA-EI 運行時間快了12.79 s，優(yōu)化了16.8%；IFWGA較FWGA快了2.28 s，優(yōu)化了3.5%.IFWGA運行時間較FWA-EI有明顯優(yōu)化.雖然IFWGA在運行時間上比GA稍長一些，但在可接受范圍內(nèi).IFWGA在運行時間上比FWGA快了一些，而且求解質量更高.證明IFWGA的改進和兩種變異算子的設置是有效的.

表3 運行時間對比 s

4 結論

目前生鮮農(nóng)產(chǎn)品配送存在求解結果差、運行時間長、早熟收斂等問題.為解決這些問題，首先，本文將碳排放成本和開/關門兩種狀態(tài)的貨損率引入生鮮農(nóng)產(chǎn)品配送路徑的傳統(tǒng)模型，提出了其改進模型.然后，將煙花算法與遺傳算法相結合，每代種群中的最優(yōu)解和最差解執(zhí)行煙花算法，產(chǎn)生爆炸火花和變異火花，以增加種群的多樣性.同時，為提高算法效率，兼顧全局搜索能力和局部搜索能力,設置了兩種步長的動態(tài)變異算子SSMO和LSMO,由此得到IFWGA算法.

最后，選取某生鮮連鎖超市的案例，從運行時間、求解質量、收斂速度方面，對GA、FWA-EI、FWGA和IFWGA 4種算法進行了對比測試.發(fā)現(xiàn)本文提出的IFWGA算法的收斂速度較快，變異算子設置較為合理，求解質量較高.