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

0 引 言

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

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

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

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

1.1 問題描述

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

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

1.2 基本假設(shè)

考慮到實際問題的復(fù)雜性，本文做如下假設(shè)：

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

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

（3） 配送中心的車輛為同質(zhì)車輛；

（4） 車輛勻速行駛；

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

1.3 參數(shù)說明

表1 參數(shù)和定量定義

1.4 模型建立

1.4.1 成本分析

①車輛的固定使用成本

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

③制冷成本

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

④貨損成本

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

⑤時間懲罰成本

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

1.4.2 目標函數(shù)

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

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

2 混合遺傳算法與設(shè)計

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

2.1 遺傳算法

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

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

圖1 算法流程圖

2.2 算法設(shè)計

2.2.1 染色體編碼

財務(wù)人員管理是加強財務(wù)管理的基礎(chǔ)，財務(wù)人員是具體監(jiān)管政策的執(zhí)行者。政府監(jiān)管部門及民辦非營利性醫(yī)療機構(gòu)應(yīng)重視加強對財務(wù)人員的業(yè)務(wù)培訓(xùn),促進他們提高業(yè)務(wù)能力和工作水平。主管部門在財務(wù)人員業(yè)務(wù)培訓(xùn)時，應(yīng)要求公立醫(yī)療機構(gòu)和民辦醫(yī)療機構(gòu)統(tǒng)一接受培訓(xùn)。

本文采用整數(shù)編碼。根據(jù)客戶數(shù)目n，對客戶進行排序，生成長度為n 的染色體。根據(jù)車輛的容量約束進行解碼，根據(jù)車輛容量按順序?qū)⒖蛻舴峙涞矫恳惠v車，如車輛容量可以滿足一條染色體上客戶i 到j(luò) 的需求，則從客戶j+1 起的路徑，由配送中心的另一輛車配送，直到染色體上的客戶都被訪問，由此生成不同的配送路徑。

2.2.2 種群初始化及適應(yīng)度函數(shù)

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

其中：f是染色體i 的適應(yīng)度值，F(xiàn)是染色體i 所對應(yīng)的的目標函數(shù)值。

2.2.3 選擇操作

2.2.4 交叉操作

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

圖2 單點交叉

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

圖3 逆轉(zhuǎn)變異

2.2.6 粒子更新操作

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

3 算例分析

3.1 數(shù)據(jù)選取

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

圖4 R101 算例節(jié)點位置分布

表2 本文參數(shù)設(shè)置

3.2 結(jié)果分析

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

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

表3 模型求解10 次運行結(jié)果

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

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

圖5 算法迭代收斂示意圖

圖6 最優(yōu)配送路徑圖

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

表4 算法結(jié)果對比

3.3 靈敏度分析

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

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

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

圖7 不同生鮮投入系數(shù)對比分析

4 結(jié) 論

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

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