基于禁忌搜索算法的生鮮冷鏈物流配送路徑優化研究

高萬晨,王宇楠

(遼寧對外經貿學院 經濟學院,大連 116052)

近年來,我國居民對生鮮農產品的需求量逐年增長,冷鏈物流應運而生,企業如何降低配送成本,消費者如何盡快收到生鮮農產品并保證產品質量變得至關重要,也成為了研究熱點。在配送過程中,應將節能減排、制冷、貨損、懲罰成本等因素考慮到構建配送路徑優化模型中,采用合理地算法進行求解,進而獲取最優的配送路徑,以達到綜合效益最優。

就配送模型而言,DANTZIG于1959年首次提出車輛路徑問題(VRP),即將需要配送的物品按照某種次序由1輛車進行配送作業且被準時送達。此類問題一般假設各節點的距離和位置坐標、車輛最大載重量等參數已知,以配送總成本最小為目標進行路徑優化[1]。隨著研究的不斷深入,麻存瑞等基于車輛路徑優化問題,建立了快遞配送的路徑優化模型,設計了考慮快遞量、車輛最大載重量等約束的遺傳算法,通過實際案例驗證了所建模型和算法設計的有效性[2]。就算法而言,學者們采用了禁忌搜索[3]、改進遺傳[4]、自適應大鄰域搜索[5]、改進蟻群[6]、NSGA-II[7]、粒子群[8]等算法對模型進行求解。

VRP雖然在解決“最后一公里”配送問題上具有一定的優勢,但目標函數考慮因素較少,以致所得配送路徑不夠好,因此,部分學者把時間窗因素考慮到VRP中,把問題轉換成了考慮配送時間窗的VRP問題(VRPTW),即將各節點可接受的配送時間考慮到優化模型中,且各客戶節點的時間窗上、下限均已知,車輛從配送中心出發向帶時間窗約束的各客戶節點進行物品配送,以獲得總成本最優的配送路徑。其中,各客戶節點的時間窗可以分為硬時間窗與軟時間窗。硬時間窗是車輛到達某一客戶節點的時間超過了其可接受時間,將導致配送損失為無窮大[9],而軟時間窗是將車輛早到或晚到各客戶節點的懲罰予以適當增大[10]。

快遞進行配送作業時車輛會產生一定的溫室氣體,是全球溫室氣體排放的來源之一,因此,將碳排放因素考慮到配送路徑優化模型中具有一定的理論和現實意義[11]。鄧紅星等將碳排放考慮到生鮮農產品冷鏈物流配送路徑優化模型中,分別計算不考慮碳排放和考慮碳排放的生鮮農產品冷鏈物流路徑優化方案[12]。

目前,國內諸多生鮮農產品原產地的冷鏈物流存在基礎設施建設不完善等問題,各環節比較容易出現農產品冷鏈脫節的現象,會引起農產品溫度的變化,進而導致生鮮農產品有冷鏈保存的損害比沒有更大。劉雨平基于農產品冷鏈物流基礎設施等問題提出了解決對策[13]。在生鮮產品的運輸和配送過程中,如果想讓其有更好的保鮮周期,那么從賣家到買家必須全程冷鏈,部分學者僅在配送中心至買家過程中考慮冷鏈,將制冷成本[14]和貨損成本[14-15]考慮到目標函數中,而忽視了從賣家到配送中心之間的成本。

綜上所述,本文在研究單個配送中心的從配送中心到買家的生鮮冷鏈物流配送路徑優化問題基礎上,增加了從賣家到配送中心之間的成本,建立了考慮從賣家至買家全過程鏈的總成本最小的數學模型,運用禁忌搜索算法對其進行求解,尋找最優的配送路徑,為快遞企業的科學配送和制定降本增益管理策略提供理論依據和技術參考。

1 配送路徑優化模型

1.1 問題描述

生鮮農產品具有不耐高溫、易腐爛變質等特點,如果未采用科學合理的包裝、運輸和配送方式,將會造成損壞,進而導致客戶的滿意度降低,增加快遞企業的運營成本。因此,研究單個配送中心的從賣家至買家全過程鏈的生鮮冷鏈物流配送路徑優化問題具有重要意義,具體的物流系統如圖1所示。

圖1 全過程鏈的物流系統網絡結構

1.2 假設條件

1) 配送中心具有一定數量同一種型號的冷藏車。

2) 冷藏車需要從配送中心出發,當完成某次配送任務后,需要返回配送中心。

3) 各客戶節點(買方)只能接受1輛冷藏車為其進行配送,且需求量不能超過冷藏車的最大載荷。

4) 各客戶節點的地理坐標、時間窗上下限、產品需求量等均已知。

5) 賣方節點之間距離較近,近似為一個綜合的賣方節點。

6) 村莊快遞點、區域匯總點、分撥中心和配送中心的個數均唯一。

7) 賣方節點至村莊快遞點、村莊快遞點至區域匯總點、區域匯總點至分撥中心、分撥中心至配送中心之間路徑唯一,且距離已知。

8) 配送中心前序節點的成本只考慮運輸成本,裝卸成本忽略不計。

1.3 模型

綜上,可以構建一個考慮碳排放、燃油消耗、制冷、貨損和違反各客戶節點配送時間窗的懲罰成本的生鮮冷鏈物流配送優化模型,該模型以總成本最小為目標,主要包括從賣方節點到配送中心之間的成本和配送中心到買方節點間的成本,具體如下。

1.3.1 配送中心至買方節點之間的成本

1) 碳排放與燃油消耗成本C1。冷藏車在行駛的過程中,將會產生一定的碳排放和燃油消耗成本,二者均與燃油消耗量有一定的聯系。本文采用負載估計法計算燃油消耗量,見式(1)。

(1)

式中:ρ(M)為冷藏車載有貨物質量為M時的單位距離的燃油消耗量;ρ0為冷藏車空載時每千米消耗的燃油量;ρ*為冷藏車滿載時每千米消耗的燃油量;M為貨物質量;Q為冷藏車輛的最大載荷。

設快遞員駕駛冷藏車完成所有客戶節點的配送作業后的總燃油消耗量為f,基于式(1),構建總燃油消耗成本,見式(2)。

(2)

式中:i,j為節點,V為節點集合,i,j∈V,i,j=1,…,m,…,N,其中,1為配送中心,m為賣方綜合節點;V’為客戶節點集合,V’=V/{1,m};K為冷藏車輛集合,k為冷藏車輛,k=1,…,K;xijk為0-1變量,冷藏車從客戶節點i至客戶節點j時值為1,否則值為0;Qij為客戶節點i到客戶節點j時的生鮮貨物載重量;Dij為客戶節點i與客戶節點j之間的距離。

基于式(1)和式(2),得到碳排放與燃油消耗成本,見式(3)。

C1=αf+υωf=(α+υω)f

(3)

式中:α為燃油(柴油)價格;υ為碳稅;ω為碳排放系數。

2) 制冷成本C2。冷藏車輛在運輸和配送過程中,具有可靠性、安全性等特點,能盡量保障生鮮農產品不受損壞。冷藏車的制冷成本主要由運輸階段與裝卸階段兩部分構成,配送階段的總制冷成本見式(4)。

(4)

式中:η1為在運輸過程中冷藏車制冷劑消耗系數;η2為在裝卸過程中冷藏車制冷劑消耗系數;tij為客戶節點i到客戶節點j的行駛時間;Ti為冷藏車在客戶節點i的服務時間;yik為0-1變量,客戶節點i的需求被冷藏車k滿足時值為1,否則值為0。

3) 貨損成本C3。生鮮農產品在運輸和裝卸的過程中容易造成產品的損壞或破損,因此,將生鮮農產品在運輸和裝卸過程中因產品損壞所造成的成本稱之為貨損成本,并將其考慮到目標函數中,為企業在運輸和裝卸搬運階段制定生鮮農產品貨損成本控制策略、提升配送質量等提供科學依據。生鮮農產品的總貨損成本見式(5)。

(5)

式中:P為生鮮農產品的單位價格;qi為客戶節點i的需求量;ti為冷藏車到達客戶節點i的時間;t1為冷藏車從配送中心出發的時間;Q′i為冷藏車駛離客戶節點i所剩余的生鮮貨物質量;σ1為在運輸過程中生鮮貨物新鮮程度的衰減系數;σ2為在裝卸過程中生鮮貨物新鮮程度的衰減系數。

4) 懲罰成本C4。當冷藏車進行配送作業前,需要與客戶商定一個可接受的時間范圍,即時間窗。時間窗的左、右側分別代表客戶最早和最晚接收貨物的時間。若快遞員沒有按照客戶可接收貨物時間窗的范圍進行送貨,將給予一定的懲罰,見式(6)。

(6)

式中:Ei為各客戶節點可接受的時間窗下限;Li為各客戶節點可接受的時間窗上限;ξ1為冷藏車到達各客戶節點的時間早于各客戶節點所能接受的時間窗下限時對應的懲罰系數;ξ2為冷藏車到達各客戶節點的時間晚于各客戶節點所能接受的時間窗上限時對應的懲罰系數。

1.3.2 賣方節點至配送中心之間的成本C5

由于生鮮農產品從賣家至村莊快遞點、村莊快遞點至區域匯總點、區域匯總點至分撥中心、分撥中心至配送中心這個過程中已經產生了運輸成本,因此,需要將此過程成本加入到目標函數中,使總成本計算更加科學、合理。此過程的成本主要包括燃油消耗和碳排放成本、制冷成本和貨損成本三部分,見式(7)。

(7)

1.3.3 目標函數

綜上,在運輸和配送過程中,基于上述成本構建目標函數,并給予各成本一個系數λi,λi為0-1變量,以便目標函數適用于不同應用場景,具體如下所示。

minZ=λ1C1+λ2C2+λ3C3+λ4C4+λ5C5=

1.3.4 約束條件

tj=ti+Ti+tij,?i,j∈V

第1、第2個約束條件為各客戶節點僅能允許某輛冷藏車出發和到達1次;第3個約束條件為冷藏車輛從配送中心出發在完成配送作業后回到配送中心;第4個約束條件為各客戶節點僅能被某輛冷藏車訪問1次;第5個約束條件為消除子回路;第6個約束條件為冷藏車從某一客戶節點到另一客戶節點應該滿足的時間條件;第7個約束條件為冷藏車的載重容量限制。

2 算法設計

2.1 禁忌搜索算法設計過程

禁忌搜索算法(簡稱TS)的基本求解思想如圖2所示。算法中涉及到的初始化、初始解構建、鄰域解、禁忌表、藐視準則、適應度值計算等如下所示。

圖2 禁忌搜索算法基本求解思想

2.1.1 算法初始化

讀取所有數據,同時初始化每一條路徑Ri(Ri∈E,i=1,…,n),將路徑的末端節點VN設定為配送中心,且配送中心的起始節點V1的最早與最晚時間均為配送中心的最早到達時間E1,末端節點均為配送中心的最晚到達時間L1,同時計算任意兩節點之間的歐氏距離。編碼方式如下:配送路徑節點集合V包含配送中心在內一共N個,起始節點和終止節點均用“1”表示,其余各節點分別用2至N-1表示,如圖3所示。

圖3 算法初始化過程

2.1.2 初始解構建

由于冷藏車容量有限制,因此,以滿足冷藏車容量約束為目的進行隨機初始化,即隨機選取一個節點i插入到第R條路徑中。如果超過冷藏車的容量限制約束,則將當前節點i插入到第R+1條路徑,且插入路徑的位置由該條路徑中已經存在的各個節點的最早到達時間的升序所決定,如圖4所示。

圖4 初始解構建過程

2.1.3 鄰域解

基于當前解x,采取插入算子產生所有鄰域解,選取當前解中2條路徑為例介紹具體插入操作:從第R條路徑中隨機選擇節點i,再選擇路徑R+1,保證節點i插入路徑R+1后,路徑R+1滿足冷藏車的容量約束,然后在路徑R+1中,找到節點j,使得節點j滿足Ej≤Ei≤Ej+1,如圖5所示。

圖5 鄰域解求解過程

2.1.4 禁忌表與藐視準則

圖6 禁忌表與藐視準則

2.1.5 適應度值計算

將模型中的目標函數值作為適應度值計算的依據,因此,把當前解xi帶入模型中,將計算結果作為當前解的適應度值,適應度值越小,則表示解的質量越高。

2.2 禁忌搜索算法求解步驟

Step1:參數和算法初始化。輸入優化模型中所需要qi,f,ti,M,α,ω等參數值,迭代次數I=0,最大迭代次數I_max=1000,禁忌長度T_L=20,禁忌表T=Φ。

Step2:隨機產生初始解x,令最優解x*=x,最優值Z(x*)。

Step3:若G(x)-T=Φ,則停止計算,否則,令I=I+1,若I>I_max,則停止計算,輸出x*和Z(x*)。其中,G(x)為x的鄰域解集。

Step4:若Z(gI(x))=min{Z(g(x))∣g(x∈G(x)-T)},令x=gI(x),更新Z(x),Z(x)是當前鄰域的最優目標函數值,其中,gI(x)為第I次迭代不在T中的鄰域中的最優解。

Step5:若Z(gL(x))

Step6:若Z(x)

Step7:更新T表,轉至Step3。

3 算例驗證與結果分析

A快遞公司位于遼寧省大連市,是一家以配送、運輸為主體的第三方生鮮冷鏈物流公司,選擇A快遞公司其中一個配送中心B作為研究對象,B配送中心擁有10臺同一種型號的冷藏車。該公司主要以運輸和配送櫻桃為主,每天將櫻桃從賣方節點運送到配送中心,再由配送中心將貨物盡可能保質保量地準時送到買方手中。目前,公司在運營過程中的基本參數信息見表1。

表1 具體參數信息

考慮到成本與配送路徑選擇有關,所以對車輛的路徑進行合理規劃,各客戶節點位置、可接受時間窗、需求量等參數見表2和圖7,配送中心序號為“1”,坐標位置為(40,50)。冷鏈物流企業根據實際到達配送中心的產品數量確定配送中心需要進行配送作業的冷藏車數量。由表2知,用戶需求量為390 kg,因此,運輸和配送階段均需要2輛冷藏車輛即可完成此次配送任務。企業為了追求總成本最優,需要在賣方節點至配送中心、配送中心至各客戶節點之間按照預先規劃好的優化路徑進行配送作業。

表2 配送小區位置

基于已構建的優化模型,采用禁忌搜索算法進行求解,運用C++編程求解,最優配送路徑如圖8所示,每次迭代的目標函數變化情況如圖9所示。經計算,采用2輛冷藏車進行配送作業的最優配送方案的總路徑長度為610.1 km,總成本為6585.1元,各分項成本見表3,其中,違反各客戶節點時間窗的懲罰成本最大,占總成本的55.6%,制冷成本最少,占比1.1%。對比各次迭代下的目標函數(圖9),可以發現在迭代初期,目標函數變化較大,得到解的質量較差,但隨著迭代次數的增加,目標函數波動較小,逐漸平穩,逐漸接近最優解。

由于在配送階段采用2輛冷藏車進行配送作業導致總成本過高,尤其是違反各客戶節點時間窗的懲罰成本占總成本一半以上,因此,將導致顧客滿意度嚴重降低,客戶可能不再選用此公司進行配送,進而造成企業營業額的損失。因此,企業應調整產品配送方案,在客戶需求不變的情況下,運輸階段仍采用2輛冷藏車,當產品運至配送中心后,應充分合理地運用配送中心已有冷藏車,模型、算法及其參數設置同上。經計算,最優配送路徑如圖10所示,由圖10知,采用6輛冷藏車進行配送作業,可以使總成本達到最優。

經計算,采用6輛冷藏車進行配送作業的最優配送方案的總路徑長度為760.5 km,總成本為4319.5元,各分項成本見表3,其中,碳排放與燃油消耗成本最大,占總成本的37.1%,同樣,制冷成本最少,占比2.0%。對比各次迭代下的目標函數(圖9),可以發現在迭代初期,目標函數變化較大,但是較2輛冷藏車的收斂速度快,隨著迭代次數的增加,目標函數能夠較快地接近最優解。

由表3知,在運輸階段,由于賣方(鄉村)至配送中心道路為公路且路徑唯一,客戶需求不變,所采用冷藏車數量相同,因此從賣方節點至配送中心之間的運輸成本相同。由于冷藏車增加了4輛,使得違反客戶節點時間窗的成本較采用2輛冷藏車成本降低了77.7%,制冷成本增加了18.0%,貨損成本降低了2.2%,碳排放與燃油消耗成本增加了59.7%,總成本降低了34.4%。雖然在配送階段選擇配送的冷藏車數量增加了,但是總成本降低了,對企業和客戶而言,優勢大于劣勢。由于到達客戶節點的準時率得到提升,客戶的滿意度進一步提高,進而提升了企業競爭力和利潤。

4 結論

通過對單個配送中心的從賣家到買家全過程鏈的生鮮冷鏈物流配送問題進行研究,在考慮碳排放與燃油消耗、制冷、貨損和違反各客戶可接受配送時間窗的懲罰等基礎上,建立了配送總成本最小的生鮮冷鏈物流配送模型,運用禁忌搜索算法進行求解,尋找最優的配送路線,得到以下結論:

1) 生鮮冷鏈物流企業在配送過程中,合理增加冷藏車的數量,可以降低企業的配送總成本。

2) 隨著迭代次數的逐漸增加,禁忌搜索算法的收斂速度不斷加快。

3) 考慮了從賣家至買家全過程鏈的生鮮冷鏈物流的配送總成本,不僅可以讓企業清楚地了解配送各環節的成本明細,還能夠為生鮮冷鏈物流企業制定降本增益策略提供理論依據。