樊倩 熊雷鳴 邵曉根 孔亮



摘要:為了響應國家低碳經(jīng)濟的號召,為了降低物流行業(yè)的成本,提高商品配送的質量和效率,該文提出了基于遺傳算法的生鮮配送的路徑優(yōu)化模型,并針對具體案例進行了仿真,初始的行駛距離為:210.76km,優(yōu)化后行駛距離為:80.4964km。該文提出的模型具有較高參考性和可行性,具有實際應用的價值。
關鍵詞:遺傳算法;生鮮配送;路徑優(yōu)化
中圖分類號:0229;F505;0224 文獻標識碼:A
文章編號:1009-3044(2020)01-0213-03
1背景
為了響應國家低碳經(jīng)濟的號召,各行各業(yè)都在最大限度地減少能源的使用。特別是物流行業(yè),隨著社會經(jīng)濟的不斷發(fā)展,物流配送業(yè)務也隨之提高,但是大量的能源在運輸過程中被消耗,運輸成本不斷上升。如何能夠在保證配送成本和消耗能源最小的情況下,提高商品配送的質量和效率,縮短生鮮在途時間是本文研究的主要內容。
2生鮮配送問題描述
目前生鮮配送主要由自營配送和建設配送網(wǎng)絡兩種構成。自營配送會產生成本的大量投入;建設配送網(wǎng)絡容易出現(xiàn)地區(qū)發(fā)展不協(xié)調的問題。
沒有做到合理的配送計劃,易造成配送成本得虛高。借助先進的物流管理理念、技術,建立合適的配送路徑優(yōu)化模型是目前配送系統(tǒng)面臨的主要問題。
考慮到這個問題,本文主要研究如何優(yōu)化現(xiàn)有的同城配送運輸網(wǎng)。優(yōu)化運輸網(wǎng),可以縮減成本,以下是該研究問題的示意圖:
3生鮮配送問題的模型的建立
如果要解決生鮮的配送路徑優(yōu)化問題,則該模型描述為:
1)車輛從暫存點出發(fā),送至客戶點,再返回暫存點;
2)滿足路徑上的需求量要求、車輛容載限制的約束;
與以往的車輛路徑問題不同的是,生鮮在配送的過程中,將會產生制冷成本,本文在研究這個優(yōu)化問題的時候需要將其考慮在內。
生鮮的配送問題,可以看作是一個多商旅問題(MTSP),可將其分成M個商旅問題(TsP)。
3.1模型的假設
在對生鮮的配送問題建模的過程中,為了保證模型準確性,運算的簡便性,本文做出以下幾點假設:
1)客戶的需求量已知;
2)配送車輛勻速行駛,行駛路徑固定;
3)在運輸范圍內不考慮生鮮腐壞的問題;
4)配送車輛的載重量一定,且能夠滿足客戶的需要量。
3.2模型的描述
生鮮暫存點,為n個客戶點提供生鮮配送服務;pi(i=1,2,…n)為第i個客戶的需求量;運送車的規(guī)定載重為O。
3.3模型的目標函數(shù)
配送車輛從暫存點出發(fā),送至多個客戶點,最后再返回暫存點。
1)配送車輛的運輸成本
運輸成本主要由以下兩個方面組成:一方面,固定成本co,這成本與行駛的距離無關;另一方面,變動成本c,這成本與行駛的距離有關:
4基于遺傳算法的生鮮配送問題的模型的求解
車輛路徑問題屬于NP-hard問題,參考文獻,本文選擇遺傳算法對問題進行求解。遺傳算法全局搜索能力強、求解時間少,避免了逐次逼近算法效率低下的問題,也避免了陷入局部最優(yōu)解。步驟如下:
4.1染色體編碼
編碼采用十進制的方式。采用一個隨機數(shù)列表示種群中的一個個體,作為染色體。
4.2初始種群設定
采用改良圈算法,解得一個初始種群。產生M個染色體(即可行解)。把這些可行解轉換成染色體編碼。這個初始種群規(guī)模應適當:規(guī)模太大,會影響搜索效果;規(guī)模太小,會容易陷入局部最優(yōu)解。
4.3適應度函數(shù)
適應度函數(shù)是一個有關目標函數(shù)的函數(shù),其目的是用來判斷個體的優(yōu)劣:
4.4遺傳操作
4.4.1選擇
在父代、子代種群中選擇適應度大的個體。適應度大的個體,將會被不斷被選中、進化到下一代。
4.4.2交叉
使用單點交叉的方式。在新的種群中隨機地選擇兩個個體,再隨機地選擇一個位置,兩者進行交叉互換。
4.4.3變異
按照給定的變異率,選擇發(fā)生變異的個體。隨機地選取該個體的一個基因段,將其隨機地插入余下的一個基因段中間,從而產生新的個體。
4.5終止原則
當算法迭代到指定的代數(shù)之后,停止運行,并將當前的最優(yōu)染色體作為最優(yōu)的解輸出。
5生鮮配送問題的模型的仿真
為了驗證本文所提出的算法是有效的,基于江蘇省徐州市的生鮮超市進行配送模擬仿真。
stepl:獲取生鮮商店的位置
首先,借助百度地圖的坐標拾取器,獲得徐州市130余家售賣生鮮食品的商店的地址及經(jīng)緯度。然后,將獲取的數(shù)據(jù)進行篩選,剔除數(shù)據(jù)缺失的項。同時,根據(jù)商店的實際經(jīng)營情況,選擇需要生鮮配送的大型商店。最終,選取了39家適合商店作為客戶點,其中包括:愛客來、悅客等連鎖便利店。將其繪制在地圖中,如下圖2所示:
step2:經(jīng)緯度轉換為距離
將經(jīng)緯度的單位為角度,利用Matlab中distance函數(shù)計算兩點與地心連線的夾角,再將角度乘以地球半徑6370km,即為徐州市客戶點之間的距離。
step3:對配送問題進行模擬仿真
根據(jù)客戶點地地理位置及城區(qū)規(guī)劃范圍,將MTSP問題轉化為3個TSP問題。求解該遺傳算法問題,將參數(shù)設定如下,種群的大小為M=19;最大的迭代次數(shù)G=1000;為保證種群能夠充分進化,交叉概率pc=1;一般來說,變異發(fā)生的可能性比較小,變異概率pm=0.1。最終,通過建立的模型,經(jīng)過Matlab計算得到結果,繪制出配送的初始路徑圖和配送的路徑優(yōu)化圖。
初始時行駛距離為:210.76km。由結果圖可以看出優(yōu)化過后的路徑更短,行駛的距離為:80.4964km。
6結束語
本文所研究的生鮮配送問題,除了考慮到距離最小之外,還考慮了生鮮在配送過程中的制冷所產生的成本,使得問題更加貼近實際生活。優(yōu)化現(xiàn)有的運輸網(wǎng)絡,降低成本,為企業(yè)的發(fā)展帶來更好的收益。