基于自適應遺傳算法的冷鏈配送干擾管理研究

舒 暉 ,曾宇清

（1.湖南現代物流職業技術學院，長沙 411000；2.湖南中煙工業有限責任公司長沙卷煙廠，長沙 410007）

0 引言

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

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

1 問題描述及模型建立

1.1 問題描述

冷鏈物流配送調度問題具體描述為：配送中心擁有K輛冷藏配送車，為該區域內的N個客戶點提供冷鏈產品的配送服務，車輛從配送中心出發給客戶配送貨物后返回配送中心。配送車輛按照初始配送方案進行配送任務時，干擾事件發生后，原始的配送方案不再最優甚至變得不可執行，需要及時生成新的配送方案。冷鏈配送階段的干擾事件主要包括以下4種情況：

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

2) 客戶時間窗提早或延遲，原方案中客戶的最早服務時間晚于新時間窗，或新方案中客戶的最早服務時間晚于原時間窗，產生干擾；

3) 配送車輛或冷藏箱發生故障無法運行，產生干擾。

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

（1）一個物流配送中心，車輛數量有限，車輛從配送中心出發并返回；

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

（3）客戶有硬時間窗約束，且每個客戶服務點的服務時間為0；

（4）每個客戶只能由1輛車進行配送服務，1輛車可以給多個客戶提供配送服務；

（5）假設貨車的運輸時間和運輸成本只和距離有關，不考慮堵車等其他因素；

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

1.2 干擾管理模型

1）變量定義

模型中的變量及參數符號定義如下：

2）模型建立

（1）客戶不滿意度

假定客戶的不滿意度只與配送到貨時間有關，當在客戶期望的時間窗內送貨時，客戶的不滿意度最低，當貨物達到時間早于或晚于客戶的期望時間窗時，會使客戶的不滿意度提高，如圖1所示。

圖1 客戶時間窗

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

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

（2）運輸成本度量

運輸成本作為配送環節最主要的成本，當客戶時間窗變動對初始配送方案造成影響時，需要對正在執行的配送方案進行調整，物流運營商的運輸成本度量公式為：

（3）新鮮度損失成本

在冷鏈運輸過程中，長時間運輸易造成貨物變質，本文考慮新鮮度貨損成本僅與配送時間有關。參考的文獻[9]的研究成果，構建冷鏈物流貨損成本計算方法，其中M為單位時間貨損成本，為冷鏈產品對時間的敏感度。

（4）路徑偏離度量

配送人員是運輸環節的執行主體，當新的配送方案會導致在途車輛的運輸路線發生變化，對配送人員的工作積極性和配送效率造成負面影響，路徑偏離量的擾動度量公式為：

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

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

3 模型求解

3.1 多目標處理

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

計算判斷矩陣A 的特征向量（權重向量）W=(0.5223，0.1998，0.1998，0.0781)T，既可將權重矩陣W將多目標問題轉為單目標優化問題，目標函數即為廣義總成本F=W*(DS，DC，DQ，DN)的最小值。

3.2 改進的遺傳算法

車輛路徑問題屬于NP-hard問題，本文設計自適應遺傳算法進行求解。為使算法快速收斂，在全局空間采用遺傳算法進行搜索，在單個車輛路徑優化時采用2-opt算子[11]進行優化，并且根據種群適應度情況來動態調整交叉變異算子的概率。

3.2.1 染色體編碼

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

3.2.2 初始化種群

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

3.2.3 局部鄰域搜索優化

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

3.2.4 選擇、交叉、變異

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

本文設計了動態自適應交叉概率和變異概率，既在算法最開始交叉概率較大，算法末期變異概率較大，可有效避免算法陷入局部最優，又加快算法收斂。動態自適應交叉概率和方差概率的改進如式(16)～式(18)所示。

方程中u為當前迭代次數，v為終止迭代次數，pc表示交叉概率，pm表示變異概率，kc，km為區間[0，1]的常數，fc為交叉個體的較大適應值，fm為個體的適應值，fa和fmax分別為當前種群的平均適應值和最大適應值。

4 仿真實驗

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

表1 配送中心及客戶信息

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

表2 初始配送方案

當配送進行到32.65時刻，客戶4、客戶6、客戶14的時間窗均發生變動，變動詳細信息如表3所示。

表3 客戶時間窗變動詳情

擾動發生時，車輛1正駛往客戶13；車輛2正駛往客戶5；車輛3還在配送中心等待，即將駛往客戶8；車輛4已到達客戶3處進行配送服務，下一站的服務對象為客戶11。此時物流配送中心還有4輛車本次未安排配送任務。運用本文的方法，得出新的配送方案，并通過與重調度方案進行對比，結果比較如表4所示。

表4 不同方案結果比較

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

表4 非標庫實際效率

5 結語

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