考慮多類型產品新鮮度的生鮮配送路徑優化

酒艷妮，胡大偉 （長安大學運輸工程學院，陜西 西安 710064）

0 引 言

隨著社會經濟水平的不斷提高，消費者對于水產品、果蔬、鮮肉產品等生鮮產品的需求與日俱增。新冠疫情的爆發改變了人們的消費方式和飲食方式，加快推動了消費者對健康食材產品的需求，消費場景化趨勢更加明顯。消費者線下到店購買頻率降低，轉到線上購買，生鮮電商在此期間蓬勃發展。由于生鮮食材的易腐性，消費者對其配送過程有著較高的要求。同時消費者的生活習慣等的差異，使其對偏好種類等產生不同，生鮮食材企業如何滿足客戶對不同種類生鮮的需求，優化生鮮食材配送網絡，提高服務質量和配送效率，同時降低成本，成為亟待解決的問題。

在生鮮配送方面，馮杰等人在純電動冷藏車生鮮配送路徑優化中考慮電動車到充電站充電及客戶軟時間窗約束，并設計蟻群算法進行求解；婁晶等考慮現實生活中城市道路交通的時變性和生鮮配送的時效性，以最小使用車輛數和最少行程時間為優化目標，構建了時變路網下帶硬時間窗的生鮮物流配送路徑選擇模型；方文婷等人將綠色發展理念考慮在冷鏈配送路徑優化中，建立以固定成本、綠色成本、制冷成本、貨損成本、時間窗懲罰成本最小為目標函數的冷鏈配送數學模型采用混合蟻群算法求解；王勇等人以運輸成本、溫控成本、違反時間窗的懲罰成本最小化及生鮮價值損失最小為目標，考慮商品溫度控制和時間窗約束建立了生鮮配送優化模型，用混合遺傳算法進行求解；趙志學、李夏苗基于時變路網的特點，同時考慮電動車電池電量約束、車輛容量約束、生鮮新鮮度約束等構建優化模型，并設計自適應改進蟻群算法求解；余建軍等研究生鮮外賣配送中最小化配送成本和最大化顧客滿意度，通過自適應算法改進遺傳算法求解優化模型。曹文彬等人考慮了新鮮度懲罰，提出變領域搜索改進遺傳算法進行求解；目前國內對生鮮配送路徑優化領域的研究豐富，多從生鮮配送過程中涉及到的成本，特別是生鮮新鮮度和配送溫度控制方面及生鮮配送的時效性進行研究，且多為單品種生鮮配送網絡。

本文針對客戶對多類型生鮮產品的需求，綜合考慮不同類型生鮮產品在配送過程中的新鮮度變化，考慮不同的保鮮制冷方式，差異化新鮮度敏感系數，引入生鮮保鮮努力系數，產生相應的制冷成本和貨損成本，同時結合客戶對生鮮配送的時效性要求，考慮配送時間窗約束，建立生鮮配送數學模型，并設計混合遺傳—粒子群算法進行求解。

1 問題描述與模型構建

1.1 問題描述

考慮到實際中客戶對不同生鮮產品的需求偏好，生鮮配送過程不同產品保鮮方式不同新鮮度衰減不同，本文研究的考慮多類型產品新鮮度的生鮮配送路徑問題描述如下：

在一定城市區域內，客戶通過生鮮電商下單，由生鮮電商在該區域內的配送中心或前置倉為其提供配送服務。每個客戶的地理位置已知，對于不同種類的生鮮產品需求已知，對配送服務的時間窗已知。生鮮產品包括常溫、冷藏、冷凍三類，對于不同的產品在配送過程中采用不同的保冷方式。配送中心利用自有車輛，利用泡沫箱、冰袋及小型冷凍箱等對常溫、冷藏和冷凍生鮮產品進行配送，受服務時間窗和車輛容量限制等的影響，合理規劃配送路線，在固定成本、運輸成本、貨損成本、制冷成本、違反時間窗的懲罰成本最小的情況下，完成客戶配送服務。

1.2 基本假設

考慮到實際問題的復雜性，本文做如下假設：

（1） 客戶點位置、時間窗及與配送中心的距離已知；

（2） 客戶對不同種類的生鮮需求已知；

（3） 配送中心的車輛為同質車輛；

（4） 車輛勻速行駛；

（5） 車輛從配送中心出發并返回原配送中心。

1.3 參數說明

表1 參數和定量定義

1.4 模型建立

1.4.1 成本分析

①車輛的固定使用成本

車輛的固定使用成本主要是指車輛被啟動所產生的一系列的固定成本，記為Z。

③制冷成本

本文研究的生鮮配送路徑優化中，生鮮產品包括三種類別：常溫、冷藏、冷凍。對于生鮮配送最后一公里問題，考慮到城市道路限制、客戶需求量小且分散的特點，采用電動車輛為客戶進行配送。對于常溫產品，在配送過程中不采取制冷措施；對于冷藏產品，一般使用冰袋、冰包等；對于冷凍產品，采用小型保冷箱等制冷措施，從而保證生鮮食材的新鮮度。且對于電動車載保冷箱或冰袋來說，配送過程中不存在開車門等影響溫度而產生額外的制冷成本，因此，本文考慮不同類別的生鮮產品和需求設置不同的制冷成本。

④貨損成本

由于生鮮食材易腐的特性，在配送過程中其質量會隨著時間和溫度的變化逐漸下降，造成貨物毀損，造成一定的經濟損失。對于不同種類的生鮮產品，其新鮮度衰減程度有所不同，隨著時間和溫度變化，冷藏冷凍產品衰減更明顯；本文差異化生鮮產品的敏感度系數。同時考慮配送過程中不同的制冷方式對新鮮度的影響，引入生鮮產品保鮮努力系數。根據文獻[8]構建的受時間和產品保鮮成本投入雙重因素影響的新鮮度函數，構建生鮮食材種類p 到達客戶i 時的新鮮度函數為：

⑤時間懲罰成本

由于生鮮配送的現實情況比較復雜，車輛的行駛速度、道路復雜性等不確定因素，都有可能使貨物不能在約定好的時間段內送到，本文采用配送服務軟時間窗進行懲罰成本分析，即配送車輛如若超出客戶指定服務時間需要承擔一定的懲罰成本。

1.4.2 目標函數

綜合以上成本分析，總目標函數為車輛的固定成本、運輸成本、制冷成本、貨損成本及時間懲罰成本之和最小。

式（9） 表示每個客戶都被訪問一次；式（10）、式（11） 表示對于每個客戶點，只允許有一輛車到達，一輛車離開；式（12） 表示電動車輛必須從生鮮配送中心出發，最終返回生鮮配送中心；式（13） 表示電動車輛容量約束，保證每輛車配送的客戶點的各類生鮮需求量總和不超過電動車的最大容量；式（14） 表示電動車輛配送時間的連續性；式（15） 表示電動車輛從節點i 到節點j 的時間等于節點i 到節點j 的距離除以平均車速；式（16） 表示車輛的服務時間必須在配送中心的時間窗內；式（17） 表示消除子回路；式（18）、式（19） 表示決策變量x、y為0～1 變量。

2 混合遺傳算法與設計

考慮多類型的生鮮配送路徑規劃屬于NP 難問題，小規模算例可用精確算法求解，大規模算例的計算復雜度增加，難以在可接受時間范圍內求解，因此設計混合遺傳算法進行求解。

2.1 遺傳算法

遺傳算法（Genetic Algorithm） 是模擬自然界生物進化機制的一種算法，遵循自然界適者生存、優勝劣汰的法則，即在搜索最優解的過程中保留有用的去除無用的過程。粒子群算法（Particle Swarm Optimization，PSO） 是通過模擬鳥群覓食行為的一種基于群體協作的隨機搜索算法，基本思想是利用群體中的個體對信息的共享從而使整個群體的運動在問題求解空間中產生從無序到有序的演化過程。

遺傳算法具有全局搜索能力強等優點，但收斂速度慢，容易早熟。而粒子群算法收斂速度快，但容易陷入局部最優。因此，本文將兩種算法混合使用，從而更快的獲得更優的解。算法流程圖如圖1 所示。

圖1 算法流程圖

2.2 算法設計

2.2.1 染色體編碼

財務人員管理是加強財務管理的基礎，財務人員是具體監管政策的執行者。政府監管部門及民辦非營利性醫療機構應重視加強對財務人員的業務培訓,促進他們提高業務能力和工作水平。主管部門在財務人員業務培訓時，應要求公立醫療機構和民辦醫療機構統一接受培訓。

本文采用整數編碼。根據客戶數目n，對客戶進行排序，生成長度為n 的染色體。根據車輛的容量約束進行解碼，根據車輛容量按順序將客戶分配到每一輛車，如車輛容量可以滿足一條染色體上客戶i 到j 的需求，則從客戶j+1 起的路徑，由配送中心的另一輛車配送，直到染色體上的客戶都被訪問，由此生成不同的配送路徑。

2.2.2 種群初始化及適應度函數

初始種群采用隨機生成，來保證個體的多樣性。適應度是衡量染色體個體優劣的標準，也是進行選擇算子操作的重要依據，適應度低的染色體個體會通過選擇算子進行淘汰。本文的生鮮產品配送路線優化模型的優化目標是希望綜合成本越小，對應的適應度就越大，得到的解就越優。因此可選擇綜合成本倒數作為適應度函數。即：

其中：f是染色體i 的適應度值，F是染色體i 所對應的的目標函數值。

2.2.3 選擇操作

2.2.4 交叉操作

采用單點交叉。隨機選取兩個染色體作為父本，在父代染色體中只隨機設置一個交叉點，將染色體分成兩部分，把兩個父本個體的部分基因片段進行交換，刪除重復基因，補充缺少的基因，從而得到兩個新個體。單點交叉過程如圖2 所示。

圖2 單點交叉

采用逆轉變異。在父代染色體中隨機選擇兩個點，然后將其之間的部分進行反轉。逆轉變異如圖3 所示。

圖3 逆轉變異

2.2.6 粒子更新操作

離散PSO 算法對粒子更新的運算符進行了重新定義，文獻[9]給出了運算符說明，粒子的速度和位置的更新公式為：別為自我學習因子和群體學習因子，p是粒子自身目前經歷的最優位置，g是整個粒子群目前經歷的最優位置。運算符! 作用后，當前粒子調整為最優位置的序列；運算符?與ω、c、c作用后，按概率保留速度中的調整序列，得到新速度；運算符⊕為調整序列的疊加作用。

3 算例分析

3.1 數據選取

數據選自Solomon 標準算例數據庫中R 類型（隨機分布）中的R101 算例，算例選取25 個客戶，1 個生鮮配送中心，生鮮配送中心及客戶位置如圖4 所示。對客戶各個種類的生鮮需求量等參數進行合理調整。其他參數設置如表2 所示。

圖4 R101 算例節點位置分布

表2 本文參數設置

3.2 結果分析

在Windows10 操作系統下，RAM 為8G，Intel（R） Core（TM） i5-8265U 的處理器上應用Matlab R2017b 編寫算法進行模型求解。

設定種群大小為200，終止進化代數為500，交叉概率為0.9，變異概率為0.05，慣性權重最大值為0.96，慣性權重最小值為0.4，自我學習因子為0.5，群體學習因子為0.5。分別用傳統遺傳算法和混合遺傳粒子群算法重復求解10 次，記錄每次運行的解及時間，并給出每次的解與10 次運行中最優解的偏差值（GAP），如表3 所示。

表3 模型求解10 次運行結果

R101 算例用遺傳算法求解10 次的平均運行時間為27.9685 秒，最優解為2 004.245，平均解為2 244.485，解的平均偏差值為11.99%，最大偏差值為24.28%；用混合遺傳粒子群算法求解10 次的平均運行時間為62.298 秒，最優解為1 804.577，平均解為1 903.713，解的平均偏差值為5.49%，最大偏差值為11.33%。與傳統遺傳算法相比，混合遺傳粒子群算法在解的質量上得到明顯改善，目標值平均降低15.18%；此外混合遺傳粒子群算法的平均偏差值也要比遺傳算法小，說明其算法穩定性較好。運行時間方面，混合遺傳算法加入了粒子更新尋優操作，運行時間較遺傳算法略有增加，但仍然在可接受范圍內。

取10 次運行解最小的結果作為最優路線，得到如下結果。遺傳算法和混合遺傳粒子群算法迭代次數如圖5 所示；圖6 為遺傳算法和混合遺傳粒子群算法求解的最優配送路徑圖。

圖5 算法迭代收斂示意圖

圖6 最優配送路徑圖

與遺傳算法相比，混合遺傳粒子群算法的收斂速度更快，求得的解更優，說明本文設計的混合遺傳粒子群算法求解性能較好。表4 給出了兩種算法10 次求解的最優解結果。

表4 算法結果對比

3.3 靈敏度分析

企業在生鮮配送末端采取不同的保鮮措施，會影響配送成本及貨物損失成本。為了進一步研究不同的生鮮保鮮投入對企業成本及產品貨損的影響，以便在生鮮配送過程中采取合理的保險措施，分別設置不同的生鮮產品單位制冷成本，對應不同的生鮮保鮮投入系數，每次實驗運行10 次取平均值，對比分析各項成本，如表5 所示。

表5 單位制冷成本及生鮮保鮮投入系數靈敏度分析

從表5 中可以得出，隨著生鮮保鮮投入的升高，制冷成本與貨損成本的變化呈悖反關系。但綜合這兩項成本之和及總成本的變化并非單調，如圖7 所示。這是由于隨著生鮮保鮮投入的變化，制冷成本和貨損成本變化的幅度不同，制冷成本增速變快，貨損成本下降的趨勢變緩，因此，當為降低貨損成本，對三種生鮮產品都采取制冷箱等保鮮投入較高的措施是不值得的。三種不同設置中，設置2（三類產品都采用冷藏措施） 的兩項成本之和及總成本最低，但相比這三種設置均對不同的產品采用一種保鮮措施，本文設置求得了最低的總成本，因此需要合理的設置對于不同種類生鮮的保鮮措施，以此來平衡制冷成本和貨損成本，從而使得系統最優。

圖7 不同生鮮投入系數對比分析

4 結 論

針對生鮮配送路徑優化問題，本文構建了以固定成本、運輸成本、制冷成本、貨損成本及時間懲罰成本總成本最小化為目標的路徑優化模型。與傳統配送問題相比，由于不同種類的生鮮產品隨時間的損耗不同，且時間要求較高，本文考慮不同種類的生鮮產品采用不同的保鮮方式，差異化新鮮敏感度敏感系數，引入生鮮保鮮努力系數，構建生鮮配送路徑優化模型；通過設計混合遺傳粒子群算法，利用Matlab 進行了算例驗證，通過對比分析傳統遺傳算法和混合遺傳粒子群算法，結果表明，混合遺傳粒子群算法在求解本文模型方面，求得的解更優，穩定性更好。針對生鮮配送過程中保鮮措施的選擇，進行了生鮮保鮮投入系數靈敏度分析，結果表明，隨著生鮮保鮮投入的升高，制冷成本與貨損成本的變化呈悖反關系，但對于綜合成本的影響，系統最優的保鮮策略是不同的生鮮產品采取不同的制冷措施，以此來平衡各項成本。

生鮮配送活動中存在許多不確定性，本文建立的模型中忽略了許多影響因素，研究可以進一步擴展，考慮生鮮需求波動等因素對于配送成本的影響。