舒 暉 ,曾宇清

（1.湖南現(xiàn)代物流職業(yè)技術(shù)學(xué)院，長沙 411000；2.湖南中煙工業(yè)有限責(zé)任公司長沙卷煙廠，長沙 410007）

0 引言

近幾年，隨著冷鏈產(chǎn)業(yè)迅速發(fā)展，冷鏈物流配送成為各物流企業(yè)關(guān)注焦點(diǎn)。由于冷鏈產(chǎn)品的特殊性，在配送的過程中不僅要考慮到配送成本，而且還要考慮嚴(yán)格的時(shí)間送達(dá)要求和冷鏈貨損情況。趙邦磊等[1]等考慮考慮交通狀況對配送的影響，構(gòu)建了最小化總成本的冷鏈車輛路徑優(yōu)化數(shù)學(xué)模型，設(shè)計(jì)了一種新的ACO算法進(jìn)行最優(yōu)路徑求解。張佳佳等[2]針對冷鏈配送成本一直居高不下的問題，結(jié)合新能源汽車提出了邊服務(wù)客戶邊進(jìn)行充電作業(yè)的模式，建立了最小化總配送成本的模型，并通過粒子群算法求解。Li等[3]分析了車輛最大負(fù)荷的變化對成本及溫室氣體排放的影響。Ma[4]在考慮道路阻抗的條件下，引入混合時(shí)間窗約束，以總配送成本最小為目標(biāo)，建立了生鮮產(chǎn)品冷鏈配送的路徑模型，然后設(shè)計(jì)了一種混合遺傳模擬退火算法求解。冷鏈產(chǎn)品配送過程中，存在不確定擾動(dòng)因素，如客戶地址或時(shí)間窗變動(dòng)、車輛冷藏箱故障等，導(dǎo)致原配送方案不可行，需要對原運(yùn)輸方案進(jìn)行調(diào)整。楊華龍[5]針對配送過程中客戶時(shí)間窗變動(dòng)的干擾問題，基于干擾管理思想，分析干擾事件對路徑、成本和服務(wù)時(shí)間三個(gè)方面的影響，通過以最小化廣義費(fèi)用偏離為目標(biāo)，建立了干擾管理模型。寧濤等[6]針對末端物流配送過程中出現(xiàn)的配送時(shí)間窗變更、配送地址變動(dòng)等擾動(dòng)問題，提出了基于前景理論的價(jià)值函數(shù)度量策略和基于量子理論的多目標(biāo)優(yōu)化求解方法。趙亮等[7]從成本和服務(wù)時(shí)間兩個(gè)方面對干擾事件對原物流配送車輛路徑方案造成的影響進(jìn)行了干擾辨識(shí)分析構(gòu)建了干擾管理模型。曹慶奎等[8]針對客戶配送地址變動(dòng)的干擾事件，以最小化客戶不滿意度、運(yùn)輸費(fèi)用和路線偏離為目標(biāo)，建立多車場環(huán)境下多目標(biāo)干擾管理數(shù)學(xué)模型并進(jìn)行求解。

綜上所述，以上學(xué)者對冷鏈物流路徑調(diào)度及物流運(yùn)輸過程中干擾事件進(jìn)行了深入研究，但是對冷鏈產(chǎn)品的配送干擾事件研究甚少，冷鏈產(chǎn)品作為一種短生命周期產(chǎn)品，遇到的各種不確定性因素也會(huì)更加復(fù)雜。鑒于此，本文研究冷鏈產(chǎn)品配送過程中客戶時(shí)間窗變動(dòng)時(shí)的路徑優(yōu)化問題，基于干擾管理思想，綜合考慮配送成本、冷鏈貨損、路徑偏離等方面，構(gòu)建了冷鏈配送干擾管理模型，并通過改進(jìn)遺傳算法進(jìn)行模型求解，從而快速生成新配送方案。

1 問題描述及模型建立

1.1 問題描述

冷鏈物流配送調(diào)度問題具體描述為：配送中心擁有K輛冷藏配送車，為該區(qū)域內(nèi)的N個(gè)客戶點(diǎn)提供冷鏈產(chǎn)品的配送服務(wù)，車輛從配送中心出發(fā)給客戶配送貨物后返回配送中心。配送車輛按照初始配送方案進(jìn)行配送任務(wù)時(shí)，干擾事件發(fā)生后，原始的配送方案不再最優(yōu)甚至變得不可執(zhí)行，需要及時(shí)生成新的配送方案。冷鏈配送階段的干擾事件主要包括以下4種情況：

1) 客戶需求量增加，配送車輛剩余的貨物無法滿足未服務(wù)客戶點(diǎn)的需求，產(chǎn)生干擾；

2) 客戶時(shí)間窗提早或延遲，原方案中客戶的最早服務(wù)時(shí)間晚于新時(shí)間窗，或新方案中客戶的最早服務(wù)時(shí)間晚于原時(shí)間窗，產(chǎn)生干擾；

3) 配送車輛或冷藏箱發(fā)生故障無法運(yùn)行，產(chǎn)生干擾。

本文考慮上述2）的干擾情況，即客戶時(shí)間窗提早或延遲的情況，并做以下假設(shè)：

（1）一個(gè)物流配送中心，車輛數(shù)量有限，車輛從配送中心出發(fā)并返回；

（2）只配送單一貨物，且所有車輛的載重能力相同；

（3）客戶有硬時(shí)間窗約束，且每個(gè)客戶服務(wù)點(diǎn)的服務(wù)時(shí)間為0；

（4）每個(gè)客戶只能由1輛車進(jìn)行配送服務(wù)，1輛車可以給多個(gè)客戶提供配送服務(wù)；

（5）假設(shè)貨車的運(yùn)輸時(shí)間和運(yùn)輸成本只和距離有關(guān)，不考慮堵車等其他因素；

（6）物流配送初始方案已知。

1.2 干擾管理模型

1）變量定義

模型中的變量及參數(shù)符號(hào)定義如下：

2）模型建立

（1）客戶不滿意度

假定客戶的不滿意度只與配送到貨時(shí)間有關(guān)，當(dāng)在客戶期望的時(shí)間窗內(nèi)送貨時(shí)，客戶的不滿意度最低，當(dāng)貨物達(dá)到時(shí)間早于或晚于客戶的期望時(shí)間窗時(shí)，會(huì)使客戶的不滿意度提高，如圖1所示。

圖1 客戶時(shí)間窗

當(dāng)Ei≤tki≤Li代表配送車輛k在客戶期望的時(shí)間窗內(nèi)抵達(dá)，懲罰為0；當(dāng)Ei-δ≤tki≤Ei或者Li≤tki≤Li+δ表示貨物沒有在期望時(shí)間到達(dá)但在客戶勉強(qiáng)可接受范圍內(nèi)，需要一定實(shí)施一定懲罰；當(dāng)tki＜Ei-δ或者tki＞Li+δ時(shí)，表示貨物沒有在期望時(shí)間到達(dá)并且貨物有被客戶退回的風(fēng)險(xiǎn)，需要實(shí)施較為嚴(yán)厲的懲罰。懲罰函數(shù)Pi(ti)如式(1)所示：

其中：ai，bi為時(shí)間超下限和超上限的懲罰系數(shù)，maxP為最大懲罰值，客戶平均不滿意度計(jì)算如公式(2)所示。

（2）運(yùn)輸成本度量

運(yùn)輸成本作為配送環(huán)節(jié)最主要的成本，當(dāng)客戶時(shí)間窗變動(dòng)對初始配送方案造成影響時(shí)，需要對正在執(zhí)行的配送方案進(jìn)行調(diào)整，物流運(yùn)營商的運(yùn)輸成本度量公式為：

（3）新鮮度損失成本

在冷鏈運(yùn)輸過程中，長時(shí)間運(yùn)輸易造成貨物變質(zhì)，本文考慮新鮮度貨損成本僅與配送時(shí)間有關(guān)。參考的文獻(xiàn)[9]的研究成果，構(gòu)建冷鏈物流貨損成本計(jì)算方法，其中M為單位時(shí)間貨損成本，為冷鏈產(chǎn)品對時(shí)間的敏感度。

（4）路徑偏離度量

配送人員是運(yùn)輸環(huán)節(jié)的執(zhí)行主體，當(dāng)新的配送方案會(huì)導(dǎo)致在途車輛的運(yùn)輸路線發(fā)生變化，對配送人員的工作積極性和配送效率造成負(fù)面影響，路徑偏離量的擾動(dòng)度量公式為：

本文設(shè)置參數(shù)ai，bi均為懲罰系數(shù)10，maxP為1000，Cb為1，冷鏈貨損單位時(shí)間貨損成本M為2，建立干擾管理模型。

式(6)～式(9)為目標(biāo)函數(shù)，其中式(6)表示客戶不滿意度最小，式(7)表示車輛運(yùn)輸成本最小，式(8)表示新鮮度損失成本最小，式(9)表示路徑偏離度量最?。皇?10)表示車輛載貨量不能超過該車的限載量；式(11)表示在途車輛不能超過配送中心車輛數(shù)量；式(12)表示車輛必須從虛擬配送中心（所在客戶點(diǎn)）出發(fā)；式(13)表示車輛在配送服務(wù)完成后返回配送中心；式(14)表示一個(gè)客戶僅僅可以被一輛車服務(wù)一次；式(15)表示客戶時(shí)間窗約束。

3 模型求解

3.1 多目標(biāo)處理

針對上述模型的多目標(biāo)優(yōu)化問題，本文使用層次分析法[10]，將多目標(biāo)問題化簡為單目標(biāo)問題求解。用數(shù)字1、3、5、7、9表示要素i、j之間的重要程度，數(shù)值越大表示要素i比j越重要，通過兩兩比較，建立目標(biāo)函數(shù)的判斷矩陣A。

計(jì)算判斷矩陣A 的特征向量（權(quán)重向量）W=(0.5223，0.1998，0.1998，0.0781)T，既可將權(quán)重矩陣W將多目標(biāo)問題轉(zhuǎn)為單目標(biāo)優(yōu)化問題，目標(biāo)函數(shù)即為廣義總成本F=W*(DS，DC，DQ，DN)的最小值。

3.2 改進(jìn)的遺傳算法

車輛路徑問題屬于NP-hard問題，本文設(shè)計(jì)自適應(yīng)遺傳算法進(jìn)行求解。為使算法快速收斂，在全局空間采用遺傳算法進(jìn)行搜索，在單個(gè)車輛路徑優(yōu)化時(shí)采用2-opt算子[11]進(jìn)行優(yōu)化，并且根據(jù)種群適應(yīng)度情況來動(dòng)態(tài)調(diào)整交叉變異算子的概率。

3.2.1 染色體編碼

本文采用文獻(xiàn)[12]的編碼方式進(jìn)行染色體編碼，即客戶點(diǎn)和配送車輛的全排列編碼為一條染色體。例如：1個(gè)停車場，共有3輛車。顧客的編號(hào)為1～9，車輛編號(hào)則為10～12。則解染色體10-1-2-3-11-4-5-6-12-7-8-9表示：10號(hào)車輛的配送線路為0-1-2-3-0，11號(hào)車輛的配送線路為0-4-5-6-0，12號(hào)車輛的配送線路為0-7-8-9-0，其中0為配送中心。

3.2.2 初始化種群

干擾事件下新的配送方案應(yīng)對原配送方案造成較小的擾動(dòng)，本文初始種群中4/5的個(gè)體隨機(jī)產(chǎn)生，1/5的群體由原配送方案的中個(gè)體組成。在生成種群的過程中依次判斷每條染色體是否滿足車輛裝載量、客戶時(shí)間窗等方面的約束。

3.2.3 局部鄰域搜索優(yōu)化

為加快算法收斂速度，在算法中引入了局部鄰域搜索，采用2-opt算子[11]來實(shí)現(xiàn)。第一步：將一輛車所經(jīng)過服務(wù)配送點(diǎn)的路徑作為染色體的一個(gè)基因段，將基因段作為初始解。第二步：然后通過2-opt算法對單個(gè)車輛的配送路徑進(jìn)行優(yōu)化，即車輛所服務(wù)的顧客點(diǎn)不變，只改變顧客服務(wù)順序。第三步：選取個(gè)體適應(yīng)度好于父代，則用子代代替父代，返回第一步；否則停止。該局部搜索并不會(huì)改變單個(gè)車輛服務(wù)的客戶，只是改變車輛的客戶服務(wù)順序，無需進(jìn)行貨物裝載量約束判斷。

3.2.4 選擇、交叉、變異

選擇操作算子采用輪盤賭的選擇方式，交叉操作采用OX（order crossover）方式[13]，變異操作采用基因段逆序[13]的方式。

本文設(shè)計(jì)了動(dòng)態(tài)自適應(yīng)交叉概率和變異概率，既在算法最開始交叉概率較大，算法末期變異概率較大，可有效避免算法陷入局部最優(yōu)，又加快算法收斂。動(dòng)態(tài)自適應(yīng)交叉概率和方差概率的改進(jìn)如式(16)～式(18)所示。

方程中u為當(dāng)前迭代次數(shù)，v為終止迭代次數(shù)，pc表示交叉概率，pm表示變異概率，kc，km為區(qū)間[0，1]的常數(shù)，fc為交叉?zhèn)€體的較大適應(yīng)值，fm為個(gè)體的適應(yīng)值，fa和fmax分別為當(dāng)前種群的平均適應(yīng)值和最大適應(yīng)值。

4 仿真實(shí)驗(yàn)

本文選取文獻(xiàn)[14]的數(shù)據(jù)進(jìn)行仿真測試，一個(gè)配送中心，8輛汽車，每輛車載重為5噸，車速為1單位，單位運(yùn)輸成本為1，增派車輛的成本為140，客戶的信息如表1所示，其中編號(hào)0表示配送中心，編號(hào)1～15表示客戶。實(shí)驗(yàn)中遺傳算法種群規(guī)模為50，迭代次數(shù)1000，設(shè)置交叉和變異概率kc=0.9和km=0.1，隨機(jī)運(yùn)行10次，取其中最優(yōu)值。

表1 配送中心及客戶信息

采用本文的改進(jìn)遺傳算法得到初始方案如表2所示，初始配送計(jì)算路徑長度為522.15，優(yōu)于文獻(xiàn)[14]的531.41。證明了算法的快速收斂能力和尋優(yōu)能力。

表2 初始配送方案

當(dāng)配送進(jìn)行到32.65時(shí)刻，客戶4、客戶6、客戶14的時(shí)間窗均發(fā)生變動(dòng)，變動(dòng)詳細(xì)信息如表3所示。

表3 客戶時(shí)間窗變動(dòng)詳情

擾動(dòng)發(fā)生時(shí)，車輛1正駛往客戶13；車輛2正駛往客戶5；車輛3還在配送中心等待，即將駛往客戶8；車輛4已到達(dá)客戶3處進(jìn)行配送服務(wù)，下一站的服務(wù)對象為客戶11。此時(shí)物流配送中心還有4輛車本次未安排配送任務(wù)。運(yùn)用本文的方法，得出新的配送方案，并通過與重調(diào)度方案進(jìn)行對比，結(jié)果比較如表4所示。

表4 不同方案結(jié)果比較

從表4可以看出，干擾事件發(fā)生后，采用本文方法的得出的配送方案雖然在路徑長度略高于重調(diào)度方法，但路徑偏離量、廣義總成本和客戶滿意度均低于重調(diào)度方案，更有利于客戶和駕駛員的體驗(yàn)，綜合比較本文干擾管理方法生成的配送方案綜合評價(jià)更優(yōu)。

表4 非標(biāo)庫實(shí)際效率

5 結(jié)語

本文結(jié)合干擾管理思想對冷鏈物流配送中的干擾事件進(jìn)行研究，在干擾事件發(fā)生后迅速生成新的配送方案。本文根據(jù)冷鏈物流產(chǎn)品易腐的特殊性，新增了新鮮度下降懲罰成本，建立以客戶滿意度、車輛配送成本、新鮮度損失成本、路徑偏移最小化為目標(biāo)的冷鏈物流干擾調(diào)度模型，并改進(jìn)遺傳算法進(jìn)行模型求解，通過仿真實(shí)驗(yàn)表明，本文提出的模型更符合冷鏈物流配送實(shí)際并且改進(jìn)的遺傳算法具有更好的收斂能力。下一步將研究多配送中心、多車型、多干擾事件的冷鏈物流配送干擾管理問題，并結(jié)合物聯(lián)網(wǎng)技術(shù)實(shí)時(shí)了解干擾事件相關(guān)信息，動(dòng)態(tài)監(jiān)測配送過程中溫度的變化及產(chǎn)品的質(zhì)量情況，更好進(jìn)行冷鏈配送的干擾管理優(yōu)化。