劉艷秋,楊 沙

(沈陽工業(yè)大學(xué) 理學(xué)院,沈陽 110870)

冷鏈物流配送路徑優(yōu)化問題屬于經(jīng)典的車輛路徑問題(vehicle routing problem,VRP),是多項式復(fù)雜程度的非確定性問題.國內(nèi)外學(xué)者對該問題展開了由淺入深的研究,已取得了諸多成果.如王淑云和孫虹[1]對冷鏈物流配送問題的研究做了綜述,并對問題的發(fā)展前景展開介紹.Amorim等[2]考慮到農(nóng)產(chǎn)品的新鮮程度,以包含貨損成本的最小配送成本為目標(biāo)來分析問題.繆小紅等[3]考慮第三方冷鏈物流配送模式,構(gòu)建了冷鏈物流成本基本優(yōu)化模型,利用改進(jìn)的遺傳算法得到了最優(yōu)路徑.范厚明等[4]考慮到運(yùn)輸?shù)臅r效性,提出基于時間窗的懲罰成本,構(gòu)建半開放式多中心冷鏈物流聯(lián)合路徑優(yōu)化模型,設(shè)計蟻群算法進(jìn)行了求解.劉虹等[5]在冷鏈車輛路徑優(yōu)化問題中,引入?yún)拹盒袨楹瘮?shù),建立了包含厭惡行為和成本的雙目標(biāo)優(yōu)化模型,并通過仿真實驗驗證了模型構(gòu)建的正確性.丁艷[6]考慮到多溫共配冷鏈物流配送問題中的干擾因素,提出一種新的路徑優(yōu)化方法,利用量子計算與蟻群算法對模型求解.李軍濤[7]、李倩等[8]建立了帶有模糊時間窗的多目標(biāo)優(yōu)化模型.Leng等[9]以最小化總成本和等待時間為目標(biāo),提出了冷鏈的選址-路徑優(yōu)化模型,采取了多目標(biāo)優(yōu)化算法驗證了模型的優(yōu)越性.

隨著綠色物流發(fā)展理念的提出,低碳冷鏈物流的話題受到了學(xué)者們的關(guān)注.Bozorgi等[10]在建立冷鏈物流配送最小成本模型時,將碳排放成本量化納入到目標(biāo)函數(shù)中,并使用精確算法求解了模型.Bortolini等[11]考慮運(yùn)營成本、碳足跡和交貨時間的三目標(biāo)生鮮車輛路徑優(yōu)化模型,通過開發(fā)的優(yōu)化系統(tǒng)對實例求解,驗證了模型的可行性.方文婷等[12]設(shè)計混合的蟻群算法求解低碳冷鏈物流路徑優(yōu)化模型,達(dá)到了節(jié)能減排的目的.沈麗等[13]進(jìn)一步探討了生鮮產(chǎn)品的貨損和碳排放來源.鮑春玲等[14]研究多中心冷鏈物流聯(lián)合配送模式,考慮時間窗和碳排放成本在內(nèi)的總成本最小優(yōu)化模型,并通過對比方法驗證了聯(lián)合模式的優(yōu)越性.但上述研究均未考慮到配送中客戶信息的動態(tài)變化.2018年劉波[15]考慮冷鏈物流配送中新增客戶和時間窗變更兩種動態(tài)事件,設(shè)計定時分批優(yōu)化處理策略,提出改進(jìn)的人工魚群算法對模型進(jìn)行求解.該處理策略可以有效控制計算量,但靈活性不強(qiáng),處理動態(tài)需求時未顧及到車輛利用率,有一定的局限性.2020年楊建[16]研究了共同配送模式下的冷鏈物流動態(tài)路徑優(yōu)化問題,引入時間軸概念,采取兩階段優(yōu)化策略,建立靜態(tài)和動態(tài)兩個模型,提出改進(jìn)遺傳算法,通過實例求解驗證了策略的可行性.該優(yōu)化策略可以提高車輛利用率,但未考慮到客戶的緊急需求,快速響應(yīng)能力弱.

綜上所述,以往由于受到現(xiàn)實技術(shù)條件的限制,無法實時獲取動態(tài)信息,相關(guān)文獻(xiàn)大多研究靜態(tài)車輛路徑問題,往往不能較好應(yīng)對配送中的突發(fā)隨機(jī)狀況,缺乏對配送的實時響應(yīng)性和靈活性,易造成資源浪費(fèi)和服務(wù)延誤,導(dǎo)致配送成本高而顧客滿意度普遍低下.基于此,將配送中客戶需求的動態(tài)特點納入考慮范疇,充分體現(xiàn)配送的現(xiàn)實性,以包含車輛啟動成本、油耗成本、貨損成本、制冷成本、碳排放成本和懲罰成本在內(nèi)的總成本最小為目標(biāo),構(gòu)建帶有軟時間窗的冷鏈物流動態(tài)路徑優(yōu)化模型,設(shè)計動態(tài)信息處理策略,提出改進(jìn)粒子群算法進(jìn)行求解,得出最優(yōu)的配送方案.

1 問題描述與模型構(gòu)建

1.1 問題描述

在一個冷鏈物流配送網(wǎng)絡(luò)G=(N′,E)中,N′=O∪N表示所有節(jié)點集合,E={(i,j)|(i,j)∈V2,i≠j}表示連接各節(jié)點的邊集.O={0}表示配送中心,N=Ns∪Nd={1,2,…,m+n}表示客戶點集合,Ns={1,2,…,m}和Nd={m+1,m+2,…,m+n}分別為靜態(tài)客戶點集和動態(tài)客戶點集.配送中心O一天中的工作時間窗為[E0,L0],可用冷藏車集合為K={1,2,…,u},車輛的最大載重為Q,行駛速度為常量v,客戶i的需求量為qi,需服務(wù)時長為si.現(xiàn)根據(jù)m個靜態(tài)客戶訂單信息,考慮車輛最大載重和時間窗等約束,安排冷藏車從中心O滿載發(fā)車進(jìn)行配送,服務(wù)完畢后需返回中心.在配送開始后會出現(xiàn)動態(tài)需求(靜態(tài)客戶訂單的取消、需求量的增減和新增客戶需求),那么如何實時處理動態(tài)需求信息,及時更新車輛調(diào)度方案,以達(dá)到在整個配送網(wǎng)絡(luò)中冷鏈物流配送總成本最小.特作出以下假設(shè)：① 待服務(wù)客戶有且僅能被1輛冷藏車服務(wù)1次；② 每輛冷藏車配送總量和單一客戶需求量均不超過車輛的最大載重；③ 所有車輛為同一型號,冷藏性能相同；④ 不考慮交通堵塞或道路維修等交通路網(wǎng)造成的影響；⑤ 考慮帶有軟時間窗的配送問題.

1.2符號及決策變量

xijk為0-1變量,xijk=1表示由車輛k完成客戶i到j(luò)的配送任務(wù),否則xijk=0；yik為0-1變量,yik=1表示客戶i由車輛k提供服務(wù),否則yik=0.

1.3 模型建立

以冷鏈產(chǎn)品配送總成本Z最小為目標(biāo)函數(shù),配送總成本Z是由車輛啟動成本C1、油耗成本C2、貨損成本C3、制冷成本C4、碳排放成本C5以及違反時間窗支付的懲罰成本C6六部分組成.其中貨損成本C3包括行駛階段產(chǎn)生的貨損成本和裝卸階段產(chǎn)生的貨損成本,為了分析貨損成本,引入常用的冷鏈產(chǎn)品變質(zhì)速率隨時間呈指數(shù)衰減的函數(shù)θ(t)=e-λt,則貨損部分表示為1-θ(t)=1-e-λt,其中λ為冷鏈產(chǎn)品的變質(zhì)速率.模型建立如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

式(2)確保每輛車的配送量不超過其最大容量；式(3)(4)表示每個客戶有且僅有1輛車為其服務(wù)；式(5)表示所有待服務(wù)的客戶均能被服務(wù)；式(6)保證在每個節(jié)點處車輛進(jìn)出流量平衡；式(7)表示從配送中心出發(fā)的車輛均滿載發(fā)車,即車輛k服務(wù)第1個客戶點j時,負(fù)載量為Q；式(8)表示對于執(zhí)行配送任務(wù)的車輛,要求從配送中心出發(fā)最終還要返回到該中心；式(9)規(guī)定車輛到達(dá)每個客戶的時間點；式(10)表示每輛配送車必須在該日工作結(jié)束前返回到中心；式(11)為標(biāo)準(zhǔn)支路消除約束；式(12)限制動態(tài)客戶出現(xiàn)的時間在規(guī)定時間段內(nèi)；式(13)為0-1約束；式(14)為函數(shù)f(q)的具體表達(dá)式.

1.4 動態(tài)處理策略

針對配送途中出現(xiàn)新增客戶需求信息,提出以下兩種處理策略.

圖1 連續(xù)時間段下的動態(tài)分批優(yōu)化策略Fig.1 Dynamic batching optimization strategy under continuous time

(15)

2) 緊急訂單即時重優(yōu)化策略.為快速響應(yīng)客戶的緊急需求,減少客戶服務(wù)延誤的概率,立即將動態(tài)請求時刻td作為批處理時刻u(t+1).當(dāng)td>u(t)時,以下兩種情形的動態(tài)事件稱為緊急訂單.

對于取消訂單的原有客戶采取配送車輛直接略過的方法；對于需求量發(fā)生改變的原有客戶,將其看成先取消又新增需求的新客戶,按照新增客戶的策略求解.與以往策略不同的是,動態(tài)分批優(yōu)化策略在批處理時刻的選取上具有動態(tài)性和靈活性,可避免定時分批處理策略下,存在車輛利用率低的缺點.緊急訂單即時重優(yōu)化策略考慮到了客戶訂單的緊急性,可有效應(yīng)對客戶緊急需求,減少服務(wù)延誤的概率.

如圖2所示,配送中心在某個工作日的配送流程可分為兩個階段,即先靜態(tài)規(guī)劃后動態(tài)調(diào)整.

圖2 兩階段求解流程圖Fig.2 Two-phase solution flow chart

2 改進(jìn)粒子群算法

2.1 算法設(shè)計

算法選取更適合在動態(tài)、多目標(biāo)優(yōu)化環(huán)境中尋優(yōu)的粒子群算法(particle swarm optimization,PSO).與其他智能算法相比,粒子可以動態(tài)地跟蹤個體極值和全局極值來調(diào)整其飛翔速度和位置,不斷進(jìn)化到全局最優(yōu)解,具有收斂速度快、易實現(xiàn)、全局尋優(yōu)能力強(qiáng)等優(yōu)勢[17-18].但PSO存在早熟收斂現(xiàn)象,易陷入局部最優(yōu).基于此,一方面,為了提高算法收斂的全局性,將relocate局部搜索算子融入PSO,增加粒子的多樣性,擴(kuò)大解的搜索空間,具體過程為：在每次更新粒子后,選取當(dāng)前解中違反時間窗最大的客戶,將其移除并重新插入到另一路徑中,產(chǎn)生更優(yōu)秀的粒子.另一方面,引入慣性權(quán)重衰減率λ來提高算法的收斂速率,并限制粒子運(yùn)動速度在[-vmax,vmax]之間,對范圍之外的速度進(jìn)行越界處理,即小于-vmax的速度賦值為-vmax,大于vmax的速度賦值為vmax,以避免粒子速度過快而錯過最優(yōu)解.

2.2 算法求解步驟

步驟1 種群初始化,隨機(jī)生成種群規(guī)模為sizepop的粒子群.

步驟2 以目標(biāo)函數(shù)Z作為適應(yīng)度函數(shù),計算每個粒子的適應(yīng)度值fitness.

步驟3 根據(jù)式(16)(17)確定每個粒子的個體極值Pi和當(dāng)前群體的全局極值Pg.

(16)

Pg=min{P1,P2,…,Psizepop}.

(17)

步驟4 判斷是否達(dá)到最大迭代次數(shù)MAXGEN.若達(dá)到,則輸出結(jié)果；否則轉(zhuǎn)至步驟5.

步驟5 根據(jù)迭代公式(18)～(20)更新粒子的位置和速度,進(jìn)行越界處理.

ω(k)=ω0×λk-1,

(18)

Vij(k+1)=ω(k)Vij(k)+c1α(Pij(k)-Xij(k))+c1β(Pgj(k)-Xij(k)),

(19)

Xij(k+1)=Xij(k)+Vij(k+1).

(20)

其中:Vij(k)和Xij(k)分別表示在第k代時第i個粒子在第j維上的速度和位置;Pij(k)表示在第k代時第i個粒子經(jīng)歷過的最好位置;Pgj(k)表示在第k代時整個粒子群所有粒子經(jīng)歷過的最好位置;w(k)為第k代時的慣性權(quán)重;w0為初始慣性權(quán)重;λ為慣性權(quán)重衰減率;c1、c2為學(xué)習(xí)因子;α、β為[0,1]之間的隨機(jī)數(shù).

步驟6 對更新后的粒子進(jìn)行relocate局部搜索操作,直至達(dá)到預(yù)設(shè)的搜索次數(shù),轉(zhuǎn)至步驟2.

3 算例測試與結(jié)果分析

3.1 算例設(shè)計

表1 動態(tài)客戶需求信息Tab.1 Dynamic customer requirements information

3.2 算例求解

算例采取改進(jìn)的粒子群算法求解,設(shè)定各參數(shù)為：種群大小sizepop=200,最大迭代次數(shù)Max Iteration=500,慣性權(quán)重ω=1,慣性權(quán)重衰減率λ=0.99,學(xué)習(xí)因子c1=1.5、c2=2,采用Matlab R2015b軟件進(jìn)行編程,在處理器為Intel(R) Core(TM) i3-7100U CPU @ 3.90 GHz的Windows 10操作系統(tǒng)下進(jìn)行測試,經(jīng)過多次運(yùn)行后取最優(yōu)的解.

1) 靜態(tài)規(guī)劃結(jié)果.靜態(tài)規(guī)劃階段的最優(yōu)配送方案為：0→4→3→18→10→8→15→0,0→19→6→14→11→0,0→2→16→12→5→20→0,0→13→1→7→17→9→0.

2) 動態(tài)調(diào)整后結(jié)果.動態(tài)批處理時刻集為{6,6.45,6.5,6.9}.經(jīng)測試,如圖3所示,得出整體最優(yōu)配送方案.車輛1配送順序：0→4→3→10→8→18→26→0.車輛2配送順序：0→19→6→28→21→15→25→0.車輛3配送順序：0→2→16→9→5→20→0.車輛4配送順序：0→13→1→7→17→29→11→0.車輛5配送順序：0→27→14→24→22→23→0.與靜態(tài)規(guī)劃結(jié)果相比,動態(tài)調(diào)整后路線的車輛平均利用率提高了7.28%,有效節(jié)約了資源,為企業(yè)創(chuàng)造了潛在效益.

圖3 考慮動態(tài)處理策略的最優(yōu)配送順序 圖4 不考慮動態(tài)處理策略的最優(yōu)配送順序Fig. 3 Optimal distribution order considering dynamic processing strategy Fig. 4 Optimal distribution order without considering dynamic processing strategy

3.3 實驗對比與結(jié)果分析

3.3.1 策略對比分析 對比實驗為不考慮動態(tài)處理策略時的測試,即靜態(tài)規(guī)劃時,冷藏車輛非滿載從中心發(fā)車執(zhí)行配送.在配送中,對于取消訂單的靜態(tài)客戶,直接跳過；對于需求量減少的靜態(tài)客戶,將多余貨物量滯留車內(nèi)帶回中心；對于需求量增加的靜態(tài)客戶和新增客戶,另派車對其服務(wù).訂單處理間隔為T=0.5 h.如圖4所示,測試結(jié)果為：0→2→16→9→12→5→0,0→11→13→1→7→17→0,0→4→3→18→6→14→0,0→19→10→8→20→15→0,0→28→23→0,0→20→21→24→0,0→22→29→27→0,0→25→26→0.兩組實驗的對比情況如表2所示.

表2 兩組實驗對比結(jié)果Tab.2 Comparison results of two groups of experiments

由表2可知,從各項成本和配送總成本上分析,考慮動態(tài)處理策略下的配送總成本減少了630.21元,約26.68%.除貨損成本外,其余成本均明顯優(yōu)于對比實驗的結(jié)果.貨損成本之所以增加1.85%,是由于冷藏車輛滿載發(fā)車,需求量剩余的部分在運(yùn)輸中產(chǎn)生了貨損造成的.但這并不影響客戶的消費(fèi)體驗,這是因為完成整個配送任務(wù)需要的時長減少了0.50 h,車輛行駛總距離大幅減少了103.92 km,冷鏈產(chǎn)品的損壞量會變少,新鮮度仍會保持較高.此外,較少的懲罰成本有利于企業(yè)形成良好的口碑.

從車輛行駛總距離上分析,行駛總距離的大幅度減少,使得油耗成本和碳排放成本分別下降22.50%和22.54%,這不僅降低了配送成本,還有利于提升企業(yè)的社會效益.從平均車輛有效利用率上分析,動態(tài)處理策略下的利用率提高35.77%,平均可達(dá)到95%以上,有利于企業(yè)資源節(jié)約化.因此,提出的動態(tài)處理策略能較好地解決動態(tài)需求下的冷鏈產(chǎn)品配送問題,可以達(dá)到有效降低配送總成本和提高車輛利用率的目的,進(jìn)而驗證了動態(tài)處理策略的優(yōu)越性.

3.3.2 算法對比分析 為了進(jìn)一步驗證算法的有效性,分別采取基本粒子群算法(PSO)、遺傳算法(genetic algorithm,GA)、改進(jìn)遺傳算法對算例進(jìn)行測試,其中基本PSO與改進(jìn)PSO不同之處在于前者缺少relocate局部搜索,而改進(jìn)GA是在GA的基礎(chǔ)上添加relocate局部搜索.經(jīng)多次測試得出實驗結(jié)果如表3所示,各算法求解結(jié)果對比情況如表4所示.由表3和表4的實驗結(jié)果可知,對于考慮動態(tài)需求的冷鏈物流路徑優(yōu)化問題,改進(jìn)PSO求解的結(jié)果均優(yōu)于其他3種算法.相較于基本PSO,改進(jìn)PSO得到的配送總成本約減少19%,配送耗時約減少4.04%,平均車輛利用率約提高20%,其他各項成本均有明顯降低,尤其是懲罰成本從之前的35.30元降為0元,這表明改進(jìn)PSO添加的relocate局部搜索算子保證了粒子種群的多樣性,增強(qiáng)了算法的局部搜索能力,提高了解的精度和質(zhì)量,同樣這個結(jié)論也可以從GA和改進(jìn)GA的結(jié)果對比中看出.而改進(jìn)GA雖然也添加了局部搜索算子來提高搜索能力,但求解的結(jié)果與基本PSO相差不大.與改進(jìn)GA相比,改進(jìn)PSO得到的配送總成本減少20.78%,貨損成本、碳排放成本分別減少15.78%、26.37%,這不僅保證了產(chǎn)品的新鮮度,同時也減少了對環(huán)境的污染.通過對比基本PSO與GA、改進(jìn)GA與改進(jìn)PSO兩組實驗結(jié)果,在各項成本方面,PSO、改進(jìn)PSO得到的結(jié)果優(yōu)于GA、改進(jìn)GA；從懲罰成本上看,這表明在考慮動態(tài)需求下進(jìn)行產(chǎn)品配送,采取粒子群算法求解能較好安排客戶配送順序,最大程度滿足客戶時間窗,提高顧客消費(fèi)體驗.因此,對于尋優(yōu)環(huán)境動態(tài)變化的優(yōu)化問題,采取PSO求解比GA更具有優(yōu)勢,這是因為粒子具有動態(tài)跟蹤極值、存儲歷史記憶等特點,更容易探測到外部環(huán)境的變化,以跳出先前環(huán)境來適應(yīng)新的環(huán)境狀況,進(jìn)而更容易搜索到問題的全局最優(yōu)解.

表3 各算法求解的最優(yōu)配送方案Tab.3 The optimal distribution scheme solved by each algorithm

表4 各算法運(yùn)行結(jié)果對比Tab.4 The running results of each algorithm

算例的動態(tài)客戶批處理時刻集為{6.00,6.45,6.50,6.90},共分為4個動態(tài)規(guī)劃時期,以第1個動態(tài)規(guī)劃時期6時的客戶信息為例,分別采用基本PSO、GA、改進(jìn)GA、改進(jìn)PSO進(jìn)行多次測試,將取得最優(yōu)值時算法收斂情況進(jìn)行對比,如圖5所示.可以看出,采取GA、改進(jìn)GA求解的結(jié)果均劣于改進(jìn)PSO,且整體上達(dá)到收斂的速度較慢,GA在迭代到330次左右出現(xiàn)停滯問題,陷入局部最優(yōu),而改進(jìn)GA后期接近最優(yōu)解時搜索速度明顯降低,做出大量的冗余迭代難以搜索到最優(yōu)解.基本PSO在迭代前期呈現(xiàn)出較快的收斂速度,在迭代到283代時收斂速度趨于平緩,但在后期由于粒子的多樣性減少致使全局尋優(yōu)能力弱,陷入局部最優(yōu)難以跳出,而改進(jìn)PSO在迭代過程中表現(xiàn)出較強(qiáng)的全局尋優(yōu)能力,整體上更快搜索到了全局最優(yōu)解,在迭代到160代左右趨于收斂,這表明relocate局部搜索算子的引入有效避免了基本PSO易陷入局部最優(yōu)的現(xiàn)象,較好地平衡了全局和局部搜索能力,使其求解性能有了很大的提高.因此,采取改進(jìn)PSO求解冷鏈物流動態(tài)路徑優(yōu)化模型更具有有效性.

圖5 不同算法收斂對比Fig.5 Convergence comparison graph of different algorithms

4 結(jié)論

本文研究了動態(tài)需求下的冷鏈物流車輛路徑問題,建立了冷鏈物流動態(tài)路徑優(yōu)化模型,主要提出了兩種動態(tài)處理策略,并利用改進(jìn)的粒子群算法對算例進(jìn)行了求解.結(jié)果表明：與不考慮動態(tài)處理策略的情況相比,本文提出的兩種動態(tài)處理策略實時處理了動態(tài)客戶需求,快速響應(yīng)了客戶緊急需求,更加合理地安排了靜態(tài)和動態(tài)客戶的服務(wù)順序,達(dá)到了有效降低配送成本和提高車輛利用率的目的,這不僅可以給客戶帶來最佳的消費(fèi)體驗,更有利于企業(yè)的長遠(yuǎn)發(fā)展.此外,通過與基本粒子群算法等進(jìn)行對比,進(jìn)一步驗證了改進(jìn)粒子群算法在求解精度和收斂速度上的優(yōu)勢,能夠較好地求解動態(tài)路徑優(yōu)化問題.今后,將進(jìn)一步考慮多中心、多車型聯(lián)合配送模式下的動態(tài)需求冷鏈路徑優(yōu)化問題,使問題更接近實際配送工作.