施文嘉, 邵竑湄, 唐迪, 胡書紅
(國網(wǎng)浙江省電力有限公司 電力科學(xué)研究院, 杭州 310000)
國內(nèi)外許多研究學(xué)者就冷鏈物流配送路徑的優(yōu)化進(jìn)行了廣泛關(guān)注[1-4],其中的要點(diǎn)與難點(diǎn)就在于車輛路徑的合理選擇問題。很多研究學(xué)者提出通過算法來解決這一問題,其中精確算法無法解決大規(guī)模車輛配送路徑的選擇處理問題,只善于求解小規(guī)模車輛問題[5];后來提出的啟發(fā)式算法[6]很好的解決了這一難題,但是又出現(xiàn)了收斂速度慢,易早熟等問題;為克服這一缺陷,通過對算法進(jìn)行改進(jìn)提出了遺傳學(xué)算法,但是遺傳學(xué)算法在解決車輛配送路徑優(yōu)化問題上存在效率低下的情況[7]?;谝陨峡紤],本文提出了基于優(yōu)化免疫算法來解決冷鏈物流配送路徑優(yōu)化問題。該算法使用廣泛,操作便捷,實(shí)用性強(qiáng),結(jié)合城市路網(wǎng),構(gòu)建冷鏈物流配送總成本最小數(shù)學(xué)模型,同時(shí),對冷鏈物流配送路徑優(yōu)化問題進(jìn)行建模研究。
生鮮產(chǎn)品在物流配送過程中,80%的損耗都是發(fā)生在運(yùn)輸配送環(huán)節(jié)。從節(jié)約成本的角度出發(fā),優(yōu)化配送路徑是降低冷鏈物流成本的突破口。在配送過程中一是有車輛油耗,二是有區(qū)別普通常溫配送的能源消耗。另外一方面,時(shí)間是影響貨物新鮮程度的最關(guān)鍵指標(biāo),相比于普通常溫配送,冷鏈物流由于產(chǎn)品本身具有的易腐性特點(diǎn)使得對冷鏈物流配送中的時(shí)間窗要求更為嚴(yán)格,這樣也就造成了產(chǎn)生懲罰成本的幾率大大增加。
冷鏈物流配送路徑優(yōu)化問題可以描述為:
1) 配送中心以及客戶的地理位置已知,配送中心有多輛車,且每輛車都配有冷凍、冷藏設(shè)備。
2) 從配送中心出發(fā),用m輛車向n個(gè)客戶進(jìn)行貨物配送,客戶到配送中心的距離為d0j(j=1,2,…,n),客戶之間的距離為dij(i,j=1,2,…,n)。每輛車的額定載荷是已知的,為wi(i=1,2,…,m),客戶對貨物的需求量是確定的,為ci(i=1,2,…,n),并且ci≤wi。
3) 根據(jù)客戶的要求以及時(shí)間安排合理安排車輛進(jìn)行貨物配送,使配送總成本最小。
在對實(shí)際問題進(jìn)行解決的過程中,有一些條件無法同時(shí)滿足,為簡化問題的處理描述,需要在進(jìn)行數(shù)學(xué)模型構(gòu)建前進(jìn)行一些條件假設(shè)與約束。
模型假設(shè):
1) 配送中心只有一個(gè);
2) 一個(gè)配送中心可以同時(shí)為多個(gè)客戶提供服務(wù),且貨物能夠滿足所有客戶的需求,同時(shí)配送中心的運(yùn)輸能力足以調(diào)配;
3) 車輛的自重不應(yīng)超過其額定載荷;
4) 車輛的最大行駛距離是確定的;
5) 在運(yùn)輸過程中車內(nèi)溫度保持不變,同時(shí)車輛在行駛過程中及打開車門時(shí)的貨損系數(shù)固定。
分配方案必須符合以下基本約束條件:
1) 在每個(gè)分配路徑上,所有客戶的總需求不超過分配車輛的額定負(fù)載;
2) 配送路徑的長度不超過分配車輛的最大行駛里程;
3) 每個(gè)客戶的貨物由一輛配送車進(jìn)行配送服務(wù);
4) 對每個(gè)客戶的配送時(shí)間都必須在約定的時(shí)間窗內(nèi)。
冷鏈物流配送總成本包括固定成本、運(yùn)輸成本、運(yùn)輸過程中的貨損成本、開車門的貨損成本、冷鏈配送懲罰成本以及制冷成本。
為了構(gòu)建數(shù)學(xué)模型,假設(shè)zp是由第p輛車服務(wù)的客戶數(shù);使用集合Sp來表示第p輛車的路線,其中元素spi表示客戶i在第p輛車配送路線中的順序,sp0=0作為配送中心。
1) 包括折舊費(fèi),人工費(fèi)等配送車輛的固定成本為式(1)。
C1=mf
(1)
其中,f是指每輛車的固定成本。
2) 與車輛的行駛的總路程成正比的運(yùn)輸成本為式(2)—式(8)。
(2)
約束條件:
(3)
0≤zp≤np=1,2,…,m
(4)
(5)
Sp={spi|spi∈{1,2,…,n}i=1,2,…,zp}
(6)
Sp1∩Sp2=? ?p1≠p2
(7)
其中,
(8)
3) 即使運(yùn)輸過程中保持低溫環(huán)境,依舊會(huì)造成生鮮產(chǎn)品一定的變質(zhì)損耗。運(yùn)輸過程中的貨損成本為式(9)。
(9)
其中,a為運(yùn)輸過程中的貨損系數(shù),g為貨物的價(jià)格,vip為0,1 變量,若第p輛車為i客戶提高服務(wù),則vip=1,否則vip=0。
4) 打開車輛車門時(shí),車內(nèi)冷空氣會(huì)和外界熱空氣進(jìn)行交換對流,造成車內(nèi)溫度升高,造成生鮮損耗。開車門的貨損成本為式(10)。
(10)
其中,b為打開車門的貨損系數(shù),Ri為每個(gè)客戶的貨物需求量。
5) 冷鏈配送懲罰成本
客戶對時(shí)間有一個(gè)要求的到達(dá)時(shí)間窗[mi,ni],還有一個(gè)可接受的時(shí)間窗[Mi,Ni],[mi,ni]?[Mi,Ni];當(dāng)?shù)竭_(dá)客戶i的時(shí)間ti早于Mi,則需等待到Mi才能完成配送,這期間產(chǎn)生的貨損該系數(shù)仍然為a;當(dāng)?shù)竭_(dá)客戶i的時(shí)間ti在Mi與ni之間,則不需要懲罰。當(dāng)?shù)竭_(dá)客戶i的時(shí)間ti在ni與Ni之間,則需付出一定的懲罰成本,懲罰系數(shù)為β。當(dāng)?shù)竭_(dá)客戶i的時(shí)間ti晚于Ni,則提供服務(wù)不成功,懲罰成本為該客戶需求貨物的總價(jià)格。冷鏈配送懲罰成本的表達(dá)式為式(11)。
(11)
6) 制冷成本為式(12)。
(12)
其中,pf為制冷劑單價(jià),F(xiàn)為制冷劑消耗量,tsp(i-1)spi為第p輛車從客戶(i-1) 到客戶i所用的時(shí)間。
綜上,冷鏈物流配送總成本最小數(shù)學(xué)模型表示如式(13)。
(13)
免疫算法是模擬生物免疫系統(tǒng)抗原抗體而生成的一種新型智能計(jì)算方法。免疫系統(tǒng)由抗原識(shí)別系統(tǒng)、記憶系統(tǒng)、抗體的加速和控制機(jī)制等組成,通過細(xì)胞分裂產(chǎn)生大量的抗體來抵抗各種抗原。免疫系統(tǒng)有很強(qiáng)的學(xué)習(xí)能力、識(shí)別能力及記憶能力,能夠辨別外界的有害信息,保證系統(tǒng)的安全穩(wěn)定性。并且免疫系統(tǒng)具有保持群體多樣性的特點(diǎn),因此免疫優(yōu)化算法能夠有效克服在尋求最優(yōu)解的過程中出現(xiàn)的“早熟”問題[8],從而獲得全局最優(yōu)解。
免疫算法流程圖如圖1所示。
實(shí)現(xiàn)步驟如下所示:
1) 分析問題。本文的研究目的是合理地確定配送車輛與客戶之間的關(guān)系,在滿足客戶需求、車輛載荷、時(shí)間窗等的約束條件下,求出最低總成本。
2) 抗原識(shí)別。本文將采用抗體與抗原之間的親和力大小來進(jìn)行識(shí)別。
3) 產(chǎn)生初始抗體群。以隨機(jī)產(chǎn)生的抗體及記憶庫存儲(chǔ)的抗體作為初始抗體群。
4) 抗體評價(jià)。本文將對每個(gè)抗體進(jìn)行評價(jià)。
5) 形成父代種群。按照個(gè)體期望繁殖概率進(jìn)行排序,排名靠前的N個(gè)個(gè)體將被選作父代種群,并選取其中的m個(gè)放入記憶庫。
6) 判斷結(jié)束與否。滿足條件結(jié)束,否則進(jìn)行下一步。
7) 新種群的產(chǎn)生。新種群由兩部分構(gòu)成,父代選擇、交叉、變異等操作形成一部分,再從記憶庫中取出來形成另一部分。
8) 新一代種群形成之后進(jìn)行循環(huán)操作。
在免疫算法對配送總成本最低的求解過程中,以目標(biāo)函數(shù)和約束條件為抗原,以其濃度為抗體。在免疫過程中,一些抗體作為記憶細(xì)胞被保留下來,當(dāng)同源抗原再次攻擊時(shí),記憶細(xì)胞會(huì)迅速爆炸產(chǎn)生大量抗體,產(chǎn)生更快的響應(yīng)。同時(shí),免疫系統(tǒng)具有自我調(diào)節(jié)功能,能維持抗體的多樣性和免疫系統(tǒng)的平衡[9]。
算法操作流程如下:
1) 抗原輸入和抗體編碼。
輸入抗原:目標(biāo)函數(shù)和約束條件。
為方便研究,減少無效解的產(chǎn)生,采用自然整數(shù)進(jìn)行編碼,形成抗體序列碼。對n個(gè)客戶進(jìn)行編號(hào),則路線可形成長度為n的抗體。如n=6,則抗體為(2,4,6,5,3,1),此抗體序列碼即表示,從配送中心0出發(fā),依次配送客戶2→4→6→5→3→1后,返回配送中心0,形成一條配送路徑。
2) 初始抗體群的產(chǎn)生
首次選擇時(shí),抗體隨機(jī)選擇。之后,部分初始抗體通過免疫系統(tǒng)的記憶功能從記憶庫中獲得,其余部分再由系統(tǒng)隨機(jī)生成[10]。由于記憶庫中的抗體具有較高的適應(yīng)度和較好的物種分布,因此可以提高收斂速度。
3) 親和度的計(jì)算
抗體與抗原間的親和度表示抗體對抗原的識(shí)別程度,當(dāng)抗體遇到抗原時(shí),它們越親和,那就越接近最優(yōu)解。本文的親和力函數(shù)表示為式(14)。
(8)
其中Yi為冷鏈物流配送路徑優(yōu)化的目標(biāo)函數(shù)。
這樣就將最小值問題轉(zhuǎn)化為目標(biāo)函數(shù)的最大值問題。
抗體與抗體間的親和度代表抗體之間的相似程度,抗體間的親和度表示為式(15)。
(15)
其中si,s表示兩個(gè)抗體間相同的位數(shù),L表示抗體的長度。L的長度由配送的客戶的數(shù)量決定,如兩個(gè)抗體分別為(1,6,5,3,2,4)和(4,7,6,5,8,9),兩個(gè)抗體有3個(gè)相同位數(shù),則親和度為0.5。
4) 抗體濃度的計(jì)算
抗體濃度代表相似抗體在整個(gè)種群中所占的比例。當(dāng)抗原或者新抗體攻擊免疫系統(tǒng)時(shí),免疫系統(tǒng)將產(chǎn)生激烈反應(yīng),產(chǎn)生大量抗體。隨著抗體的增加,其親和力就會(huì)上升。達(dá)到一定程度時(shí),其濃度就會(huì)降低[11]。即在優(yōu)化過程中,會(huì)導(dǎo)致優(yōu)化停滯,并收斂過早。
抗體濃度表示為式(16)。
(10)
5) 期望繁殖概率:促進(jìn)和抑制抗體產(chǎn)生
期望繁殖概率由抗體與抗原之間的親和度及抗體濃度來表示,期望繁殖概率Pi表示為式(7)。
(17)
從上式可以看出個(gè)體適應(yīng)度與期望繁殖概率成正比,個(gè)體濃度與期望繁殖概率成反比。這樣就既可以鼓勵(lì)高適應(yīng)度的個(gè)體的產(chǎn)生,又可以抑制高濃度個(gè)體的產(chǎn)生,從而保證個(gè)體的多樣性。
6) 交叉變異操作
群體更新的方法與遺傳算法基本相同。本文采用輪盤賭選擇機(jī)制進(jìn)行選擇操作,個(gè)體期望繁殖概率即個(gè)體被選擇概率。采用多點(diǎn)交叉的方式進(jìn)行交叉操作,從交叉操作中產(chǎn)生的抗體群中隨機(jī)選擇變異位進(jìn)行變異操作產(chǎn)生新的個(gè)體[12-13]。
本文以武漢某生鮮配送公司為例,對冷鏈物流配送路徑進(jìn)行研究。該公司共有3輛車,對9個(gè)市內(nèi)生鮮批發(fā)市場進(jìn)行生鮮配送供應(yīng)。每輛車額定載量均為w=4t,各參數(shù)數(shù)值如表1所示。配送中心與各批發(fā)市場之間、各批發(fā)市場之間的距離(km)及各批發(fā)市場貨物需求量(t)如表2所示,0代表配送中心,市場時(shí)間窗如表3所示。
表1 各參數(shù)數(shù)值
通過理論分析及數(shù)學(xué)建模,基于免疫優(yōu)化算法求解冷鏈物流配送路徑最優(yōu)問題,可以通過編程實(shí)現(xiàn),并通過對結(jié)果的分析,驗(yàn)證了算法的有效性。
初始代生成是隨機(jī)的,給定群N=40,最大進(jìn)化代數(shù)G=200 ,碼長L=27 ,交叉概率Pc=0.7,突變概率Pm=0.1。根據(jù)時(shí)間窗要求,預(yù)先設(shè)定客戶9為第一條線路的第一個(gè)客戶。通過編程,輸入約束條件,隨機(jī)求解6次,結(jié)果,如表4所示。
從計(jì)算結(jié)果可以看出,計(jì)算到61代時(shí),首次搜到最優(yōu)解,配送最低成本為2015.58元,且適應(yīng)度最高。配送路徑各個(gè)車次都按照相應(yīng)時(shí)間窗要求,將貨物送到,懲罰成本為0。當(dāng)前每輛車都達(dá)到85%以上的滿載,但每輛車服務(wù)的客戶較少,同時(shí)生鮮配送公司離各批發(fā)市場較遠(yuǎn),這樣就造成了在這段路程上成本的浪費(fèi)。另外一方面,每個(gè)批發(fā)商之間的距離是比較近的,從批發(fā)商到批發(fā)商之間耗費(fèi)時(shí)間是比較少的,我們可以通過合理安排時(shí)間窗,把運(yùn)輸車改為額定載量為5.5 t和6 t的貨車,這樣兩輛車就能完成所有貨物的配送,可以有效降低成本,減少資源浪費(fèi)。
表2 配送中心與各批發(fā)市場之間、各批發(fā)市場之間的 距離及各批發(fā)市場貨物需求量
表3 各批發(fā)市場時(shí)間窗
表4 冷鏈物流配送路徑優(yōu)化問題的免疫優(yōu)化算法求解結(jié)果
為:0→9→3→1→0; 0→5→2→6→0; 0→4→7→8→0;如表5所示。
表5 配載情況表
由此可得,免疫優(yōu)化算法可以方便有效地求得冷鏈物流配送路徑的最優(yōu)解,為實(shí)際應(yīng)用進(jìn)行指導(dǎo)。
本文研究了冷鏈物流配送路徑優(yōu)化問題?;诿庖邇?yōu)化算法,通過數(shù)學(xué)模型的建立,加入時(shí)間窗及車輛載荷等約束條件,快速求得最優(yōu)配送路徑。通過對實(shí)列的分析,可證明免疫優(yōu)化算法對冷鏈物流配送路徑問題求解是合理有效的,免疫優(yōu)化算法具有更高的收斂速度,沒有半早熟收斂,并且它可以在短時(shí)間內(nèi)搜索最佳路徑。通過抑制高濃度的抗體并添加新的高適應(yīng)度個(gè)體,免疫優(yōu)化算法可以維持抗體的多樣性。同時(shí),免疫優(yōu)化算法通過選擇交叉和變異操作來保持良好的本地搜索能力,是一種有效的路徑優(yōu)化方法。最后在具體實(shí)例中提出了更為合理的路徑安排方法,使得在配送過程中可以最大程度地節(jié)約成本,提升配送效率,保證生鮮產(chǎn)品的質(zhì)量。