基于K均值聚類算法的生鮮運輸路徑優化模型

周蓉蓉 陳 棟 劉思遠

（1.南京國家現代農業產業科技創新中心，南京 211800；2.國家農業信息化工程技術研究中心，北京 100097；3.智慧農業技術集成與應用創新農業農村部重點實驗室，南京 211800；4.廣西大學計算機與電子信息學院，南寧 530004）

1 引言

近年來，隨著生活水平的提高，人們對生鮮農產品的需求不斷增加，我國的生鮮市場規模不斷擴大，對生鮮的冷鏈配送服務要求日益增加；由于冷鏈配送受交通狀況與配送地分散程度的影響較大，尤其在一線城市普遍面臨著生鮮配送成本高、配送訂單分散的問題。目前，我國大型生鮮供應企業每日的貨物配送仍舊需要人工根據配送地址對配送車輛進行調度安排，耗費的人力時間成本較高，而且無法保證配送成本的最優化。如今隨著物流技術[1]的快速發展，生鮮冷鏈配送的調度、路徑選擇正向智能化方向發展。基于以上背景，通過引入車輛路徑問題（Vehicle Routing Problem，VRP）[2]求解方法，研究生鮮冷鏈配送路徑優化算法，對提高物流效率，降低成本具有重要意義。

冷鏈物流路徑優化問題(Vehicle routing problem,VRP)于1959年提出后[2],成為運籌學與組合優化領域的熱點問題，而生鮮農產品物流作為冷鏈物流分支，也受到了學界的極大關注。生鮮農產品物流涵蓋包裝、裝卸、運輸、儲存、加工和配送等多個環節，涉及從農業生產到銷售終端，跨越不同行業及不同企業，參與主體多元、組織化程度不一，從業人員專業能力和知識水平參差不齊，加上農產品運輸成本、儲存加工保鮮成本、流通中介費用等層層疊加，導致物流成本上升。在物流成本占比中，糧食類農產品為40%左右，蔬菜、水果等生鮮農產品超過60%[3]。國內冷鏈物流近些年取得了高速發展[4]，但仍然存在冷鏈物流流通率較低、地區發展不均衡、冷鏈物流體制不健全，以及第三方物流發展緩慢等問題。當前，國內冷鏈物流網絡優化主要包括配送中心選址和配送路徑優化兩個問題，對于冷鏈物流配送中心選址問題的研究，需要考慮的不確定變量較多，因此研究的范圍也比較廣泛，主要研究的還是被選擇的配送中心點與輻射半徑的距離之間的約束、用戶需求量與配送中心點之間的約束等問題，采用的方法也較多，包括采用啟發式算法[5]、混合算法[6]、元啟發式算法[7]、模擬退火算法[8]、禁忌搜索算法[9]、蜂群算法[10]等現代智能優化算法。冷鏈物流配送路徑優化問題的研究目前主要考慮對不同成本因子的約束研究，包括配送過程中的運輸成本、時間窗約束下的懲罰成本、貨損成本等，有的也考慮了碳排放成本[11-15]，王芳等對帶時間窗的多目標蔬菜運輸配送路徑優化進行了研究[16],吳亮然等提出了基于車輛配送線路的區域協同配送方法[17],趙志學考慮擁堵區域的多車型綠色車輛路徑問題優化[14],杜琛等將客戶滿意度和最小損耗加入了目標函數，對冷鏈配送路徑優化問題進行了求解[18]，以上研究為本研究提供了求解參考。

綜上所述，當前的冷鏈物流車輛路徑優化問題多以變化不同優化因子作為研究目標函數，從而得出一種或多種約束因子的車輛路徑優化模型。但針對大城市內配送目的地分布范圍廣的場景，比如針對城市生鮮配送較為鮮見。陳棟等對跨省雛雞配送場景提出了訂單分群的求解方法[1]，為解決大城市生鮮配送路徑優化問題提供研究思路。本研究通過引入K 均值聚類算法，根據配送目的地位置進行配送單元劃分，并以配送距離和貨物損耗最小、車輛使用數較少為目標函數，構建生鮮配送路徑優化模型，并使用改進的遺傳算法進行求解，以北京某生鮮農產品供應商實際配送車輛數據進行模型驗證。在此基礎上設計研發了適用于城市生鮮農產品配送的車輛路徑優化服務系統，實現了生鮮配送車輛調度優化等功能。

2 模型構建

2.1 問題描述

北京某生鮮農產品企業每天負責北京各大商超的生鮮果蔬配送，配送的目的地跨越北京全市，地理位置跨度較大，每天需要針對不同配送需求進行車輛配送安排，并盡可能減少車輛所走的路程，同時需要滿足客戶的時間要求。本研究根據實際場景，對研究范圍進行約束如下：①此企業只有一個配送中心，每天所有生鮮果蔬貨物由此配送中心統一配送；②配送所使用的冷鏈車輛的型號、載重量、體積都相同；③配送的客戶目的地的位置固定，且每天的需求量一定；④配送安排盡可能達到路程最短，使用的配送車輛數量盡可能少。

2.2 模型構建

基于以上問題的描述，構建生鮮農產品配送路徑優化目標函數，目標函數的約束條件為配送總里程、車輛數、時間窗約束條件，其數學表達如下。

一是確保每條路徑上各客戶的貨物需求量之和不超過配送車輛的載重量：

二是確保每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離：

三是確保每條路徑上的客戶數不超過總客戶數：

四是確保每個客戶都得到配送服務：

五是確保每條路徑的客戶的組成：

六是限制每個客戶僅能有一臺配送車輛送貨，當第k 輛車服務的客戶數≥1 時，說明該臺車參加了配送，則取sign(nk)=1，當第k輛車服務的客戶數＜1時,，表示未使用該臺車輛，則取sign(nk)=0。表達如下：

在本研究中，對于時間懲罰函數默認為一個常數，此參數不在本次研究中作為動態約束條件，為下一步深入研究做預留。

3 模型求解

3.1 求解流程

針對生鮮農產品配送問題，本研究設計了兩種求解流程，一種是直接對所有配送訂單進行整體路徑優化求解，如圖1 所示。①鮮配送訂單數據預處理，提取出訂單中訂單編號、地址（經緯度）與訂單的需求量、客戶配送時間等信息；②將全部生鮮配送訂單信息與車輛信息作為參數輸入到遺傳算法中，按照優化目標函數，匹配相應的配送車輛，經過算法的復制—交叉—變異等迭代操作，最終選擇表現最好的結果輸出。

圖1 整體優化流程圖Fig.1 Overall optimization flow chart

另一種采用根據訂單目的地位置先進行聚類，然后分組進行路徑優化求解，如圖2所示。

圖2 基于聚類的優化求解流程圖Fig.2 Optimization flow chart based on clustering

①對生鮮配送訂單數據預處理，提取出訂單中訂單編號、地址（經緯度）與訂單的需求量、客戶配送時間要求等信息；②根據配送目的地的經緯度信息，采用基于位置的K均值的聚類方法，對生鮮配送訂單進行聚類劃分小組，形成多個訂單配送單元。③將劃分好的訂單配送單元中的配送信息作為算法參數進行輸入，調度優化算法基于遺傳算法對每個訂單配送單元的配送信息按照目標函數進行求解，最終選擇表現最好的結果輸出。④將對每個訂單配送單元優化的結果進行合并后輸出。

3.2 配送目的地聚類方法

在3.1 小節中，采用根據訂單目的地位置先進行聚類，然后分組進行路徑優化求解。本研究采用K均值聚類算法根據配送訂單目的地經緯度進行配送訂單位置聚類。K 均值聚類算法是一種非層次聚類算法，在最小誤差的基礎上將數據劃分了特定的類，類間利用距離作為相似度指標，兩個向量之間的距離越小，其相似度就越高[1]。其算法求解過程中，關鍵是確定K 的值，本研究使用肘部法與輪廓系數確定K的值。

本研究選用了北京某生鮮供應企業的209 個真實訂單數據，其訂單的位置散點分布如圖3所示。

圖3 訂單位置散點圖Fig.3 Order Position Scatter Chart

通過肘部法確定聚類K（最終的簇數）值，如圖4所示。取不同K值的平均畸變程度曲線，曲線曲率最高的K值范圍在8～15之間。

圖4 K均值聚類肘部法則平均畸變曲線Fig.4 K-means clustering elbow rule average distortion curve

通過輪廓系數法確定K（最終的簇數）值，如圖5所示。由此確定K=10，系數最大。

圖5 K取不同值對應的聚類效果圖Fig.5 Clustering effect with different K values

3.3 遺傳算法求解過程

通過對遺傳算法進行改進，實現對生鮮農產品配送路徑優化的求解，結合實際生鮮果蔬訂單配送路徑優化問題，確定問題求解的具體流程如下。

算法參數與數據初始化，對種群規模Population-Size、交叉概率Pc、變異概率Pm、進化代數GenerationNum 以及懲罰函數Pw 等參數進行初始化設置，提取生鮮農產品配送訂單中的訂單編號、訂單經緯度、訂單的貨物需求量等數據。②初始化種群，對種群個體進行編碼，生成對應規模的種群矩陣。③計算種群中每個個體的目標函數值，根據目標函數值確定每個個體的適應度，選取適應度最優的個體保留。④對種群中的個體進行交叉、變異操作，生成新的種群。⑤重復③—④步，直到滿足進化代數。⑥將適應度最優（適應度值最小）的個體作為最優解輸出。

4 結果分析與模型應用

4.1 數據的初始化及求解過程

本研究選用北京某生鮮供應商的209 條配送訂單數據作為樣本數據。數據項包含訂單編號、客戶姓名、配送時間、最后達到時間、地址、經度、緯度、農產品數量、農產品重量、農產品體積、出貨倉庫編號、出貨倉庫名稱、客戶是否為VIP。篩選訂單編號、經度、緯度、農產品重量、農產品體積、出貨倉庫地址數據項作為求解數據，數據概要如圖6所示。

圖6 實驗數據概要圖Fig.6 Schematic diagram of experimental data

求解過程如下：

（1）種群初始化：以配送訂單的順序作為一個種群的個體，即一個染色體。

（2）種群描述矩陣：生成一個矩陣，一行代表種群中一個個體，列代表客戶訂單編號。矩陣如下所示：

（3）結合實際情況，對配送車輛進行數字化描述，規定只有一種類型的車輛，載重為8噸、容積為50立方米；車輛數量滿足當日訂單數。

（4）求解：①數據初始化。②初始化種群生成。③計算種群適應度：fitness-個體路徑的總里程，取倒數fitness=1/evaluation;一般適應度越大越好，在總里程中約束中是越小越好，故在此去倒數。④計算種群中各個個體的累計概率:。⑤記錄種群中適應度最好的個體。⑥生成新的種群：選擇上一代中最優個體作為新種群的第一個個體，另外使用輪盤賭法選擇生成剩余m-1 個個體；按照交叉概率Pc 使用OX交叉法對種群進行交叉；按照變異概率Pm 對種群中個體進行變異。⑦判斷種群的代數是否達到設置數。不滿足則重復執行③-⑦；滿足則輸出最優的個體，求解結束。

（5）對遺傳算法參數進行設置：種群數量為200個，交叉概率為0.5，變異概率為0.05，迭代次數為10000 次。經過以上求解步驟，得到適應度曲線，如圖7所示，在種群迭代進化5000次后，趨于平緩。

4.2 求解結果比較與分析

基于以上求解步驟，分別對整體路徑優化求解結果和經聚類后的路徑優化求解，如圖8 所示，未聚類與聚類的配送區分明顯，使用聚類的方法對配送訂單分布更清晰。

圖8 配送訂單聚類前后效果對比圖Fig.8 Comparison of the effect before and after the clustering of delivery orders

如表1 所示。對比兩種方式的求解結果，配送優化總里程和車輛使用數量，由表中可以看出，未經聚類的優化里程平均3753.01Km，使用車輛數平均32輛；經聚類的優化里程平均2105.4Km，使用車輛數平均輛34 輛；在車輛使用數量相差不大情況下，配送運行總里程大幅度降低。結果顯示使用聚類的方式具有合理性。

表1 不同算法求解算例計算結果Table 1 Calculation results of examples solved by diferent algorithms

4.3 模型應用

本研究通過基于以上研究，設計研發了適用于城市生鮮農產品配送的車輛路徑優化服務系統，實現了生鮮配送車輛調度優化等功能，為生鮮供應企業減低配送成本，提升企業效率提供了科技支撐。系統采用B/S架構，將模型打包成服務，提供API調用接口的形式來為生鮮供應企業服務。系統功能運行流程如圖9所示。

圖9 配送路徑優化服務流程Fig.9 Optimizing service progress

系統的服務API接口與應用實例如圖10所示。

圖10 系統服務實例Fig.10 System running instance

5 結果與建議

本研究針對生鮮農產品城市配送場景，針對其配送訂單分散，配送成本高，配送路線選擇人工依賴性強的問題，提出了基于K均值聚類算法的生鮮運輸路徑優化模型，通過引入K 均值聚類算法，實現了根據配送目的地位置的配送單元劃分，并以配送距離和貨物損耗最小、車輛使用數量較少的情況做為目標函數，構建生鮮配送路徑優化模型，模型使用改進的遺傳算法進行求解。通過對北京某生鮮供應企業實際的配送訂單的數據分析與求解，分別對未聚類與聚類情況下的求解結果進行對比，結果顯示配送目的地不進行聚類情況下配送的里程平均為3753.01 公里，使用的車輛數量平均為32 輛；在對配送目的地進行聚類情況下配送的里程平均為2105.4公里，使用過的車輛數量平均為34 輛；在使用車輛數量增幅不多的條件下對配送目的地聚類分組后模型讓配送總里程比未進行聚類分組的情況降低了43.9%。通過對城市生鮮農產品配送的車輛路徑優化服務系統的設計與研發實現了生鮮配送車輛調度優化服務功能，為生鮮供應企業降低配送成本和提升企業效率提供了技術支撐。

本研究對大城市范圍的生鮮配送路徑優化問題中的訂單位置聚類問題進行了深入的研究，其優化的約束條件只考慮了配送總里程與配送車輛，在下一步研究中，將對配送時間窗、碳排放等約束條件以及考慮不同聚類算法的使用對優化結果影響性進行研究。