基于改進(jìn)螢火蟲(chóng)算法的農(nóng)產(chǎn)品物流配送路徑多目標(biāo)規(guī)劃研究

楊 松

(貴州大學(xué) 人民武裝學(xué)院 信息工程系，貴陽(yáng) 550025)

隨著電子商務(wù)的發(fā)展和物流業(yè)的興起，農(nóng)產(chǎn)品物流配送效率直接影響企業(yè)的物流配送成本和消費(fèi)者的滿意度。為了降低農(nóng)產(chǎn)品物流配送成本、滿足消費(fèi)者的需求，如何科學(xué)地規(guī)劃和部署農(nóng)產(chǎn)品物流配送路徑成為物流配送企業(yè)亟待解決的問(wèn)題。對(duì)于物流配送路徑規(guī)劃問(wèn)題，很多學(xué)者進(jìn)行了研究。王戰(zhàn)權(quán)等[1]將遺傳算法用于物流配送路徑規(guī)劃，與傳統(tǒng)的混合整數(shù)規(guī)劃法相比，遺傳算法求解物流配送路徑具有更高的搜索效率和更低的配送成本。趙冬玲等[2]提出了一種改進(jìn)的單點(diǎn)PMX交叉方法求解大規(guī)模的物流配送優(yōu)化模型，結(jié)果表明，該算法具有更快的收斂速度和最短配送路程和最低的配送成本。吳兵等[3]提出一種基于優(yōu)先權(quán)編碼的遺傳算法的物流中心選址優(yōu)化模型，該方法能夠有效降低求解選址問(wèn)題的復(fù)雜度。針對(duì)易腐物品的物流中心選址問(wèn)題，姜大立等[4]提出了一種基于AGA的整數(shù)規(guī)劃的物流中心選址數(shù)學(xué)模型，結(jié)果表明該算法可以增加獲得最佳配送路徑的概率。

為了降低農(nóng)產(chǎn)品物流配送成本，提高消費(fèi)者滿意度，實(shí)現(xiàn)農(nóng)產(chǎn)品物流配送路徑的合理規(guī)劃和調(diào)度。本文針對(duì)螢火蟲(chóng)算法(Firefly Algorithm，F(xiàn)A)存在局部最優(yōu)和收斂速度慢的缺點(diǎn)，提出一種云自適應(yīng)螢火蟲(chóng)算法，并將其應(yīng)用于農(nóng)產(chǎn)品規(guī)劃多目標(biāo)物流配送路徑的模型求解。選擇物流配送成本最低和路徑最短為目標(biāo)函數(shù)，將螢火蟲(chóng)位置編碼為車輛編號(hào)和車輛路徑順序，通過(guò)改進(jìn)的螢火蟲(chóng)算法規(guī)劃出農(nóng)產(chǎn)品多目標(biāo)物流配送的最佳路徑。

1 改進(jìn)的螢火蟲(chóng)算法

螢火蟲(chóng)算法[5]是基于螢火蟲(chóng)發(fā)光的生物特征提出的群智能算法。螢火蟲(chóng)的亮度I、吸引度β、螢火蟲(chóng)之間的距離rij分別定義為：

(1)

螢火蟲(chóng)位置更新數(shù)學(xué)公式為：

xi(t+1)=xi+β×(xj(t)-xi(t))+α×(rand-1/2)，

(2)

式中：xi(t)、xj(t)表示迭代次數(shù)為t時(shí)的螢火蟲(chóng)i和j的位置；xi(t+1)表示迭代次數(shù)為t+1時(shí)的螢火蟲(chóng)i的位置；γ為光強(qiáng)吸收系數(shù)；I0和β0分別為螢火蟲(chóng)的最大亮度和最大吸引度；α、rand為擾動(dòng)。

由于FA算法在后半段極容易出現(xiàn)由于局部最優(yōu)與全局最優(yōu)的左右搖擺而導(dǎo)致的局部最優(yōu)問(wèn)題，為了解決此問(wèn)題，運(yùn)用云模型[6]的隨機(jī)傾向性和穩(wěn)定性生產(chǎn)慣性權(quán)重引入FA，提出云自適應(yīng)螢火蟲(chóng)算法(Cloud Model Adaptive Firefly Algorithm，CMAFA)，云算子慣性權(quán)重w生成方式可以詳細(xì)描述為：

(3)

(4)

(5)

(6)

式中：k1、k2為控制系數(shù)。第k代慣性權(quán)重wk為[7]：

(7)

式中：慣性權(quán)重w的最小值wmin和最大值wmax。

CMAFA算法的螢火蟲(chóng)位置更新數(shù)學(xué)公式改進(jìn)為：

xi(t+1)=wxi+β×(xj(t)-xi(t))+α×(rand-1/2)，

(8)

其中，主要引入慣性權(quán)重w改進(jìn)基本FA算法的局部最優(yōu)問(wèn)題。

2 多目標(biāo)的物流配送路徑規(guī)劃

2.1 問(wèn)題描述

多目標(biāo)的物流配送路徑規(guī)劃問(wèn)題可以描述為[8-9]：對(duì)于配置了K輛農(nóng)產(chǎn)品物流運(yùn)輸車的倉(cāng)庫(kù)而言，每個(gè)物流車的最大承載力為qk，其中(k=1，2，3，…，K)，對(duì)于整個(gè)配送環(huán)節(jié)的L個(gè)配送點(diǎn)位，每個(gè)配送點(diǎn)位需要裝卸的農(nóng)產(chǎn)品需求量要求gi(max(gi)≤

max(qi))，要求物流車輛在時(shí)間為Ti內(nèi)完成該點(diǎn)位的農(nóng)產(chǎn)品配送裝卸需求，即每一個(gè)配送任務(wù)i必須在最早開(kāi)始時(shí)間TEi和最遲開(kāi)始時(shí)間TLi范圍內(nèi)完成。假設(shè)物流運(yùn)輸車比TEi點(diǎn)提前到配送點(diǎn)，則需要等待農(nóng)產(chǎn)品。反之，配送裝卸任務(wù)時(shí)間將增加。物流配送如圖1所示，配送點(diǎn)空間位置如圖2所示。

圖1 配送示意圖

圖2 配送點(diǎn)空間位置示意圖

2.2 數(shù)學(xué)模型

定義0為農(nóng)產(chǎn)品物流配貨倉(cāng)庫(kù)，1，2，3，…，L為農(nóng)產(chǎn)品對(duì)應(yīng)的配送點(diǎn)位對(duì)應(yīng)編號(hào)，設(shè)置i=(0，1，2，3，…，L)對(duì)應(yīng)任務(wù)以及中心倉(cāng)庫(kù)變化，使用式(9)獲得決策變量為[10]：

(9)

(10)

基于上述原理，生成農(nóng)產(chǎn)品多目標(biāo)物流車輛規(guī)劃路徑模型為：

(11)

(12)

(13)

(14)

式中：cij代表配送點(diǎn)i與配送點(diǎn)j之間運(yùn)輸花銷；si代表物流配送車到配送點(diǎn)i所需時(shí)長(zhǎng)；pE、pL分別代表農(nóng)產(chǎn)品物流運(yùn)輸車出現(xiàn)提前、延后抵達(dá)配送點(diǎn)i過(guò)程中單位時(shí)間內(nèi)所發(fā)生的成本。

本文模型匯總的全部配送點(diǎn)位均配套了物流車輛，而且對(duì)于每個(gè)點(diǎn)位與物流配送車站之間存在配送關(guān)系。

2.3 算法執(zhí)行流程

螢火蟲(chóng)的表達(dá)方式的合理構(gòu)建是實(shí)現(xiàn)本文規(guī)劃模型的核心所在。算法執(zhí)行過(guò)程中使用文獻(xiàn)[11-12]設(shè)計(jì)了一個(gè)2L維空間對(duì)應(yīng)L個(gè)配送點(diǎn)的農(nóng)產(chǎn)品配送任務(wù)。當(dāng)配送任務(wù)數(shù)為7，配送運(yùn)輸車為3時(shí)，配送任務(wù)編碼為[1 2 3 4 5 6 7]。使用圖3標(biāo)識(shí)對(duì)應(yīng)構(gòu)造的螢火蟲(chóng)位置向量X，圖3中螢火蟲(chóng)的位置可編碼為農(nóng)產(chǎn)品物流配送車輛和對(duì)應(yīng)的配送路徑。

圖3 農(nóng)產(chǎn)品配送車輛與路徑編碼示意圖

編號(hào)為1、2、3的農(nóng)產(chǎn)品配送車的規(guī)劃路徑分別為：1號(hào)車0、1、0；2號(hào)車0、4、5、3、2、0；3號(hào)車0、7、6、0。

基于改進(jìn)螢火蟲(chóng)算法的多目標(biāo)農(nóng)產(chǎn)品物流配送路徑規(guī)劃流程如圖4所示。

圖4 農(nóng)產(chǎn)品物流配送路徑多目標(biāo)規(guī)劃流程

3 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)選擇文獻(xiàn)[13-14]作為實(shí)驗(yàn)對(duì)象，通過(guò)實(shí)驗(yàn)論證本文模型的路徑優(yōu)化的合理性和有效性，其中設(shè)置用戶的配送點(diǎn)位以及中心倉(cāng)庫(kù)到各個(gè)配送點(diǎn)位距離矩陣如表1及表2所示。

表1 用戶需求

表2 距離矩陣

對(duì)比本文的CMAFA模型以及FA、GA，分別設(shè)置的算法參數(shù)為：1)CMAFA模型的初始參數(shù)：步長(zhǎng)變換參數(shù)α取值為0.5、設(shè)置100次的最大迭代次數(shù)，對(duì)應(yīng)的控制參數(shù)k1、k2取值為2。2)FA初始參數(shù)：步長(zhǎng)變換參數(shù)α取值為0.5、設(shè)置100次的最大迭代次數(shù)。3)GA初始參數(shù)[15]：設(shè)置種群規(guī)模popsize為50，交叉概率Pc取值為0.7、變異概率Pm取值為0.1、設(shè)置100次的最大迭代次數(shù)，對(duì)比實(shí)驗(yàn)對(duì)應(yīng)的結(jié)果如圖6～圖11所示。

圖5 距離矩陣圖

圖7 CMAFA尋優(yōu)收斂圖

圖8 FA配送路徑

圖9 FA尋優(yōu)收斂圖

圖10 GA配送路徑

圖11 GA尋優(yōu)收斂圖

由表3和圖6～圖11可知，與FA和GA相比，本文提出的CMAFA模型的搜索時(shí)間以及平均搜索耗能等方面，成本最小、效率最佳。另一方面，CMAFA模型的搜索成功率達(dá)到了67%，而FA與GA分別為46%和25%，進(jìn)一步證明了本文提出的CMAFA模型對(duì)于農(nóng)產(chǎn)品配送物流路徑的規(guī)劃方面具有較好的效果。

4 結(jié)論

本文對(duì)螢火蟲(chóng)算法進(jìn)行了改進(jìn)，建立了一種對(duì)農(nóng)產(chǎn)品規(guī)劃多目標(biāo)物流配送路徑的模型。針對(duì)傳統(tǒng)螢火蟲(chóng)存在局部最優(yōu)和收斂速度慢的缺點(diǎn)，提出一種自適應(yīng)螢火蟲(chóng)算法。實(shí)驗(yàn)數(shù)據(jù)顯示，對(duì)比經(jīng)典的FA、GA等模型，本文提出的CMAFA模型的搜索時(shí)間以及平均搜索耗能等方面，成本最小、效率最佳。為農(nóng)產(chǎn)品物流配送路徑規(guī)劃研究提供了新的思路和方法。