生鮮肉品冷鏈配送最短路徑算法的構建與應用

王小輝 洪瑾芳 許海林 劉春秀 楊得勝 史 惠 陳冬群 鄭麗英

（1.永泰縣農業農村局 福州 350700；2.福建省動物疫病預防控制中心 福州 350003；3.南平市延平區動物疫病預防控制中心 福建南平 353000）

近年來隨著我國在國際上的地位不斷提高，在當今世界擁有著舉足輕重的地位， 作為世界第一大豬肉生產國和世界第一大豬肉消費國， 生豬肉的運輸問題一直面臨著巨大的挑戰。 隨著人們生活水平不斷提高，人們越來越注重食品安全問題，特別是對于生鮮食品， 這就對生鮮食品冷鏈物流配送提出了更高的要求。 肉類屬于鮮活農產品， 水分多容易被各種細菌、寄生蟲等污染，具有易腐爛性等特點，如果處理不到位，會造成非常嚴重的食品安全問題[1]，直接和間接威脅及影響到人畜的健康安全。 因此，對生鮮肉類冷鏈運輸的問題更應該找出最優化的方案。

1 背景及意義

目前國內農產品冷鏈物流的發展水平較為落后，生鮮物流還是以常溫運輸為主體的配送模式，生鮮食品的冷鏈流通率只有57%，而在歐美、日本等發達國家，易腐食品冷藏運輸率已超過90%，冷鏈流通率更是高達95%～98%。 而且，冷鏈物流的成本比常溫運輸要高出6%左右， 我國冷鏈企業通常的利潤率為10%，冷鏈利潤率僅為8%左右，而發達國家冷鏈的利潤率可以達到20%以上，冷鏈物流成本過高已成為制約冷鏈企業發展的重要因素。此外，冷鏈物流由于對溫控的要求比較高， 冷鏈斷鏈現象時有發生，產品腐爛變質更是屢見不鮮，我國冷鏈過程中的產品損耗率高達25%，從數據上很明顯可以看出尋找最科學最優化的路線， 沖破眼前的局面迫在眉睫，特別是在基層縣級的運輸線路。

在實際調查過程中發現， 很多縣級屠宰場生鮮肉品的配送路線未經精準計算，大多還采用無科學、無系統的運輸方式， 無形中進一步加劇了冷鏈物流的成本損耗。為有效提升冷鏈物流的效率，本文以福州市永泰縣為例對有關方面進行探討， 永泰縣常年平均氣溫在14.6～20.1 ℃，氣溫逐月變化基本近于周期性， 以1 月 （或2 月） 為最低， 月平均在5.5～11.0 ℃；7 月（或8 月）氣溫上升到最高值，月平均在23.0～29.0 ℃（見圖1）[2]。 從屠宰場宰殺后配送給最遠的洑口鄉，最遠距離為81.4 km，按冷藏車平均時速60 km/h 計算，單次配送也需要近90 min，目前該縣屠宰場已經采用專用冷藏車冷鏈配送模式， 但要配送給各鄉鎮， 沒有冷鏈將無法保證鮮肉在配送中達到質量需求。 為此，初步設定以一定約束條件[3]的假設基礎上，以最短的總路程為目標函數，構建縣級屠宰場生豬胴體冷鏈配送路線的最短路徑優化算法。 并將該算法的結果作為指導并應用到實際生產中，為其他縣域級冷鏈物流配送提供相應的參考。

圖1 永泰縣歷史各月氣溫趨勢

2 問題描述與研究假設

以福州市永泰縣青云食品公司屠宰場近年來生鮮肉品冷鏈配送的運輸情況、車輛、線路、輸送點、運輸時間等為研究對象。 設定屠宰場配送中心共配備冷鏈運輸車9 輛，其中2 輛載重2 000 kg，5 輛載重1 200 kg，2 輛載重350 kg。 為了能達到算法運算的構建要求，初步設定的約束條件假設為：（1）永泰縣青云食品公司屠宰場僅有單一配送中心， 其所有冷鏈運輸車均從該配送中心出發， 需要若干車輛完成對各鄉鎮生豬胴體配送點的鮮肉配送。（2）各鄉鎮生豬胴體配送點分布位置已知（見圖2）。 （3）各鄉鎮生豬胴體配送點之間的距離已知。（4）各配送點與屠宰場配送中心之間的最短距離已知， 路途中排除堵車的情況。（5）各鄉鎮生豬胴體配送點的貨物需求量和要求配送的時間窗已知， 排除路途中人為的耽擱時間。（6）配送路途中的內外溫度保持恒定。（7）車輛型號、車速運行統一。 （8）每條配送線路上都只有一輛車進行配送， 且每個鄉鎮生豬胴體配送點冷鏈運輸車只到達一次。 （9）配送過程中不存在裝貨的情況。

圖2 永泰縣屠宰場配送中心及各鄉鎮生豬胴體配送點分布情況

2.1 模型構建 路徑優化算法采用遺傳算法，2014 年王玥丹[4]證實遺傳算法可應用于冷鏈配送路線的適用性。以最短的總路程為目標函數，從一個配送中心出發， 以同種型號車輛不同的數量所到達的不同需求點為已知條件， 構建縣級屠宰場生鮮豬胴體冷鏈配送路線的最短路徑優化算法。 主要考慮的參數為冷鏈運輸車配送總時間和配送的最短路徑。通過數學函數測算最短配送路徑和時間， 確保冷藏生鮮豬胴體及時配送到各鄉鎮，滿足群眾的需求。

2.2 算法構建的參數及參數定義[5]k：表示車輛；m：表示車輛數目，車輛編號表示為k=1,2,......m；n：各鄉鎮生豬胴體配送點數目， 各鄉鎮配送點表示為i，j（i，j∈V，V={0,1,......n}）；V：表示任意不同的鄉鎮配送點（當V 等于0 時表示屠宰場配送中心）；tik，tjk：表示分別到達需求點i，j 的時間點；tei： 表示車輛到達需求點i 的最早時間點；tli：表示車輛到達需求點i的最晚時間點；pi： 表示需求點i 所需物料的備料時間；si：需求點i 所需物料的服務時間；dij：表示需求點i 和j 之間的距離；v： 配送車輛平均行駛速度；a：車輛每千米配送費用；Q： 配送車輛最大裝載容量；Qi：第i 個需求點的需求量；Cα：車輛早于需求點最早滿意時間點到達懲罰系數；Cβ： 車輛晚于需求點最晚滿意時間點到達懲罰系數；X：表示屠宰車間待宰和生豬胴體裝載時間（X={0,1,......n}）；y：表示各鄉鎮配送點卸載生豬胴體時間（y={0,1,......n}）；Z：表示各鄉鎮生豬胴體配送點卸載生豬胴體時間 （Z={0,1,......n}）。

2.3 模型構建步驟

2.3.1 冷鏈運輸配送時間 為能在預定的時間內保證鮮肉在配送中達到質量需求， 在規定的路程上需要的最短冷鏈運輸配送總時間就是冷鏈運輸車的行駛時間、 屠宰車間待宰和生豬胴體裝載時間以及各鄉鎮配送點卸載生豬胴體時間的算數和。

從需求點i 到需求點j 的行駛時間用公式表示為：tij=dij/v；冷鏈運輸車的行駛時間表示為屠宰車間待宰和生豬胴體裝載時間表示為：各鄉鎮生豬胴體配送點卸載生豬胴體時間表示為；冷鏈運輸車配送總時間最少的函數表示為

2.3.2 冷鏈運輸配送誤差系數 在冷鏈運輸過程及在設定的約束條件下總會出現概率性誤差。 在整個模型的建立中， 按照存在不同的情況需要有相應的應對措施-懲罰系數。 本文中懲罰系數指的是冷藏生鮮豬胴體能否在各鄉鎮的配送點和需求點期望時間窗內到達。不同期望時間窗存在不同的懲罰系數。如果早于期望時間到達就通過早到懲罰系數進行懲罰， 如果晚于期望時間到達就設置晚到懲罰系數進行懲罰。

2.3.3 算法的約束條件 當m 輛冷鏈運輸車均從同一個屠宰場的配送中心出發， 用公式表示為yok=m； 每個鄉鎮生豬胴體配送點均由一輛車配送，用公式表示為（i=1，2，...，n）；每個鄉鎮生豬胴體配送點有且只有一輛車訪問一次， 用公式表示為（j=0，1，...，n）； 冷鏈運輸車從屠宰場的配送中心出發，完成任務后返回配送中心，途中無裝貨，用公式表示為每條冷鏈配送路線上的所有鄉鎮生豬胴體配送點所需生豬胴體重量之和小于等于單位冷鏈運輸車最大裝載量，用公式表示為Q（k=1，2，...，m）；每個鄉鎮生豬胴體配送點到達的車輛和離開的車輛數目相同，用公式表示為同一配送路線上連續的兩個鄉鎮生豬胴體配送點間， 冷鏈運輸車到達前一鄉鎮生豬胴體配送點的時刻不超過到達后一鄉鎮生豬胴體配送點的時刻， 用公式表示為：xijk（tik+si+tij-tjk）≤0，（i≠j，k=1，2...，m）。

3 運算結果

應用Matlab2018a 編制與該算法匹配的程序，完成對屠宰場生鮮肉品配送算法的求解， 經過對算例進行多次隨機試驗，抽出的最優試驗結果及圖3-圖4[6]。 在節假日期間預估生豬胴體高峰需求時，需使用冷鏈運輸車8 輛， 其中使用載重350 kg 的2 輛，載重1 200 kg 的5 輛，載重2 000 kg 的1 輛，全部完成配送任務5 030.68 kg，冷鏈運輸車總行駛距離為736.4 km，總行駛時間為12.29 h（見表2）。而在非節假日期間預估生豬胴體低峰需求時， 需使用冷鏈運輸車7 輛， 其中使用載重350 kg 的2 輛，使用載重1 200 kg 的5 輛， 全部完成配送任務2 752.06 kg，冷鏈運輸車總行駛距離為613.7 km，總行駛時間為10.22 h（見表3）。

表3 非節假日期間冷鏈運輸車行駛路線的配送情況模擬結果

圖3 節假日期間車輛配送線路圖

圖4 非節假日期間車輛配送線路圖

4 討論分析

本算法采用遺傳算法求解最短路徑， 該遺傳算法由美國密歇根大學John H H 教授及其學生在20世紀六七十年代提出，其具有自組織性、自適應性和自學習性的特性，是一種“生成+檢測”的迭代搜索算法（見圖5）[7]。 它以種群中的所有個體為操作對象、 每個個體對應問題的一個解。 選擇、 交叉和變異是其3 個主要操作[8]。 遺傳算法利用遺傳算子進行組合交叉和變異， 逐代直到進化出代表最優解的種群。

圖5 遺傳算法基本流程

本算法測算是通過數學算法估算較合理的車輛最短路徑優化配置，在實際工作過程中，還需考慮車輛維修、維護、保養等車輛待場等情況，因此，該場配備一定的備用車輛就顯得非常有必要。 從運行結果可以看出， 冷鏈運輸車完成配送時間均控制在2 h左右，防止疲勞駕駛，保證駕駛人員的安全。 本算法測算目的是預估最短的行駛路線和最短的配送時間，但在目前低碳要求的情況下，還應該再考慮運輸成本、熱能損耗、實際路況、隨機需求等問題，有待于下一步的算法測算中再進行優化。