基于改進遺傳算法的農(nóng)產(chǎn)品物流配送模型研究①

汪 曄

(安徽商貿(mào)職業(yè)技術(shù)學(xué)院,安徽 蕪湖 241000)

0 引 言

在物質(zhì)經(jīng)濟水平不斷提升的背景下,人們對安全、綠色的農(nóng)戶品的需求逐漸提高。因此,農(nóng)產(chǎn)品物流配送問題成為如今諸多領(lǐng)域?qū)W者共同探討的話題。相較于大多數(shù)發(fā)達國家,我國農(nóng)產(chǎn)品采摘、運輸?shù)拳h(huán)節(jié)的損耗率處于較高水平,損耗率數(shù)值高達30%?，F(xiàn)階段國際農(nóng)產(chǎn)品物流模式的主體為農(nóng)協(xié)的縣協(xié)組織和全國性組織,以及基層組織[1-3]。針對農(nóng)產(chǎn)品物流模型,國內(nèi)外大多數(shù)學(xué)者已經(jīng)采用遺傳算法等啟發(fā)式算法對其進行求解,但模型的求解結(jié)果并沒有獲得物流企業(yè)和客戶等多方面的認可。研究構(gòu)建了一種農(nóng)產(chǎn)品物流配送模型,并提出一種優(yōu)化的遺傳算法對其進行求解,旨在為電子企業(yè)物流配送的創(chuàng)新提供技術(shù)支持。

1 農(nóng)產(chǎn)品物流配送模型及求解

1.1 農(nóng)產(chǎn)品物流配送模型

農(nóng)產(chǎn)品物流配送車輛路徑問題可視為一種常見的組合優(yōu)化問題,其分析的是在客戶需求和地理位置確定的情況下,通過數(shù)學(xué)模型生成成本最低的車輛路徑。圖1是指農(nóng)產(chǎn)品物流配送路徑問題的示意圖。該問題可以結(jié)合時間窗的車輛路徑問題來分析[4]。因此,農(nóng)產(chǎn)品物流車輛配送路徑問題可視為帶有軟時間窗的車輛路徑規(guī)劃問題。軟時間窗并沒有對時間有較高的要求,它可允許運輸車輛在時間窗外到達。但當(dāng)車輛提前到達預(yù)約地點,則會存在等待成本;否則將會出現(xiàn)懲罰成本。式(1)是指成本函數(shù)。

(1)

式(1)中,在服務(wù)客戶i時,車輛k由于時間窗約束而導(dǎo)致的損失。車輛k到達客戶i的時間點,客戶i的時間窗為[T1(i),T2(i)],T1(i)和T2(i)分別是指用戶i最早時間和最晚時間,分別是指車輛提前到達或延時到達的單位等待成本值和單位懲罰成本值。sik={0,1},當(dāng)sik的取值為1時,則表明車輛k能給客戶提供配送運輸服務(wù);而當(dāng)sik的取值為0時,則表明車輛k無法為客戶提供配送運輸服務(wù)。車輛路徑問題的構(gòu)成要素可分為目標(biāo)函數(shù)、運輸網(wǎng)絡(luò)、約束條件、客戶、配送中心、運輸貨物、運輸車輛。

物流配送系統(tǒng)中,配送中心可以為一個或者多個,配送中心的位置也具有隨機性。對于配送中心而言,配送貨物既可以是單種類,也可以是多種類的,同時它所供應(yīng)的貨物既可以滿足部分客戶的要求,也可以滿足所有客戶的需求。圖2是指物流配送中心選址的因素,主要包括交通狀況、經(jīng)濟效應(yīng)、環(huán)境因素、其他因素等?？蛻羰切枨蠹安糠旨s束條件的制定者,也是車輛路徑問題中需考慮的重要因素。這里面包括最大載重約束、特定貨物的到達和取走時間等約束條件。約束條件如下所示,符合客戶對貨物品種、質(zhì)量、數(shù)量的限制;符合客戶對貨物到達時間的要求;實際載重得不低于核載的重量。運輸網(wǎng)絡(luò)是指車輛路徑問題中所需關(guān)注的主要因素,運輸網(wǎng)絡(luò)由無向邊、有向弧、頂點組成。農(nóng)產(chǎn)品物流車輛配送問題的目標(biāo)函數(shù)為配送總體成本最小、客戶對配送服務(wù)滿意度高、運輸車輛配送所行駛的距離最小、參與運輸?shù)能囕v最少。

圖1 農(nóng)產(chǎn)品物流配送路徑問題的示意圖

總成本包括車輛的運輸成本和時間成本,其中運輸成本包括行駛總成本。時間成本具體為運輸車輛延時到達的懲罰成本和提前到達所需的等待成本。式(2)是指目標(biāo)函數(shù)的計算表達式。

(2)

式(2)中,客戶數(shù)量和運輸車輛的數(shù)目為n和m,配送車輛的單位距離成本和單位啟用成本分別為α和β,cij是指客戶i和j之間的距離,xijk是指客戶i和j是否由車輛k配送。

圖2 物流配送中心選址的因素

1.2 改進遺傳算法求解

針對農(nóng)產(chǎn)品車輛配送問題,常見的求解方法為精確算法和啟發(fā)式算法。遺傳算法具存在初始解隨機化、收斂速度慢、局部最優(yōu)解等問題。研究針對這些問題進行了改進,圖3是指改進遺傳算法的示意圖。首先依據(jù)農(nóng)產(chǎn)品物流配送模型的特點,編碼方式選擇整數(shù)編碼。然后根據(jù)客戶服務(wù)的優(yōu)先級別和影響因素確定存在解集的初始種群。其次,依據(jù)不同的目標(biāo)函數(shù)確定相應(yīng)的適應(yīng)度函數(shù),并利用適應(yīng)度確定個體的遺傳幾率。再者,采用精英保留策略進行選擇操作。接著,交叉操作和變異操作個體的自適應(yīng)概率。最后,持續(xù)迭代遺傳操作,當(dāng)適應(yīng)度函數(shù)不再變化或到達最大迭代次數(shù)時結(jié)束迭代。研究以非冗雜性、健全性、完備性作為恒量標(biāo)準(zhǔn),結(jié)合農(nóng)產(chǎn)品配送路徑模型的特點確定整數(shù)編碼作為編碼方式。

圖3 改進遺傳算法的示意圖

圖4 配送中心及客戶需求點位置圖

在種群初始化方面,研究在分析客戶優(yōu)先順序的基礎(chǔ)上構(gòu)建初始種群。式(3)是指客戶優(yōu)先關(guān)系的確定公式,即評價函數(shù)E(i)。

(3)

式(3)中,權(quán)重系數(shù)為ω1,ω2,ω3,t0i和coi分別是指配送中心與客戶點i的時間和距離。對于適應(yīng)度的計算,研究將目標(biāo)函數(shù)的倒數(shù)作為模型的適應(yīng)度函數(shù)。研究為了克服農(nóng)產(chǎn)品物流配送模型中的問題,以及保留種群中優(yōu)秀個體并變異獲得更優(yōu)秀的個體,對交叉和變異概率兩個參數(shù)進行優(yōu)化。遺傳算法中,交叉概率pc的變化公式為式(4)。

(4)

式(4)中,k1和k2均為取值范圍在(0,1)中的改變系數(shù),等待交叉兩個個體適應(yīng)度值中較高的適應(yīng)度值為f′,favg是指每代種群的平均適應(yīng)度。變異概率pm的計算公式為式(5)。

(5)

式(5)中,k3和k4均為取值范圍在(0,1)中的改變系數(shù),f是指等待變異的個體適應(yīng)度。聯(lián)合式(4)和式(5)可知,當(dāng)群體的最大適應(yīng)度和個體的適應(yīng)度相同時,交叉和變異概率均為0。這種調(diào)節(jié)方式在進化的末期具有一定的適用性,但在進化前期很容易陷入局部最優(yōu)解?；谧赃m應(yīng)調(diào)節(jié)方式的缺點,研究提出了改進的遺傳算法。常見的選擇策略為輪盤賭選擇、隨機競爭選擇等。研究選取最為經(jīng)典的輪盤賭法[9-12]。研究使用部分匹配交叉,克服一點交叉信息小而帶來的較大偏差,以及多點交叉和一致交叉計算工作量的問題。對于變異算子而言,其通常和交叉操作聯(lián)合應(yīng)用,研究使用倒位變異。

2 改進遺傳算法在農(nóng)產(chǎn)品物流配送模型求解中的應(yīng)用效果

研究采用部分Solomon算例作為數(shù)據(jù)來源分析農(nóng)產(chǎn)品物流配送模型求解結(jié)果。該算例包括C型、R型、RC型三部分數(shù)據(jù)集,不同數(shù)據(jù)集的區(qū)別點為客戶的坐標(biāo)和時間窗不同。研究利用R101數(shù)據(jù)庫中的50條數(shù)據(jù),某地有一個大型農(nóng)產(chǎn)品配送中心,周圍有49個地理坐標(biāo),且每個位置對農(nóng)產(chǎn)品的到達時間有著不同需求,如圖4所示。設(shè)置運輸車輛的單位啟用成本為60元/(km.輛),每輛車的單位距離成本為8元/(km.輛),配送中心的配送車輛為10輛。

表1是指遺傳算法和改進遺傳算法在農(nóng)產(chǎn)品物流配送模型中的求解結(jié)果。在農(nóng)產(chǎn)品物流配送模型求解過程中,遺傳算法和改進遺傳算法的最優(yōu)解分別為16087.9元和15129.6元,最優(yōu)配送路徑分別有9條和10條。

圖5是指遺傳算法改進前后的迭代圖。遺傳算法和改進遺傳算法達到最優(yōu)解的迭代次數(shù)分別為377代和321代。改進遺傳算法的最優(yōu)適應(yīng)度值隨著迭代次數(shù)的增加而逐漸降低,迭代過程中不斷出現(xiàn)穩(wěn)定的適應(yīng)度值,出現(xiàn)的迭代次數(shù)分別是68次,101次,151次,321次,相應(yīng)的適應(yīng)度值分別為18725.6,17021.5,16583.7,15129.6。而遺傳算法在迭代次數(shù)從300次開始,迭代曲線呈現(xiàn)急劇下降趨勢。

圖5 遺傳算法改進前后的迭代圖

為了驗證結(jié)合改進遺傳算法的農(nóng)產(chǎn)品物流配送效果,研究設(shè)置對比算法進行分析。通過6個數(shù)據(jù)集進行仿真分析,結(jié)果如圖6所示。從圖中可知,四種智能啟發(fā)式算法均經(jīng)過300次迭代后達到收斂,相比較于其他啟發(fā)式算法而言,改進遺傳算法的最優(yōu)目標(biāo)函數(shù)值為最具有優(yōu)勢。在R101,R103,C101,C103,RC101,RC103六種實例中,改進遺傳算法的最低目標(biāo)成本值為15129.6元,12758.3元,15426.3元,12654.3元,14895.5元,12654.8元。與傳統(tǒng)遺傳算法相比,改進遺傳算法具有一定的有效性和合理性,并表現(xiàn)出一定的優(yōu)化效果。

圖6 不同啟發(fā)式算法的農(nóng)產(chǎn)品物流配送效果

3 結(jié) 論

針對農(nóng)產(chǎn)品物流配送過程中多目標(biāo)優(yōu)化問題,研究利用改進遺傳算法對農(nóng)產(chǎn)品物流配送模型進行求解。實驗結(jié)果表明,在R101,R103,C101,C103,RC101,RC103六種實例中,改進遺傳算法的最低目標(biāo)成本值為15129.6元、12758.3元,15426.3元,12654.3元,14895.5元,12654.8元。該模型求解方式為農(nóng)產(chǎn)品物流配送路徑優(yōu)化問題的解決提供新的研究方向,可應(yīng)用于新鮮農(nóng)產(chǎn)品的運輸環(huán)節(jié)。但受限于研究時間,研究在對遺傳算法進行優(yōu)化過程未考慮算法的復(fù)雜程度對運算效率的影響。

參考文獻:;

[1] 魏慶豪,吳憲. 基于客戶滿意度的農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J]. 湖北農(nóng)業(yè)科學(xué),2020,59(24):189-194.

[2] 宋志蘭,黃益,孔民警,等. 基于TOPSIS和GRA的生鮮農(nóng)產(chǎn)品物流配送中心選址研究 —以某地生鮮農(nóng)產(chǎn)品配送中心選址為例[J]. 物流技術(shù),2019,38(12):49-53+102.

[3] 夏文匯,張霞,夏乾尹. 城市生鮮農(nóng)產(chǎn)品電商冷鏈物流配送模式及協(xié)同機制[J]. 江蘇農(nóng)業(yè)科學(xué),2019,47(4):321-325.

[4] 丁秋雷,胡祥培,姜洋,等. 考慮新鮮度的農(nóng)產(chǎn)品冷鏈物流配送受擾恢復(fù)模型[J]. 系統(tǒng)工程理論與實踐,2021,41(3):667-677.