基于改進(jìn)遺傳算法的生鮮農(nóng)產(chǎn)品物流配送路徑優(yōu)化

陳鑫影，李依琳，肖司義

(大連交通大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，遼寧 大連 116028)

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

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

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

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

(1)固定成本

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

(1)

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

(2)運(yùn)輸成本

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

(2)

(3)懲罰成本

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

(3)

(4)貨損成本

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

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

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

(4)

在車輛到達(dá)客戶點(diǎn)時(shí)需要開(kāi)門(mén)卸貨，開(kāi)門(mén)狀態(tài)下的貨損成本C42,見(jiàn)式(5).

(5)

C4=C41+C42

(6)

(5)制冷成本

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

用熱負(fù)荷來(lái)表示關(guān)門(mén)狀態(tài)的制冷劑消耗量.本文引入轉(zhuǎn)化系數(shù),用Qk1來(lái)表示k車運(yùn)行時(shí)的熱負(fù)荷，Qk2表示k車開(kāi)門(mén)狀態(tài)下傳入的熱量，C51表示關(guān)門(mén)狀態(tài)下的制冷成本，C52表示開(kāi)關(guān)門(mén)過(guò)程中的制冷成本，見(jiàn)式(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的時(shí)間；α代表了開(kāi)門(mén)的頻率,其取值見(jiàn)表1.

表1 開(kāi)門(mén)頻度系數(shù)

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

C5=C51+C52

(11)

(6)碳排放成本

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

(12)

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

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

E1=e0ρ(X)d

(13)

E2=wXd

(14)

(15)

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

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

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

(16)

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

2.1 算法設(shè)計(jì)思路

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

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

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

2.2 算法流程

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

2.2.1 染色體編碼

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

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 選擇

選擇操作采用輪盤(pán)賭選擇法,并在選擇過(guò)程中引入精英保留策略.

2.2.3 交叉

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

2.2.4 變異

變異操作采用交叉變異,將兩個(gè)隨機(jī)選中的點(diǎn)進(jìn)行交叉變異 ,這種變異方法適用于固定位置關(guān)系的問(wèn)題[14].

2.2.5 煙花算法

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

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

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

(17)

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

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

Smax=round(M·0.8)

(18)

Smin=round(M·0.1)

(19)

(2)計(jì)算爆炸半徑

爆炸半徑與個(gè)體適應(yīng)度有關(guān)，適應(yīng)度優(yōu)的個(gè)體半徑更小，爆炸半徑Ai見(jiàn)式(20).

(20)

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

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

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

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

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

(21)

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 求解質(zhì)量對(duì)比

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

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

(a) 遺傳算法(GA)

表2 總成本對(duì)比

3.2.2 收斂速度對(duì)比

為對(duì)比GA、FWA-EI、FWGA和IFWGA的收斂速度，截取了4種算法的迭代曲線圖，并總結(jié)了4種算法達(dá)到最優(yōu)解的代數(shù)，見(jiàn)圖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代就達(dá)到最優(yōu).

3.2.3 運(yùn)行時(shí)間對(duì)比

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

表3 運(yùn)行時(shí)間對(duì)比 s

4 結(jié)論

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

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