基于改進遺傳算法的低碳冷鏈物流研究

劉子豪，劉祥偉

（安徽理工大學 經濟管理學院，安徽 淮南 232000）

黨的二十大報告再次強調要打造綠色低碳高質量物流體系，著重開展低碳物流、智慧物流、高效物流體系發展。低碳冷鏈物流路徑優化研究在節約能源、減少排放、提高資源利用效率、降低物流成本、保障產品質量與安全以及推動低碳經濟發展等方面具有重要意義，也符合可持續發展的需求，對于促進綠色物流發展具有積極作用。在生鮮食品運輸過程中，貨碳排放不可避免，如何科學地計算并對產品損耗進行控制是實現高質量生鮮食品運輸的重點工作，鄧紅星等人構建考慮碳排放成本因素的模型，將碳排放成本計入模型之中［1］。

車輛路徑（VRP）由Dantzig 等人在1959 年率先提出，是利用VRP數學模型建立解決該問題的啟發式算法［2］。由于我國物流運輸行業高速發展，VRP路徑問題在國內已深入研究。第一，求解模型構建不斷優化。首先對帶有時間窗問題進行模型構建。魏子秋等人將軟時間窗引入目標函數模型，利用客戶期望時間窗模型，計算出超預期時間罰款成本［3］。李想等人提出多目標模糊需求最小成本求解模型［4］。李尤等人結合顧客滿意度構建出模糊時間窗，并根據不同情景構建出相對應成本模型，然后在相關成本因素上進行多方面考慮［5］。李軍濤等人針對碳排放因素采用投入產出法計算運輸過程中所產生的碳排放量［6］，盧森等人提出生鮮行業的顧客滿意度成本模型［7］。第二，算法模型不斷改進。邵美晨采用NSGAⅡ算法對雙目標路徑優化問題進行求解［8］。張無瑞等人針對多中心車輛路徑問題設計出兩階段自適應遺傳算法，并結合TOPSIS模型［9］。郭文強等人在遺傳算法基礎上添加變領域搜索并結合A*算法［10］。周國華等人利用天牛須-遺傳混合算法（BAS-AGA）對多層級選址問題進行求解［11］。

綜上所述，針對車輛VRP路徑優化問題，不僅進行了成本模型的考慮，更將算法進行了各種融合，問題不斷復雜化，但是算法求解速度和精度都在提高。通過研究對象A，考慮碳排放和貨運損耗，在遺傳算法的基礎上，綜合已有的研究結果進行算法優化，從而實現降低排放成本和運費，以期提高企業經濟效益，實現低碳綠色運輸目標。

1 問題描述與模型構建

1.1 問題描述

帶時間窗的車輛路徑規劃問題（Vehicle Routing Problem with Time Window，VRPTW）是在VRP基礎上添加配送時間約束條件產生的一個新問題。在這類問題中，假定為單一配送中心，且顧客所需只由該配送中心提供服務，對指定車輛至目的地的最早或最晚到達時間進行確定，要求車輛必須以規定的服務時間到達，若提前或延后，均視為違背規定，并在路費方面給予處罰，且車輛負載具有最大限度，在完成工作后返回原配送中心。通過分析，將燃油費、固定費、損耗費、懲罰成本和碳排放等因素納入成本目標函數計算，其中在計算貨損成本時引入特定變質率與損耗率，將貨損成本考慮為風險成本并計入目標函數之中，同時引入碳排放系數與碳排放價格，結合參考文獻估算出碳排放成本，是復雜模型下的成本最優解問題，此問題旨在尋找滿足所有約束條件的最優路徑方案，求出最小配送成本。

1.2 參數設置

L0:表示配送中心；

M:｛1，2，3...m｝所有可用車輛的集合；

N:｛0，1，2...n}其中0表示配送中心，其他表示顧客配送點；

Q:表示運輸車最大荷載量；

V0:表示運輸車特定平均運輸速度；

C:目標函數成本。

表1為模型相關參數值設定。

表1 基礎參數設置

1.3 假設條件

（1）所有路徑運輸車均為相同型號，最大載重相同且無法裝載超過載重限制的貨物；

（2）每個客戶必須被恰好一輛車服務，所有車輛最終必須返回起點中心；

（3）配送中心與客戶的所有信息，包括需求量、位置與時間窗等均為已知條件；

（4）不考慮交通擁堵因素與其他未知因素，車輛假定為全程勻速行駛；

（5）所配送的產品是同一種類、同一規格的商品，沒有差異性；

（6）每個配送點與配送中心之間的運輸路徑具有確定性，即路線確定、交通情況穩定、運輸時間可控制；

（7）產品的每個客戶（發貨點或收貨點）對于到達時間都有要求，即每個客戶都有一個指定的訪問時間范圍，車輛必須在該時間窗口內到達客戶處；損壞率為可控因素，即假定其在運輸時間范圍內損耗率相同；

（8）每輛運輸車不考慮最大行駛距離，即假定不受可行駛距離約束；

（9）所有的顧客需求均為靜態，不考慮實時變動因素。

1.4 路徑優化目標函數模型構建

1.4.1 固定成本

固定成本并不考慮運輸時間及車輛使用年限產生的動態成本變化，只涵蓋運輸過程中相關工作人員薪酬、車輛折舊費以及車輛維護費等費用。

式中，fm為第m輛車的固定使用費用；Gm為0，1 決策變量，若Gm=1，表示第m輛冷藏車被使用，否則Gm=0.

1.4.2 運輸成本

車輛運輸成本主要包括車輛燃油費用，在不考慮路況與氣溫等不可控因素的情況下，車輛燃油費用與運輸車行駛距離成正比。運輸成本為

式中，f2表示運輸車在單位距離行駛過程中所產生的運輸成本；dij表示配送中心i與顧客服務點j之間的距離，為0，1決策變量，當冷藏車m從配送中心i配送到超市門店j時，，否則，數值為0.

1.4.3 貨損成本

根據生鮮農產品變質的客觀規律構造函數I（t）=IOe-ε來定量描述生鮮農產品的變質程度，其中I（t）表示在時間t時刻生鮮農產品的變質程度，I0表示初始狀態下貨品品質水平，ε表示變質速率，變質率數值與貨物所處自然環境的溫度及濕度等相關，且與運輸花費時間呈指數型增長關系［12］。運輸車輛到達門店j時，打開車門前在行駛過程中產生的貨損成本為

在整個產品流通過程中裝卸服務在自然環境下進行，車內溫度會與所設定的理想溫度產生差異，意味著其變質率與在運輸過程中處于特定溫度條件下的變質率有所差異，故應根據所設定的服務時間內計算其損耗成本，公式如下:

式中，p為生鮮農產品的平均單位價格；ai為顧客i對于生鮮產品的需求量；為運輸車從顧客i到顧客j之間運輸所花費的時間；ε1為生鮮農產品在特定溫度下的變質率為0、1 變量，當車輛為生鮮超市門店i服務時，則=1，否則=0；ε2為在顧客進行裝卸等服務期間產品特定變質率；ti為在客戶i的冷藏車服務時間。

1.4.4 碳排放成本

碳排放成本包括制冷導致的碳排放和在生鮮運輸過程中的耗用能源，包括汽油、柴油等所造成的二氧化碳排放的費用兩部分組成的成本。其中燃油消耗量與交通工具的運輸距離和載重成正比，為將碳排放轉化為成本，引入碳排放數值關系函數［13］，如下列函數所示

式中，e0表示運輸車輛在空載情況下單位配送距離所產生的油耗量；e1為滿載情況下的油耗量；Q為冷藏車的額定載重量，m=1，2，3；x為車輛載重量。

在生鮮農產品配送過程中燃油所產生的碳排放成本為

式中，Pc為單位碳稅價格；ρ為碳排放系數；λ為配送單位重量貨物行駛單位距離制冷產生的排放；Qij為從超市i到超市j運送的貨物量。碳成本公式如下

1.4.5 懲罰成本

時間懲罰成本［ETi，LTi］為超市門店i期望被服務的時間窗；［EETi，LLTi］為超市門店i可以接受服務的時間窗。事實上，逾越時間窗規定并不會產生懲罰性費用，但會對顧客滿意度產生影響。因此必須考慮時間窗，將時間窗約束轉化成本對路徑選擇進行約束［14］。然而，本研究的研究對象是易腐敗的生鮮品，遲早都會出現產品損耗，因而必須將懲罰性費用引入成本模型中，以促進客戶的滿意度和提升產品的質量。圖2說明懲罰性費用與時間的關系。

懲罰時間與時間窗之間函數關系如下:

約束條件（11）表明為客戶提供服務的運輸車數量不超過配送中心擁有的運輸車總和；

約束條件（12）表示所有運輸車對配送點逐一提供服務后返回配送中心；

約束條件（13）表示每條運輸路線上的運輸車所運輸貨物重量不超過最大荷載量；

約束條件（14）表示每個顧客必須由一輛運輸車提供配送服務，且每個配送中心有且只能有一次配送機會，不考慮動態需求；

約束條件（15）與（16）表示0、1決策值約束；

約束條件（17）表示配送時間要在所設定的約定時間窗內。

2 改進遺傳算法設計與算法步驟

2.1 改進遺傳算法設計

傳統遺傳算法在處理單目標問題方面表現出較強的適應性，但對于NP-Hard 多目標路徑優化問題而言，其選擇操作通?；谶m應度函數對個體進行評估，選擇概率與適應度相關。而在多目標路徑優化問題中，個體之間的相似性往往會導致種群陷入局部最優解。為了解決這一問題，在傳統遺傳算法的基礎上，改進后的遺傳算法引入了貪婪算法、精英保留策略以及移民操作。通過利用貪婪算法構建初始化種群，可以快速生成一組較好的個體，增加了初始種群的多樣性。同時，通過精英保留策略在每一代中保留適應度最好的個體，防止種群陷入局部最優解。此外，引入移民操作可以在不同子種群之間進行個體交流，增加種群的多樣性，并避免陷入局部最優解。

2.1.1 貪婪算法初始化種群

本質是在局部搜尋最優解，達到局部最優目標。具體操作如下:在種群隨機選取一個客戶Ii，將其添入個體之中，然后在未加入個體的群體中進行搜索，找出距離目前客戶最近的客戶Ij并加入個體之中，如此循環操作直至所有顧客均加入個體。由于運輸車具有運載重量限制，故其算法也應設置約束條件，公式如下

對各條基因上相應的生鮮需求量進行累計，當累計至第n個客戶時，顧客總需求量小于車輛最大荷載數，累計至n+1 顧客時，結果則相反，那么此時就在第n個顧客后插入終止編碼符號0，表示一條染色體編碼完成，如3-5-1-6-9-4-0，如此反復直至所有個體均被編入，形成可以滿足種群數量規模的數目。

2.1.2 精英策略

具體操作為:首先依據適應度函數值從大到小進行排序，后將排在前10%的優秀個體進行保留，對續子代染色體進行適應度評估，接著將所保留的優秀個體替代子代后10%劣質基因。替代完成后進行輪盤賭法，為確保所保留的優秀基因能夠全部保留，在輪盤中單獨設置概率為1的區域。而其他個體通過個體適應度占群體總適應度的比例來賦予比例，通過輪盤形式隨機選取，采用下列公式進行概率賦值。

2.1.3 PMX部分匹配交叉

基因交叉是指將兩個父體的部分基因進行替換，在保留父代部分相較優秀的基因前提下產生新的子代，其中常用方法為PMX（Partially Mapped Crossover，簡稱PMX）交叉。其原理是從兩個父代染色體中選擇兩個交叉點，將這兩個交叉點之間的基因段交換位置，并保持其中的元素映射關系不變，進行交叉后執行沖突檢測，消除交叉后所形成的重復個體。具體操作如下。

步驟1:從一組父代染色體中隨機選取位置相對應的兩個基因作為起止位置。

步驟2:交換所選取兩組基因位置。

步驟3:做沖突檢測。根據兩組所交換的基因建立映射關系，如圖5 所示，以3-6-2 這一映射關系為例，在子代A 中編號為2 的基因重復存在，此時根據映射關系，將原父代基因2 轉變為基因3，以此重復操作，直到沒有重復沖突基因為止。操作如圖5所示。

2.1.4 逆轉算子

采用逆轉算子策略，將子代基因進行基因突變操作，具體操作為:隨機選取片段基因上的兩個基因位置點，將片段內基因進行逆轉。

2.1.5 移民策略

移民策略是在交叉變異操作后，由于交叉變異具有隨機性，可能會將優秀個體或優秀子代進行破壞，而移民策略是在保留潛在最優解的前提下人為將優秀個體保留至群體之中，可增強種群多樣性與后代基因的質量，從而提升算法搜索能力與準確性。需要進行該操作應根據已設定的閾值進行判定，判斷是否有早熟收斂跡象，公式如下:

其中，fi表示第i個體的適應度值，favg表示整個群體的平均適應度，當結果E低于所設定的值時便進行移民操作，增強算法收斂性。

2.1.6 動態交叉變異概率

動態改變交叉變異概率的原理為當種群適應度趨于一致或有陷入局部最優可能時增加其概率，而當種群適應度過于分散則可適當降低交叉變異概率，公式如下:

其中，f'表示所挑取兩個要交叉的個體中適應度值較大的，f要變異的個體的適應度值。Pc1，Pc2分別表示最大與最小交叉概率，Pm1，Pm2分別表示最大和最小變異概率，Pc1，Pc2，Pm1，Pm2均為0 至1 之間的常數。設置Pc1=0.8，Pc2=0.6，Pm1=0.1，Pm2=0.001.

2.2 算法步驟

經過上列算法改進后再編入算法步驟之中，引入貪婪算法、動態交叉變異概率以及精英策略與移民操作，步驟示意如圖8所示。

3 實例驗證

3.1 門店距離與需求信息

以合肥市周谷堆蔬菜交易中心A 為研究對象，依據相關資料在合肥市不同行政區選取20 個顧客，其中配送中心以“0”表示，“1～20”代表20個不同的顧客。依據百度地圖進行標點得到服務點分布圖，再使用相關地圖測距工具，建立以橫縱坐標為（25，15）的距離圖，坐標數據來源于百度地圖，位置如圖9所設計。參考當地瓜果蔬菜交易數據對服務點的需求量、配送時間與時間窗要求進行估計。

表2 運輸車輛數據

為直觀觀測地理位置分布，通過Excel軟件，將位置坐標轉換為單位為km的散點分布圖，如圖10所示。

圖1 多路徑規劃示意圖

圖2 時間懲罰成本與時間關系圖

圖3 父代基因片段選取示意圖

圖4 子代基因交換示意圖

圖5 沖突檢測示意圖

圖6 最終子代基因示意圖

圖7 子代基因突變操作示意圖

圖8 改進遺傳算法的求解步驟

圖9 顧客地理位置

圖10 客戶分布散點圖

配送中心所用車輛為解放冷藏車，通過車輛生產商獲取運輸車參數信息，如表2 所示。從表2 可知，該型號最大運輸荷載為10t，且生鮮運輸多為上午4:00—9:00 之間，不需考慮市區內堵車的影響，依據行政區內運輸車限速政策，可假定總體車隊平均行駛速度為60 km/h，每輛運輸車的固定使用成本為300 元/輛，每輛運輸車的單位行駛距離成本為2 元/km，其他基礎參數設置與上文保持一致。

表3中，編號0表示配送中心，1～20表示顧客編號，通過地圖工具以（25，15）為配送中心向四周輻射并測算出顧客所在坐標軸距離以及根據市場綜合判斷出期望時間窗與可接受時間窗，需求量依據相關統計資料進行特定估算。

表3 A企業冷鏈配送需求信息表

3.2 模型求解與結果分析

3.2.1 傳統遺傳算法與改進遺傳算法對比

通過MATLAB2021 對VRP路徑最優問題進行實例仿真，電腦處理設備參數為12thGenIntel（R）Core（TM）i5-12500H 2.50 GHz，內存16GB.設定初始種群NP（0）為100，算法迭代次數MAXGEN為2000，交叉變異概率采用動態自適應概率，代溝GGPA=0.9.

分兩個模塊進行數據求解與對比分析，下列為傳統遺傳算法與改進遺傳算法之間性能的對比。

在對兩種基因算法路徑優化迭代圖（圖11）進行比較后，得到如下結論:傳統遺傳算法在經歷200次迭代后便開始收斂，600次迭代后陷入局部最優，而改進后的遺傳算法在大約850次迭代后開始趨于收斂，求解時間雖然加長，但所求總成本數值更小，最優解更優。

圖11 傳統遺傳算法與改進遺傳算法求解迭代對比圖

通過表4 可知傳統遺傳算法成本最優解為4284.63 元，需6 輛車配送，配送路線為［0，9，7，16，1，0］，［0，18，17，13，8，0］，［0，10，3，4，0］，［0，14，15，19，0］，［0，6，5，12，0］，［0，2，20，11，0］.改進后遺傳算法最優成本為4088.79 元，需6 輛車配送，配送路線為［0，6，4，10，0］，［0，19，17，13，1，0］，［0，16，17，14，12，0］，［0，20，9，8，3，11，0］，［0，18，5，0］，［0，2，15，0］.改進后的總成本下降近4.5%，其中運輸成本下降近7.9%.圖12與圖13分別為傳統遺傳算法與改進遺傳算法路徑圖。

表4 遺傳算法與傳統遺傳算法最優配送方案詳細信息 單位:元

圖12 傳統遺傳算法路徑圖

圖13 改進遺傳算法路徑圖

3.2.2 碳排放成本對改進后遺傳算法求解影響

為在改進遺傳算法基礎上考慮碳排放成本是否會影響路徑抉擇與最優解數值，將目標函數中不包含碳排放成本的算法與包含碳排放成本的算法進行對比，不包含碳排放成本的算法模型中的碳排放成本是根據求解結果進行獨立計算。圖14與圖15分別為不包含碳排放成本路徑與包含碳排放成本路徑。

圖14 不包含碳排放成本路徑

圖15 包含碳排放成本路徑

表5 結果為在最大迭代次數內的最優解。經過仿真運行，通過兩組數據的比較，可以得到如下結論:在考慮到碳排放的前提下，總成本不僅沒有增加，反而減少了2.3%，碳排放的成本下降了2.1%，運輸費用降低了8%.這是由于碳排放成本與時間成正比，要降低碳排放成本，需要盡量縮短運輸路程，以降低成本，從而對貨物運輸費用和損耗費用產生影響。該算法能增強收斂性和搜索能力，同時還指出路徑優化中碳排放成本具有重要意義。

表5 包含碳排放成本與不包含碳排放成本最優配送詳細信息 單位:元

4 小結

目前生鮮農產品冷鏈運輸存在求解結果差異較大且運行時間長、易陷入局部最優解等問題。文章首先將碳排放成本引入生鮮配送成本模型之中，對傳統求解模型進行改進，然后采用貪婪算法構建出初始種群，為增加種群多樣性與最優解搜索能力在動態概率交叉、變異后引入移民策略。最后對A 企業進行實例驗證，運用MATLAB2021 對傳統遺傳算法與改進后的遺傳算法進行數據對比，驗證文章設計后的遺傳算法可以改善傳統遺傳算法的不足，該研究對于改進遺傳算法缺陷以及綠色冷鏈提供一定的參考。