考慮多類型產(chǎn)品新鮮度的生鮮配送路徑優(yōu)化

酒艷妮，胡大偉 （長安大學(xué)運(yùn)輸工程學(xué)院，陜西 西安 710064）

0 引 言

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

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

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

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

1.1 問題描述

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

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

1.2 基本假設(shè)

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

（1） 客戶點(diǎn)位置、時(shí)間窗及與配送中心的距離已知；

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

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

（4） 車輛勻速行駛；

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

1.3 參數(shù)說明

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

1.4 模型建立

1.4.1 成本分析

①車輛的固定使用成本

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

③制冷成本

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

④貨損成本

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

⑤時(shí)間懲罰成本

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

1.4.2 目標(biāo)函數(shù)

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

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

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

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

2.1 遺傳算法

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

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

圖1 算法流程圖

2.2 算法設(shè)計(jì)

2.2.1 染色體編碼

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

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

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

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

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

2.2.3 選擇操作

2.2.4 交叉操作

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

圖2 單點(diǎn)交叉

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

圖3 逆轉(zhuǎn)變異

2.2.6 粒子更新操作

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

3 算例分析

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

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

圖5 算法迭代收斂示意圖

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

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

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

3.3 靈敏度分析

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

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

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

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

4 結(jié) 論

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

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